Udowodnij spójność grafu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
vtvs
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 11 maja 2008, o 20:00
Płeć: Mężczyzna
Podziękował: 11 razy

Udowodnij spójność grafu

Post autor: vtvs »

Witam.

Do poniższego zadania mam zapisane rozwiązanie, jednak nie wyjaśnia mi ono wszystkiego, dlatego proszę o pomoc.

Udowodnij, że jeśli \(\displaystyle{ e(G)> {{|G|-1} \choose 2}}\), to graf \(\displaystyle{ G}\) jest spójny.

Moje notatki zawierają następujący dowód:
Przypuśćmy, że \(\displaystyle{ e(G)>{{|G|-1} \choose 2}}\), ale graf \(\displaystyle{ G}\) jest niespójny (dowód przez zaprzeczenie).
Jedna składowa ma \(\displaystyle{ k}\) wierzchołków, druga \(\displaystyle{ n - k}\) (cały graf ma \(\displaystyle{ n}\) wierzchołków). \(\displaystyle{ k=1, 2, ..., n-1}\)

\(\displaystyle{ e(G) \le {k \choose 2}+{{n-k} \choose 2}= \frac{k(k-1)}{2} + \frac{(n-k)(n-k-1)}{2}=k^2 - nk + \frac{n(n-1)}{2}}\)

Do tego momentu wszystko rozumiem. Problem zaczyna się tutaj:
dla \(\displaystyle{ k=1}\):
\(\displaystyle{ {1 \choose 2} + {{n-1} \choose 2} = {{n-1} \choose 2}}\)
dla \(\displaystyle{ k=n-1}\):
\(\displaystyle{ {{n-1} \choose 2}+{1 \choose 2}={{n-1} \choose 2}}\)

Widzę, że jest to podstawienie do mojej nierówności \(\displaystyle{ e(G)>{{|G|-1} \choose 2}}\) i oznacza to, że taka sama ilość krawędzi jest wtedy gdy w danej składowej jest 1 lub n-1 wierzchołków, jednak jak to przeczy temu, że graf jest niespójny, nie mogę się domyślić. Proszę o rozjaśnienie umysłu.
Ostatnio zmieniony 17 paź 2011, o 18:26 przez ares41, łącznie zmieniany 1 raz.
Powód: Temat umieszczony w złym dziale.
ODPOWIEDZ