Graphentheorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | a) Zeigen Sie: Sind die Knoten v und w eines Graphen durch einen beliebigen Kantenzug
verbindbar, so sind sie sogar durch einen Pfad oder einen leeren Kantenzug verbindbar.
b) Zeigen Sie: Ist V die Knotenmenge eines Graphen G mit |V | = n und
deg(v) > (n/2) − 1 für jedes v Element von V , so ist G zusammenhängend. |
Hallo, ich 2 Beweise führen, nur leider komme ich nicht wirklich weit.
Bei a sehe ich einen Wiederspruch, wie kann man 2 Knoten mit einem leeren Kantenzug verbinden wenn v und w nicht identisch sind?
Zudem soll es auch gleichzeitig sollen aber v und w auch durch einen Pfad verbindbar sein. Dann müssen aber v und w verschieden sein.
Bei b bin ich leider zu keinem Ansatz gekommen.
Vielen Dank Tobias
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:31 Mi 19.04.2006 | | Autor: | Frank05 |
> a) Zeigen Sie: Sind die Knoten v und w eines Graphen durch
> einen beliebigen Kantenzug
> verbindbar, so sind sie sogar durch einen Pfad oder einen
> leeren Kantenzug verbindbar.
>
> b) Zeigen Sie: Ist V die Knotenmenge eines Graphen G mit |V
> | = n und
> deg(v) > (n/2) − 1 für jedes v Element von V , so ist
> G zusammenhängend.
> Hallo, ich 2 Beweise führen, nur leider komme ich nicht
> wirklich weit.
> Bei a sehe ich einen Wiederspruch, wie kann man 2 Knoten
> mit einem leeren Kantenzug verbinden wenn v und w nicht
> identisch sind?
So wie ich einen leeren Kantenzug kenne gar nicht.
> Zudem soll es auch gleichzeitig sollen aber v und w auch
> durch einen Pfad verbindbar sein. Dann müssen aber v und w
> verschieden sein.
Vorsicht: da steht (nicht ganz so) dick und fett ein oder
> Bei b bin ich leider zu keinem Ansatz gekommen.
Versuchs doch mal mit einem Widerspruchsbeweis indem du annimmst, dass der Graph trotz dieser Bedingung nicht zusammenhängend ist. Dann gibt es mind. 2 Zusammenhangskomponenten. Jetzt brauchst du dir nur noch in einer dieser Komponenten einen Knoten ansehen und überlegen, was diese Bedingung in diesem Fall bedeutet, was sehr schnell zum gewünschten Widerspruch führt.
|
|
|
|
