Hey! Mam parę pytań odnośnie grafów i bardzo proszę o pomoc:
1. Czy w multigrafach prawdziwe jest twierdzenie, że zawsze są przynajmniej dwa wierzchołki o tej samym stopniu? (Dla grafów prostych jest prawdziwe, z zasady szufladkowej Dirichleta, ale jak to jest dla multigrafów?)
2. Co to znaczy i jak wykonać takie polecenie: "Scharakteryzuj grafy o maksymalnym stopniu 2"?
3. Pokaż, że dowolne drzewo G, w którym \(\displaystyle{ \Delta(G) \geqslant k, k \geqslant 2}\) ma co najmniej k liści.
4. Jaki można podać przykład grafu, który spełnia warunek Orego, a nie spełnia warunku Diraca?
5. Jak można wykazać, że hamiltonowski graf kubiczny (regularny, każdy wierzchołek stopnia 3) posiada skojarzenie doskonałe?
Z góry wielkie dzięki!
Pytania dotyczące grafów
-
miodzio1988
Pytania dotyczące grafów
Uwilebiam grafy....ehhhhhhhh to co umiem:
1)Nie miałem multigrafow.
2) co to znaczy?? Juz mowie . Musisz podac warunek rownowazny Twojemu stwierdzeniu i go udowodnic.
graf ma maksymalny stopien 2 \(\displaystyle{ \Leftrightarrow...}\)
\(\displaystyle{ ...}\) - musisz napisac warunek
3) się mysli. Pewnie wieczorem podam dowod.
4)Graf \(\displaystyle{ K_{5}}\) . I do tego grafu :
a) na jednej krawędzi stawiasz wierzchołek
b)dodajesz wierzchołek poza ten graf i łączysz go z dwoma dowolnymi wierzchołkami \(\displaystyle{ K_{5}}\)
Jeden z tych grafow powinien byc przykładem
5)w książce Wilsona widziałem dowod tego. Poszukaj
1)Nie miałem multigrafow.
2) co to znaczy?? Juz mowie . Musisz podac warunek rownowazny Twojemu stwierdzeniu i go udowodnic.
graf ma maksymalny stopien 2 \(\displaystyle{ \Leftrightarrow...}\)
\(\displaystyle{ ...}\) - musisz napisac warunek
3) się mysli. Pewnie wieczorem podam dowod.
4)Graf \(\displaystyle{ K_{5}}\) . I do tego grafu :
a) na jednej krawędzi stawiasz wierzchołek
b)dodajesz wierzchołek poza ten graf i łączysz go z dwoma dowolnymi wierzchołkami \(\displaystyle{ K_{5}}\)
Jeden z tych grafow powinien byc przykładem
5)w książce Wilsona widziałem dowod tego. Poszukaj
Pytania dotyczące grafów
1) Nie. Weź dwa wierzchołki, połącz je, a do jednego z nich dodaj pętlę.
3) Indukcyjnie.
Pierwszy krok dla n=k+1. Wtedy to drzewo to graf dwudzielny. Jeden zbiór stanowi pojedynczy wierzchołek (o stopniu k), a drugi zbiór to pozostałe k wierzchołków.
Drugi krok, startujemy od drzewa T na n wierzchołkach. W nim na pewno istnieje jeden liść (gdyby tak nie było, to każdy wierzchołek byłby stopnia co najmniej 2, a wtedy na pewno w drzewie byłby cykl - sprzeczność). Niech v będzie tym wierzchołkiem. maksymalny stopien grafu T-v wynosi k, więc z założenia indukcyjnego w T-v istnieje k wierzchołków. Teraz mamy dwa przypadki:
a) v jest połączony z liściem drzewa T-v. Wtedy w drzewie T jest (k-1) + 1 liści.
b) v nie jest połączony z liściem drzewa T-v. A wtedy w T jest k+1 liści.
ckd.-- 30 maja 2009, o 19:26 --5) Z grafu usuwamy cykl Hamiltona. Wtedy stopień każdego wierzchołka wynosi 1, co implikuje istnienie skojarzenia.
3) Indukcyjnie.
Pierwszy krok dla n=k+1. Wtedy to drzewo to graf dwudzielny. Jeden zbiór stanowi pojedynczy wierzchołek (o stopniu k), a drugi zbiór to pozostałe k wierzchołków.
Drugi krok, startujemy od drzewa T na n wierzchołkach. W nim na pewno istnieje jeden liść (gdyby tak nie było, to każdy wierzchołek byłby stopnia co najmniej 2, a wtedy na pewno w drzewie byłby cykl - sprzeczność). Niech v będzie tym wierzchołkiem. maksymalny stopien grafu T-v wynosi k, więc z założenia indukcyjnego w T-v istnieje k wierzchołków. Teraz mamy dwa przypadki:
a) v jest połączony z liściem drzewa T-v. Wtedy w drzewie T jest (k-1) + 1 liści.
b) v nie jest połączony z liściem drzewa T-v. A wtedy w T jest k+1 liści.
ckd.-- 30 maja 2009, o 19:26 --5) Z grafu usuwamy cykl Hamiltona. Wtedy stopień każdego wierzchołka wynosi 1, co implikuje istnienie skojarzenia.