Udowodnić, że każdy graf prosty, który ma \(\displaystyle{ n}\) wierzchołków i więcej niż \(\displaystyle{ \frac{(n-1)(n-2)}{2}}\) krawędzi jest grafem spójnym.
Jak za to się zabrać?
Udowodnij że graf jest spójny
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Udowodnij że graf jest spójny
Wsk. Najwięcej "zużyjesz" krawędzi gdy jeden wierzchołek izolujesz a z pozostałych \(\displaystyle{ n-1}\)
zrobisz graf pełny i policz ile będzie miał krawędzi a dodatkowo nie będzie spójny...
Maximum funkcji:
\(\displaystyle{ f(x)= {x \choose 2}+ {n-x \choose 2} , x \in \left\langle 1;\left[ \frac{n}{2} \right] \right\rangle}\)
jest dla:
\(\displaystyle{ x=1}\)
zrobisz graf pełny i policz ile będzie miał krawędzi a dodatkowo nie będzie spójny...
Maximum funkcji:
\(\displaystyle{ f(x)= {x \choose 2}+ {n-x \choose 2} , x \in \left\langle 1;\left[ \frac{n}{2} \right] \right\rangle}\)
jest dla:
\(\displaystyle{ x=1}\)