MATeMAtyka 2. Zakres podstawowy i rozszerzony — strona 256
rozdział 5. Planimetria · temat „Problem mostów królewieckich” · 2 zadania z rozwiązaniem
Rozwiązania: opracowanie własne
Zadanie 1
Pokaż rozwiązanieUkryj rozwiązanie
Graf składa się ze zbioru wierzchołków i zbioru krawędzi łączących wybrane pary wierzchołków. Krawędzie mogą być nieskierowane albo skierowane; czasem przypisuje się im też wagi, np. długości dróg. Stopień wierzchołka to liczba krawędzi z nim związanych.
Podstawowe przykłady to ścieżka, cykl, drzewo, graf pełny i graf dwudzielny. Graf jest spójny, jeśli między każdą parą wierzchołków istnieje droga. Grafy opisują m.in. sieci drogowe i komputerowe, relacje społeczne, zależności między zadaniami, połączenia chemiczne i przepływy.
Graf jest matematycznym modelem obiektów i relacji między nimi; tworzą go wierzchołki oraz łączące je krawędzie.
Rozwiązanie: opracowanie własneWeryfikacja: brak w kluczu
Zadanie 2
Pokaż rozwiązanieUkryj rozwiązanie
Graf półeulerowski to spójny graf, który ma drogę przechodzącą przez każdą krawędź dokładnie raz, ale droga ta nie jest zamknięta. Taki graf ma dokładnie dwa wierzchołki nieparzystego stopnia. Spacer Eulera musi zacząć się w jednym z nich i zakończyć w drugim. Pozostałe wierzchołki mają stopnie parzyste. Dla porównania graf eulerowski ma wszystkie stopnie parzyste.
Spójny graf jest półeulerowski wtedy i tylko wtedy, gdy dokładnie dwa jego wierzchołki mają nieparzysty stopień.
Rozwiązanie: opracowanie własneWeryfikacja: brak w kluczu