Ist Graph verbunden? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:25 Do 11.02.2010 | | Autor: | Wimme |
| Aufgabe | Nimm einen Graph mit 8 Knoten, 4 von diesen Knoten haben Rang 2 (soll heißen hat 2 Nachbarn) die anderen 4 haben Rang 1. Ist dieser Graph verbunden?
|
Hallo!
Meiner Meinung nach ist es unter den gegebenen Voraussetzungen unmöglich den Graph zu verbinden.
Ich versuche mal zu erklären wieso:
Die 4 Knoten mit Rang 1 können nur mit jeweils einem verschiedenen Knoten von Rang 2 verbunden werden, so dass man 4 Komponenten erhält. (verbindet man 2 Knoten mit Rang 1 hat man auf jeden Fall eine seperate Komponente. Verbindet man 2 Knoten von Rang 1 mit einem von Rang 2 gilt dasselbe).
Verbindet man nun jeweils 2 dieser 4 Komponenten erhält man 2 Komponenten, bei denen alle Knoten bereits ihren vollen Rang erfüllt haben.
Eine zusätzliche Kante würde einen weiteren Rang 2 Knoten bedeuten oder aber einen Knoten von Rang 3.
Ist das so nachvollziehbar? Wie schreibe ich sowas schön auf? ;)
Dankesehr,
Wimme
|
|
| |
|
> Nimm einen Graph mit 8 Knoten, 4 von diesen Knoten haben
> Rang 2 (soll heißen hat 2 Nachbarn) die anderen 4 haben
> Rang 1. Ist dieser Graph verbunden?
>
>
> Hallo!
>
> Meiner Meinung nach ist es unter den gegebenen
> Voraussetzungen unmöglich den Graph zu verbinden.
> Ich versuche mal zu erklären wieso:
>
> Die 4 Knoten mit Rang 1 können nur mit jeweils einem
> verschiedenen Knoten von Rang 2 verbunden werden, so dass
> man 4 Komponenten erhält. (verbindet man 2 Knoten mit Rang
> 1 hat man auf jeden Fall eine seperate Komponente.
> Verbindet man 2 Knoten von Rang 1 mit einem von Rang 2 gilt
> dasselbe).
>
> Verbindet man nun jeweils 2 dieser 4 Komponenten erhält
> man 2 Komponenten, bei denen alle Knoten bereits ihren
> vollen Rang erfüllt haben.
> Eine zusätzliche Kante würde einen weiteren Rang 2
> Knoten bedeuten oder aber einen Knoten von Rang 3.
>
>
> Ist das so nachvollziehbar? Wie schreibe ich sowas schön
> auf? ;)
>
> Dankesehr,
> Wimme
Hallo Wimme,
Dein Lösungsweg ist nachvollziehbar und meiner Meinung nach richtig. Wie Du diese Lösung in eine besonders gute Form bringst, das weiß ich auch nicht so genau. Ich würde vermutlich die Knoten durchnummerieren und sagen, dass die ersten vier nur Rang eins haben...(?)
Ich kann Dir aber eine Alternative anbieten: Man kann relativ leicht zeigen, dass ein zusammenhängender Graph mit acht Knoten mindestens eine bestimmte Kantenzahl hat. Füge einfach nacheinander Knoten in den Graphen ein und sorge dann immer dafür, dass der Graph mit jedem weiteren Knoten immer noch zusammenhängend ist.
Die so ermittelte Kantenzahl passt nicht zu dem Graphen in Deiner Aufgabe.
Ich lenke Deine Aufmerksamkeit auf diesen anderen Lösungsweg, weil ich glaube, dass man ihn viel leichter aufschreiben kann.
viele Grüße vom Kalkulator
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:02 So 14.02.2010 | | Autor: | Wimme |
Hallo kalkulator!
Also ich würde behaupten ein Graph mit 8 Knoten braucht mindestens 7 Kanten um verbunden zu sein.
Ein Graph der 4 Knoten mit Rang 2 und 4 Knoten mit Rang 1 hat, hat aber nur 6 Kanten, weil jede Kante im Rang ja doppelt gezählt wird.
Daraus folgt, dass der Graph nicht verbunden sein kann.
So meinst du das etwa?
|
|
|
| |
|
> Hallo kalkulator!
>
> Also ich würde behaupten ein Graph mit 8 Knoten braucht
> mindestens 7 Kanten um verbunden zu sein.
>
> Ein Graph der 4 Knoten mit Rang 2 und 4 Knoten mit Rang 1
> hat, hat aber nur 6 Kanten, weil jede Kante im Rang ja
> doppelt gezählt wird.
>
> Daraus folgt, dass der Graph nicht verbunden sein kann.
>
> So meinst du das etwa?
Hallo Wimme,
wie kalkulator das ganz genau gemeint hat, weiß ich nicht,
aber dein Lösungsweg ist so richtig.
Übrigens denke ich, dass man die Struktur des vorliegenden
Graphen vollständig (bis auf Isomorphie) beschreiben kann.
Er muss wohl aus einem "Vierer-Ring" und zwei "Hanteln"
bestehen und ist also offensichtlich nicht verbunden.
LG Al-Chw.
|
|
|
| |
|
Jo, genauso hab' ich mir das auch gedacht.
viele Grüße von Andreas .
(Tarnname is doch vielleicht n' bischen reingesteigert)
|
|
|
|
