Graf prosty

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kazafin
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 27 maja 2007, o 11:46
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 14 razy

Graf prosty

Post autor: kazafin »

Udowodnij, że jeżeli graf prosty o n wierzchołkach ma więcej niż (n-1)(n-2)/2 krawędzi, to musi on być spójny.
abc666

Graf prosty

Post autor: abc666 »

hint.
\(\displaystyle{ {n \choose 2} = \frac{n(n-1)}{2}}\)
kazafin
Użytkownik
Użytkownik
Posty: 79
Rejestracja: 27 maja 2007, o 11:46
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 14 razy

Graf prosty

Post autor: kazafin »

A czy mógłbyś bardziej to rozwinąć?
Byłbym wdzięczny.
abc666

Graf prosty

Post autor: abc666 »

Chodzi o to że gdy weźmiemy \(\displaystyle{ n-1}\) wierzchołków z tego grafu oraz \(\displaystyle{ {n-1 \choose 2}}\) krawędzi to powstanie graf pełny, zostaje nam tylko jeden wolny wierzchołek oraz co najmniej jedna krawędź więc graf musi być spójny
ODPOWIEDZ