graf lub jego dopełnienie jest grafem spójnym- dowód

[lilith123]

Wykazać, że dla każdego grafu albo on sam albo jego dopełnienie jest grafem spójny

[Dasio11]

Załóżmy, że graf \(\displaystyle{ G = (V, E)}\) nie jest spójny. Wtedy zbiór wierzchołków \(\displaystyle{ V}\) da się podzielić na dwa niepuste, rozłączne podzbiory \(\displaystyle{ V = A \cup B}\), takie że żaden wierzchołek z \(\displaystyle{ A}\) nie jest połączony z żadnym wierzchołkiem z \(\displaystyle{ B}\). Wykaż, że w tej sytuacji dopełnienie \(\displaystyle{ G}\) jest grafem spójnym.

[lilith123]

Czy powinnam skorzystać z własności \(\displaystyle{ (A\cup B)'}\) czy w inny sposób? niestety nadal nie widzę jak wykazać że dopełnienie \(\displaystyle{ G}\) jest grafem spójnym

[Dasio11]

Skoro graf \(\displaystyle{ G}\) ma taką własność, że żadna krawędź nie łączy wierzchołka w zbiorze \(\displaystyle{ A}\) z wierzchołkiem w zbiorze \(\displaystyle{ B}\), to jaką własność ma dopełnienie grafu \(\displaystyle{ G}\)?

[lilith123]

Łączy wierzchołek A z wierzchołkiem B

[Dasio11]

Nie. Wiesz czym jest dopełnienie grafu?

[lilith123]

Tak,

dopełnieniem grafu \(\displaystyle{ G}\) nazywamy graf \(\displaystyle{ G'}\) zawierający te same wierzchołki co graf \(\displaystyle{ G}\) natomiast pomiędzy wierzchołkami grafu \(\displaystyle{ G'}\) istnieje krawędź wtedy i tylko wtedy, gdy pomiędzy tymi wierzchołkami nie istnieje krawędź w grafie \(\displaystyle{ G}\).

[Dasio11]

W takim razie skoro dla każdego wierzchołka \(\displaystyle{ u \in A}\) i każdego wierzchołka \(\displaystyle{ v \in B}\) w grafie \(\displaystyle{ G}\) nie ma krawędzi łączącej \(\displaystyle{ u}\) z \(\displaystyle{ v}\), to jaką własność ma dopełnienie grafu \(\displaystyle{ G}\)?

[lilith123]

Łączy wierzchołek \(\displaystyle{ u}\) z wierzchołkiem \(\displaystyle{ v}\).

[Dasio11]

Niedobrze, bo piszesz o wierzchołkach \(\displaystyle{ u}\) i \(\displaystyle{ v}\), a nie wiadomo, co to za wierzchołki. Jest różnica w zapisach:

1. Każdy wierzchołek \(\displaystyle{ u \in A}\) ma tę własność, że...
2. Wierzchołek \(\displaystyle{ u}\) ma tę własność, że...

W pierwszym z tych stwierdzeń mówimy po prostu, że każdy wierzchołek ze zbioru \(\displaystyle{ A}\) ma dalej opisaną własność, przy czym od razu nadajemy temu wierzchołkowi nazwę \(\displaystyle{ u}\), żeby dalej móc skutecznie opisać, jaką to on własność powinien mieć. Natomiast drugie stwierdzenie jest bezsensowne, jeśli wcześniej nie określiliśmy, czym jest wierzchołek \(\displaystyle{ u}\), bo próbujemy stwierdzić coś o pojedynczym, ale nie wiadomo którym wierzchołku \(\displaystyle{ u}\), a to nie ma sensu.

Poprawna odpowiedź brzmi: każdy wierzchołek zbioru \(\displaystyle{ A}\) jest połączony z każdym wierzchołkiem zbioru \(\displaystyle{ B}\). Czy potrafisz stąd wywnioskować, że taki graf jest spójny?

Jeśli nie, zbadaj konkretny przykład. Narysuj \(\displaystyle{ 7}\) wierzchołków i podziel je na zbiór \(\displaystyle{ A}\) mający \(\displaystyle{ 5}\) elementów i zbiór \(\displaystyle{ B}\) mający \(\displaystyle{ 2}\) elementy. Potem narysuj krawędzie od każdego wierzchołka zbioru \(\displaystyle{ A}\) do każdego wierzchołka zbioru \(\displaystyle{ B}\) (czyli łącznie \(\displaystyle{ 10}\) krawędzi). Stwierdź, czy taki graf jest spójny i dlaczego, a następnie spróbuj uogólnić tę obserwację.