Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:17 Di 01.08.2006 | | Autor: | mond |
| Aufgabe | Aufgabe:
(a) Sei G=(V,E) ein zusammenhängender Graph und e von E eine Kante. Zeige: Der Teilgraph G1( V, E\ {e}) ist genau dann zusammenhängend, wenn es einen Kreis in G gibt, der die Kante e enthält.
(b) Zeige, dass es in einen zusammenhängenden Planaren Graphen mit 20 Knoten und 40 Kanten mindestens 8 Dreiecke gibt. |
Bitte kann Jemand mir hilfen.
wie kann ich a und b beantworten
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:14 Di 01.08.2006 | | Autor: | kretschmer |
Hallo,
also es wäre schön, wenn Du nicht einfach nur nach einer Lösung fragst, sondern auch sagst, was Du bereits geschafft hast. Dann kann man Dir auch helfen!
Zum Teil a): Also ich würde das vielleicht per Widerspruch versuchen. Angenommen e gehört nicht zu einem Kreis ...
Zum Teil b): Da würde ich mir die Eigenschaften zu Hilfe nehmen, die planare Graphen ausmachen. D.h. man hat keine 5-Klicken, zum Beispiel. Gab noch andere Objekte, die es nicht geben kann. Dann das gepaart mit der Anzahl der Knoten zu der Anzahl der Kanten sollte Dich zu einer Lösung bringen.
--
Gruß
Matthias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:45 Di 01.08.2006 | | Autor: | mond |
danke fuer die Hilfe
Ich moechte wissen ist Teil a so richtig
wenn G keinen Kreis enthaelt, so ist G bereit ein Baum ( kreisfrei und zusammenhaenged)
wenn G ist ein Baum, dann e ist ein Blatter
dann [mm] G1=G\e [/mm] ist nicht yusammenhaengd weil wenn wir e loeschen dann gibt es kein Kantenzug zwischen ( ve-1,ve)
dann G1 nicht zusammenhaenged ist.
Nun enthaelt G einen Kreis k, e ist die Kante die von G1 geloescht hat.
Da k ein Kreis ist, werden die Enfknoten von e durch G1 verbunden. Daher ist G1 immer noch yusammenhaenged.
|
|
|
| |
|
Hallo,
also es ist sehr schwer Dir zu folgen. Ja wenn ein Graph kreisfrei und zusammenhängend ist, dann ist es ein Baum modulo Richtung der Kanten. Eine Kante entfernen führt dazu, dass es dann kein zusammenhängender Graph. Formal müsstest Du jetzt noch beweisen, dass jeder kreisfreie zusammenhängende Graph einem Baum (module Richtung der Kanten) entspricht.
--
Gruß
Matthias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:06 Mi 02.08.2006 | | Autor: | mond |
für b habe ich nue knoten una kanten Anzahl.
und 8 Dreieckig
und als Satz habe ich
n-m+f=2 in Planar Graphen
20-40+f=2
dann f die Anzahl von Faces ist 22 .f=22
wie kann ich weiter gehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:46 Mi 02.08.2006 | | Autor: | felixf |
Hallo mond!
> für b habe ich nue knoten una kanten Anzahl.
> und 8 Dreieckig
> und als Satz habe ich
> n-m+f=2 in Planar Graphen
> 20-40+f=2
> dann f die Anzahl von Faces ist 22 .f=22
> wie kann ich weiter gehen?
Das ist schonmal ein guter Anfang. Sei $F$ die Menge aller Faces, und zu jedem $f [mm] \in [/mm] F$ sei [mm] $\deg [/mm] f$ die Anzahl der Ecken (was gleich der Anzahl von Kanten ist, die zum Face gehoeren). Dann ist naemlich [mm] $\sum_{f \in F} \deg [/mm] f = 2 m$ (da jede Ecke zu genau zwei Faces gehoert). Nun ist $2 m = 2 [mm] \cdot [/mm] 40 = 80$.
Beachte, dass ein Face $f [mm] \in [/mm] F$ genau dann ein Dreieck ist, wenn [mm] $\deg [/mm] f = 3$ ist.
Sei $d$ nun die Anzahl der Dreiecke. Dann ist [mm] $\sum_{f \in F} \deg [/mm] f = [mm] \sum_{f \in F \atop \deg f > 3} \deg [/mm] f + d [mm] \cdot [/mm] 3 [mm] \ge \sum_{f \in F \atop \deg f > 3} [/mm] 4 + d [mm] \cdot [/mm] 3 = (22 - d) [mm] \cdot [/mm] 4 + d [mm] \cdot [/mm] 3 = 22 [mm] \cdot [/mm] 4 - d$.
Wenn also $d < 8$ ist, dann ist [mm] $\sum_{f \in F} \deg [/mm] f [mm] \ge [/mm] 88 - d > 80$, ein Widerspruch. Also muss $d [mm] \ge [/mm] 8$ sein, es muss also mindestens acht Dreiecke geben!
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:16 Mi 09.08.2006 | | Autor: | mathiash |
Moin zusammen,
da nichts anderes erwähnt ist, sollte man davon ausgehen, dass es sich um einen ungerichtetetn Graphen handelt.
Jedenfalls ist die Sprechweise ''modulo Richtung der Kanten'' unüblich.
Ansonsten frohes Schaffen wünscht
Mathias
|
|
|
|
