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: 5739
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 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}\)