Grafy, ogolne pojecia
: 13 maja 2011, o 10:48
Czy mógłby mi ktoś pomóc z kilkoma zadaniami? dużo juz się zastanawiam nad nimi i nie moge dość do niczego sensownego:(
Zad1.
Uzasadnić, że w każdym grafie \(\displaystyle{ G}\) istnieje ścieżka długości\(\displaystyle{ δ(G)}\)przy założeniu, że \(\displaystyle{ δ(G) \(\displaystyle{ \ge}\) \(\displaystyle{ 1}\).
Zad2.
Dla danych grafów\(\displaystyle{ G}\)i \(\displaystyle{ H}\)niech graf\(\displaystyle{ G + H}\) oznacza graf taki, że
\(\displaystyle{ V (G + H) = V (G) ∪ V (H)}\), zaś\(\displaystyle{ E(G + H) = E(G) ∪ E(H) ∪ {uw : u ∈ V (G),w ∈ V (H)}}\).Książką\(\displaystyle{ B _{n+2}}\) nazywamy graf \(\displaystyle{ K_{2}+ O_{n}}\)(\(\displaystyle{ O_{n}}\)- graf pusty). Ile wynosi spójność wierzchołkowa \(\displaystyle{ (n \ge 2)}\), a ile krawędziowa dla książki? Ile wynosi jej indeks chromatyczny?
Zad3.
Niech G będzie grafem takim, że\(\displaystyle{ \left| V(G)\right|}\) \(\displaystyle{ [\ge]4}\) oraz między dowolnymi trzema wierzchołkami istnieją przynajmniej dwie krawędzie. Wykazać, że graf G jest hamiltonowski. WSKAZÓWKA: wykorzystać jeden z klasycznych warunków dostatecznych na hamiltonowskość.}\)
Zad1.
Uzasadnić, że w każdym grafie \(\displaystyle{ G}\) istnieje ścieżka długości\(\displaystyle{ δ(G)}\)przy założeniu, że \(\displaystyle{ δ(G) \(\displaystyle{ \ge}\) \(\displaystyle{ 1}\).
Zad2.
Dla danych grafów\(\displaystyle{ G}\)i \(\displaystyle{ H}\)niech graf\(\displaystyle{ G + H}\) oznacza graf taki, że
\(\displaystyle{ V (G + H) = V (G) ∪ V (H)}\), zaś\(\displaystyle{ E(G + H) = E(G) ∪ E(H) ∪ {uw : u ∈ V (G),w ∈ V (H)}}\).Książką\(\displaystyle{ B _{n+2}}\) nazywamy graf \(\displaystyle{ K_{2}+ O_{n}}\)(\(\displaystyle{ O_{n}}\)- graf pusty). Ile wynosi spójność wierzchołkowa \(\displaystyle{ (n \ge 2)}\), a ile krawędziowa dla książki? Ile wynosi jej indeks chromatyczny?
Zad3.
Niech G będzie grafem takim, że\(\displaystyle{ \left| V(G)\right|}\) \(\displaystyle{ [\ge]4}\) oraz między dowolnymi trzema wierzchołkami istnieją przynajmniej dwie krawędzie. Wykazać, że graf G jest hamiltonowski. WSKAZÓWKA: wykorzystać jeden z klasycznych warunków dostatecznych na hamiltonowskość.}\)