Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
ProblemW danym grafie należy znaleźć ścieżkę, która przechodzi co najmniej jeden raz przez wszystkie krawędzie i wraca do wierzchołka startowego. |
W roku 1962 chiński matematyk Mei-Ko Kwan zaproponował następujący problem:
Listonosz, roznosząc listy, musi przejść przez wszystkie ulice w swojej dzielnicy co najmniej jeden raz i wrócić na pocztę. Ponieważ jest człowiekiem leniwym (nie odnosi się to do pozostałych listonoszy, tylko do tego konkretnego ), chciałby mieć jak najkrótszą do przejścia trasę. Znalezienie takiej trasy jest problemem, który nazwano problemem chińskiego listonosza (ang. Chinese postman problem - CPP ).
W języku grafów układ ulic to graf nieskierowany (problem z grafem skierowanym może wystąpić wtedy, gdy listonosz jeździ furgonetką pocztową, a część ulic jest jednokierunkowa ) z wagami - każda ulica to krawędź, której waga jest równa długości ulicy. Skrzyżowania ulic to wierzchołki grafu. Poczta jest wierzchołkiem startowym i końcowym. Naszym zadaniem jest znalezienie cyklu wychodzącego z poczty i wracającego do niej po przejściu przez wszystkie krawędzie grafu co najmniej jeden raz i o takiej własności, iż suma wag krawędzi cyklu jest najmniejszą możliwą sumą wag krawędzi wszystkich takich cykli w grafie.
Jeśli graf zawiera cykl Eulera, to rozwiązanie jest bardzo proste - cykl Eulera przechodzi przez każdą krawędź grafu dokładnie jeden raz, zatem suma wag jego krawędzi jest zawsze minimalna.
Jeśli graf nie zawiera cyklu Eulera (trudno żądać, aby architekci budowali ulice zgodnie z regułami grafów Eulera ), to zadanie się komplikuje. Załóżmy, iż w grafie są tylko dwa wierzchołki o nieparzystym stopniu ( wierzchołki F i K ).
Aby graf zawierał cykle Eulera, wszystkie wierzchołki muszą posiadać stopnie parzyste. W celu osiągnięcia tego stanu w grafie dublujemy krawędzie wchodzące w skład ścieżki łączącej wierzchołki o nieparzystych stopniach F i K ( np. ścieżka F–G–L–J–K ):
![]() |
→ |
![]() |
Po tej operacji stopnie wszystkich wierzchołków grafu są parzyste. Stało się tak dlatego, ponieważ do wierzchołków F i K o nieparzystych stopniach dodaliśmy po jednej krawędzi, co spowodowało przejście stopni nieparzystych w parzyste. Do pozostałych wierzchołków ścieżki dodaliśmy po dwie krawędzie (wchodzącą i wychodzącą ), a to nie zmieniło parzystości ich stopni. Graf, w którym krawędzie mogą być dublowane, nazywamy multigrafem.
Teraz multigraf spełnia warunki istnienia cyklu Eulera. W odniesieniu do pierwotnego grafu cykl Eulera przebiegnie przez zdublowane krawędzie dwukrotnie (tymi ulicami nasz listonosz będzie musiał przejść dwa razy ). Cykl znajdziemy za pomocą algorytmu znajdowania cyklu Eulera w spójnym grafie nieskierowanym. Algorytm ten jest już przystosowany do multigrafów. Przygotujmy dane wejściowe. Zastąpimy etykiety literowe (bardziej czytelne dla ludzi) etykietami liczbowymi (mniej czytelne dla ludzi, ale lepsze dla komputera ):
![]() |
12 27 0 1 0 2 0 3 0 4 1 2 1 5 1 6 2 3 2 5 3 4 3 7 4 9 4 10 5 6 5 6 6 7 6 11 6 11 7 8 7 11 8 9 8 10 8 11 9 10 9 10 9 11 9 11 |
Po uruchomieniu programu i wprowadzeniu do niego przygotowanych danych, otrzymujemy wynik następujący (numerki obok krawędzi określają kolejność ich przechodzenia w wyznaczonym cyklu Eulera ):
12 27 0 1 0 2 0 3 0 4 1 2 1 5 1 6 2 3 2 5 3 4 3 7 4 9 4 10 5 6 5 6 6 7 6 11 6 11 7 8 7 11 8 9 8 10 8 11 9 10 9 10 9 11 9 11 EULERIAN CYCLE : 0 4 10 9 11 9 10 8 11 6 11 7 8 9 4 3 7 6 5 6 1 5 2 3 0 2 1 0 |
![]() |
Suma wag krawędzi wchodzących do cyklu Eulera w zmodyfikowanym grafie jest równa sumie wag wszystkich krawędzi pierwotnego grafu powiększonej o sumę wag krawędzi zdublowanych. Oczywistym jest, iż ścieżkę łączącą wierzchołki o nieparzystych stopniach należy dobrać, tak aby suma wag jej krawędzi była najmniejsza ze wszystkich możliwych ścieżek w grafie, które łączą te wierzchołki. Ścieżkę taką możemy bez problemu znaleźć przy pomocy algorytmu Dijkstry.
Jeśli graf zawiera więcej niż dwa wierzchołki o nieparzystych stopniach, problem staje się trudny obliczeniowo. W takim przypadku za pomocą algorytmu Dijkstry musimy wyznaczyć najkrótsze ścieżki pomiędzy wszystkimi tymi wierzchołkami. Istnieje twierdzenie, które mówi, iż liczba wierzchołków o nieparzystych stopniach w grafie spójnym jest zawsze liczbą parzystą. Skoro tak, to wierzchołki możemy połączyć w pary za pomocą znalezionych ścieżek. Problem leży w tym, aby suma wag użytych do połączeń ścieżek była jak najmniejsza. Powód jest prosty - ścieżki te będą dublowane w grafie, aby uzyskać parzyste stopnie wierzchołków. Suma wag ich krawędzi doda się do sumy wag wszystkich krawędzi w grafie. Skoro szukamy najkrótszej trasy, to dublowane ścieżki powinny być najkrótsze z możliwych.
Rozważmy problem kombinatorycznie.
|
Cztery wierzchołki mogą już być połączone na 3 różne sposoby:
|
{A – B, C – D} {A – C, B – D} {A – D, B – C} |
Sześć wierzchołków (pięć nie może wystąpić, gdyż liczba wierzchołków o nieparzystych stopniach jest zawsze parzysta) można połączyć na 15 różnych sposobów:
|
Do wyniku tego dochodzimy następująco: pierwszy wierzchołek A można skojarzyć z dowolnym z pięciu pozostałych wierzchołków B, C, D, E lub F. Otrzymujemy pięć możliwości utworzenia pierwszej pary: A – B, A – C, A – D, A – E i A – F. Po wyborze pierwszej pary pozostają zawsze 4 nieskojarzone wierzchołki, a te można skojarzyć w pary na trzy różne sposoby. Zatem dla każdej z pierwszych par mamy trzy kombinacje pozostałych dwóch par. W wyniku otrzymujemy 5 • 3 = 15 różnych skojarzeń.
Kontynuując to rozumowanie dalej, wyliczamy, iż dla 8 wierzchołków pierwszą parę można wybrać na 7 sposobów, a pozostałe trzy pary na 15 sposobów. Zatem liczba możliwych skojarzeń wynosi 7 • 15 = 105.
Dla 10 wierzchołków otrzymamy: 9 • 105 = 945. Dla 12 wierzchołków otrzymamy: 11 • 945 = 10395 Dla 14 wierzchołków otrzymamy: 13 • 10395 = 135135 Dla k wierzchołków liczba skojarzeń wierzchołków w pary jest równa: S = ( k - 1 ) • ( k - 3 ) • ( k - 5 ) • ... • 7 • 5 • 3 • 1 Jest to iloczyn kolejnych liczb nieparzystych mniejszych niż k: ![]() |
Problem znajdowania skojarzeń par wierzchołków o minimalnych wagach krawędzi rozwiązuje algorytm Edmondsa pracujący w klasie złożoności O ( n 3 ). Jednakże jest on bardzo skomplikowany i wymaga dobrej znajomości teorii grafów oraz programowania liniowego. Dla prostszych przypadków ( k < 20 ) można zaryzykować podejście kombinatoryczne.
K01: Sprawdź, czy graf jest spójny.
Jeśli nie jest,
to zakończ algorytm z odpowiednim komunikatemK02: Wyszukaj w grafie wszystkie wierzchołki
o nieparzystych stopniachK03: Jeśli liczba tych wierzchołków jest równa 0,
to idź do kroku K07K04: Wyznacz za pomocą algorytmu Dijkstry
najkrótsze ścieżki łączące ze sobą wszystkie
znalezione wierzchołki o nieparzystych stopniach.K05: Wyszukaj skojarzenie tych wierzchołków
w pary o najmniejszej sumie wag krawędziK06: Krawędzie wchodzące w skład wyznaczonych
ścieżek skojarzenia zdubluj w grafie wejściowymK07: Wyznacz w grafie cykl Eulera i wyprowadź wynik K08: Zakończ
Podany algorytm jest jedynie szkicem rozwiązania. Aby go efektywnie zaimplementować, należy rozwiązać kilka problemów. Oto niektóre z nich.
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.