Zerlegbarkeit von Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:29 Fr 06.01.2017 | | Autor: | cey112 |
Hallo zusammen,
ich habe den folgenden Graphen und soll zeigen, dass er nicht zerlegbar ist, ohne die Definition:
Ein ungerichteter Graph G ist genau dann zerlegbar, wenn er trianguliert ist.
zu nutzen.
[Dateianhang nicht öffentlich]
Ich wäre jetzt über den Weg der Definition von zerlegbaren Graphen gegangen:
Ein ungerichteter Graph G heißt zerlegbar, wenn er entweder vollständig ist, oder wenn er eine eigentliche Zerlegung (A, B, C) besitzt, für die jeder der beiden durch A ∪ C und B ∪ C aufgespannten Teilgraphen von G wieder zerlegbar ist. Eigentliche Zerlegung bedeutet:
Es sei G=<V,E> ein ungerichteter Graph und V = A ∪ B ∪ C mit paarweise disjunkten Teilmengen (A, B, C). (A, B, C) heißt Zerlegung von G , wenn gilt:
a). C separiert A und B in G ;
b). der durch C beschriebene Teilgraph von G ist vollständig.
Sind A und B beide nichtleer, so wird die Zerlegung (A, B, C) eigentlich genannt.
So: Das mit der vollständigkeit habe ich hinbekommen, aber bei der eigentlichen Zerlegung hab ich Schwierigkeiten. Vielleicht kann mir da jemand helfen.
Ich hätte jetzt versucht, die Knoten so in Mengen zu gruppieren, dass die Menge C, A und B separiert. Meine Idee wäre folgende:
A={A,B,C,D,E}
B={H,I,J,K}
C={G,F}
Damit separiert C doch A und B und ist gleichzeitig auch vollständig. Oder nicht? Aber dann würde das ja bedeuten, dass der Graph G doch zerlegbar ist. Ich werde daraus nicht schlau :(
Vielleicht ist es auch der falsche Weg. ich bin mir nicht sicher.
Wäre super.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:28 So 08.01.2017 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
