Jak pokazać, że każdy graf prosty zawiera co najmniej \(\displaystyle{ \varepsilon - \nu + \omega}\) różnych cykli. Gdzie \(\displaystyle{ \varepsilon}\) jest liczba krawędzi, \(\displaystyle{ \nu}\) liczbą wierzchołków i \(\displaystyle{ \omega}\) liczbą składowych.
Bardzo proszę o pomoc, wyjaśnienia, z góry dziękuję.
Liczba cykli w grafie prostym
-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Liczba cykli w grafie prostym
Zadanie pokaże ci na grafie spójnym składowe łatwo sobie dodasz
Zmieniam ciut oznaczenia bo tak mi wygodniej:
\(\displaystyle{ z }\)- liczba krawędzi
\(\displaystyle{ n }\)- liczba wierzchołków
\(\displaystyle{ c }\)- liczba cykli
Wzrór w moim przypadku będzie:
Udowodnij, że:
\(\displaystyle{ z-n+1 \le c}\)
Zrobimy to indukcyjnie:
Dla:
\(\displaystyle{ n=1,2,3}\)
Nie będę sprawdzał sam sobie sprawdzisz sprawa jest oczywista...
Założenie indukcyjne zrobimy dla: \(\displaystyle{ n-1}\) , teza do udowodnienia dla \(\displaystyle{ n}\)
Z: \(\displaystyle{ z-(n-1)+1 \le c}\)
T: \(\displaystyle{ z+k-n+1 \le c_{1}}\)
gdzie ka liczba nowych "doszłych" krawędzie w grafie poprzez dołączenie nowego wierzchołka...
\(\displaystyle{ c_{1}}\) - liczba nowych cykli w grafie \(\displaystyle{ n}\)
Dw:
Jak dołożymy nowy punkt a graf ma być spójny to dochodzi np. jedna krawędź i liczba cykli się nie zmienia więc będzie:
\(\displaystyle{ z+1-n+1=z-n+2 \le c_{1}=c}\)
Co jest prawdziwe z założenia indukcyjnego...
Załóżmy teraz , że dodaliśmy jeden nowy wierzchołek i z niego wychodzi \(\displaystyle{ k}\) krawędzi, oczywiście \(\displaystyle{ 1 \le k \le n-1}\)
Wtedy liczba punktów będzie: \(\displaystyle{ n}\), liczba krawędzi:\(\displaystyle{ z+k}\), a liczba cykli minimalnie ale musi się zwiększyć przynajmniej o:
\(\displaystyle{ {k \choose 2} }\) - ze zrozumiałych względów...
a więc wystarczy udowodnić, że:
\(\displaystyle{ z+k-n+1 \le c+ {k \choose 2} }\)
przy założeniu, że:
\(\displaystyle{ z-n+2 \le c}\)
Biorąc to pod uwagę otrzymamy:
\(\displaystyle{ z+k-n+1=(z-n+2)+k-1 \le c+k-1}\)
Wystarczy więc udowodnić, że:
\(\displaystyle{ c+k-1 \le c+ {k \choose 2} }\)
lub:
\(\displaystyle{ k-1 \le {k \choose 2} }\)
A jest to jak widać prawda, cnd...
Zmieniam ciut oznaczenia bo tak mi wygodniej:
\(\displaystyle{ z }\)- liczba krawędzi
\(\displaystyle{ n }\)- liczba wierzchołków
\(\displaystyle{ c }\)- liczba cykli
Wzrór w moim przypadku będzie:
Udowodnij, że:
\(\displaystyle{ z-n+1 \le c}\)
Zrobimy to indukcyjnie:
Dla:
\(\displaystyle{ n=1,2,3}\)
Nie będę sprawdzał sam sobie sprawdzisz sprawa jest oczywista...
Założenie indukcyjne zrobimy dla: \(\displaystyle{ n-1}\) , teza do udowodnienia dla \(\displaystyle{ n}\)
Z: \(\displaystyle{ z-(n-1)+1 \le c}\)
T: \(\displaystyle{ z+k-n+1 \le c_{1}}\)
gdzie ka liczba nowych "doszłych" krawędzie w grafie poprzez dołączenie nowego wierzchołka...
\(\displaystyle{ c_{1}}\) - liczba nowych cykli w grafie \(\displaystyle{ n}\)
Dw:
Jak dołożymy nowy punkt a graf ma być spójny to dochodzi np. jedna krawędź i liczba cykli się nie zmienia więc będzie:
\(\displaystyle{ z+1-n+1=z-n+2 \le c_{1}=c}\)
Co jest prawdziwe z założenia indukcyjnego...
Załóżmy teraz , że dodaliśmy jeden nowy wierzchołek i z niego wychodzi \(\displaystyle{ k}\) krawędzi, oczywiście \(\displaystyle{ 1 \le k \le n-1}\)
Wtedy liczba punktów będzie: \(\displaystyle{ n}\), liczba krawędzi:\(\displaystyle{ z+k}\), a liczba cykli minimalnie ale musi się zwiększyć przynajmniej o:
\(\displaystyle{ {k \choose 2} }\) - ze zrozumiałych względów...
a więc wystarczy udowodnić, że:
\(\displaystyle{ z+k-n+1 \le c+ {k \choose 2} }\)
przy założeniu, że:
\(\displaystyle{ z-n+2 \le c}\)
Biorąc to pod uwagę otrzymamy:
\(\displaystyle{ z+k-n+1=(z-n+2)+k-1 \le c+k-1}\)
Wystarczy więc udowodnić, że:
\(\displaystyle{ c+k-1 \le c+ {k \choose 2} }\)
lub:
\(\displaystyle{ k-1 \le {k \choose 2} }\)
A jest to jak widać prawda, cnd...