Pytania dotyczące grafów
: 29 maja 2009, o 20:10
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!
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!