Grafy - podstawowe zadania (5 kobiet i ty do 22) Madzia19: Hej chłopaki, czy moglibyście pomóc mi i moim koleżanką w zadaniach z grafów? W nagrodę postaramy się jakoś odwdzięczyć. Czasu niestety mamy od 20 − 22 dzisiejszego dnia. sendfile.pl/pokaz/215654−−−wyx4 . html Pozdrawiam.

Madzia19: Mamy już takie: 1. 43 2. 3, 4 3. 3, 4 5. 6. 17 7. 8. 9. 10. 11. 12 13. 14. 15.

Madzia19: Pytanie 4: Ile jest ciągów złożonych z m jedynek i n zer (n ›= m), takich że dwie jedynki rozdielone są co najmniej trzema zerami Pytanie 6: W grafie prostym o 7 wierzchołkach, jeden z wierzchołków ma stopień 2. Ile maksymalnie krawędzi może posiadać taki graf? Pytanie 7: Ile jest nieizomorficznych, nieetykietownych grafów o 5 wierzchołkach i 7 krawędziach? Pytanie 8: Pełny graf trójdzielny K50,70,20: 1. jest grafem Eulerowskim, 2. jest trójkolorowalny, 3. jest dwudzielny, 4. jest grafem Hamiltonowskim, Pytanie 9 Jaka jest najmniejsza możliwa liczba krawędzi w grafie 100 wierzchołko− wym o 2 spójnych składowych? Pytanie 10 Który z poniższych grafów, o ile istnieje, może być narysowany jednym pociągnięciem ołówka, tak, że każda krawędź jest rysowana tylko raz? 1. graf z 5 wierzchołkami o stopniach 0, 3, 3, 4, 5, 2. graf o dwóch spójnych składowych, 3. graf Kn,m,k,s gdzie n, m, k, s ›= 4 i n + m + k + s − nieparzyste, 4. graf K100. Pytanie 12: Mamy trzy proste równoległe, na jednej zaznaczono 5 punkty na dru− giej 4 a na trzeciej 3 punkty wybieramy 3 spośród podanych punktów i tworzymy trójkąt, ile różnych trójkątów można uzyskać? Pytanie 13: Ile jest krawędzi w pełnym grafie dwudzielnym K50,51 Pytanie 14: Ile krawędzi w pełnym grafie dwudzielnym K50,51 ma drzewo rozpinające Pytanie 15: Na ile sposobów można pomalować etykietowany graf K3, 2 za pomocą k ›= 5 kolorów