8097134157

G7

Jeśli graf jest kliką o rozmiarze n, to ile potrzeba do jego pokolorowania kolorów. Narysuj klikę o rozmiarze 4 i 5. Ile krawędzi ma klika o rozmiarze n.

Pokoloruj następujący graf (dla ułatwienia podwójną linią zaznaczono węzły tworzące klikę):

He kontenerów potrzeba, aby przewieźć wilka (W), gęś (G), kozę (K), marchew (M) i psa myśliwskiego (P). Zakładamy, że w kontenerze nie ma żadnych klatek, ścianek działowych itp. Chcemy zminimalizować liczbę kontenerów i bezpiecznie dowieść dobytek. Jakbyśmy wszystko wpakowali do jednego kontenera, to koza mogłaby zjeść marchew chyba, że wcześniej zjadłby ją wilk, albo pies mógłby zagryźć gęś chyba, że byłby zajęty walką z wilkiem, albo ... Rozwiąż problem za pomocą kolorowania grafu. Jaki wpływ na rozwiązanie problemu ma nasza niewiedza co do zamiarów psa względem kozy? (Może chcieć ją zagryźć albo wskutek dobrej tresury lub respektu przed rogami będzie ją pilnować - różnie to może być.)

rl!!f»WiTQB Dany jest graf reprezentujący pewną mapę z krawędź opisanymi liczbami reprezentujący odległości między miejscowościami: ¹

1

gwiazdką oznaczone są zadania, które nie są realizowane na ćwiczeniach i są przeznaczone do wykonani? jako zadania domowe.