Knotenzusammenhang < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:58 Mo 22.01.2007 | | Autor: | Bastiane |
Hallo!
Ich habe nur eine kurze Frage. Wenn ein Graph k-knotenzusammen hängend ist, bedeutet das ja, dass man beliebige (k-1) Knoten wegnehmen kann, und der Graph immer noch zusammenhängend ist. Dann ist klar, dass bei einem solchen Graphen jeder Knoten mindestens Grad k haben muss. Aber gilt das auch umgekehrt herum? Wenn jeder Knoten mindestens Grad k hat, ist der Graph dann k-zusammenhängend?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
Halluliod Bastianchen,
nimm zwei knotendisjunkte Cliquen der Größe k, dieser Graph erfullt die Gradbedingung, aber er ist noch nicht mal einfach zusammenhángend.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:51 Di 23.01.2007 | | Autor: | Bastiane |
Lieber Mathias!
Für mich ist ein Graph - wenn nicht extra erwähnt - immer als zusammenhängend gedacht. Gilt die Aussage denn dann?
Viele Grüße
Bastiane
|
|
|
| |
|
Liebe Chris,
leider auch nicht, denn dann kannst Du sowas machen wie zwei Cliquen nehmen und sie an einem Knoten verschmelzen, dieser heisst dann Artikulationspunt, ist also das Knoten-Pendant zu einer Brücke.
Lieben Gruss,
Mathias
|
|
|
|
