Grafy, ogolne pojecia

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
marffy
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 15 cze 2010, o 19:12
Płeć: Kobieta
Lokalizacja: Biała Podlaska
Podziękował: 2 razy

Grafy, ogolne pojecia

Post autor: marffy »

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ść.}\)
adek05
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

Grafy, ogolne pojecia

Post autor: adek05 »

Z.1
Zakładam, że chodzi o \(\displaystyle{ \delta(G)}\), co oznacza minimalny stopień wierzchołka w \(\displaystyle{ G}\).
Wtedy robimy następująco: wybieramy dowolny wierzchołek \(\displaystyle{ v}\). Ma on conajmniej \(\displaystyle{ \delta (G)}\) sąsiadów. Wybieramy jednego z nich, np. \(\displaystyle{ u}\). Teraz patrzymy się na sąsiadów \(\displaystyle{ u}\). No on ma ich znowu conajmniej \(\displaystyle{ \delta (G)}\), ale jeden z nich może być już wcześniej na naszej ścieżce, itd.(czytaj indukcja po rozmiarze grafu).
Z.2
Spójność wierzchołkowa, narysuj i wskaż, że wystarczy usunąć dwa.
Spójność krawędziowa, pokaż, że wystarczy usunąć dwie.
Spróbuj pokazać, że indeks chromatyczny wynosi \(\displaystyle{ n+1}\)
Z.3
Chodzi o warunek \(\displaystyle{ deg(v_1) + deg(v_2) \ge n}\). Spróbuj to wykorzystać.
marffy
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 15 cze 2010, o 19:12
Płeć: Kobieta
Lokalizacja: Biała Podlaska
Podziękował: 2 razy

Grafy, ogolne pojecia

Post autor: marffy »

dziękuję:) do 3 zadania mam pytanie bo z tego twierdzenia orego czy nawet diraca widać że ten graf jest hamiltonowski tylko nie bardzo wiem jak to zapisać żeby udowodnić że to prawda
ODPOWIEDZ