Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Podstawowe pojęcia dotyczące sieci przepływowych

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Podstawowe definicje

Sieć przepływowa (ang. flow network) jest spójnym grafem skierowanym G = ( V,  E ) (ang. connected directed graph ), w którego krawędziach odbywa się przepływ ( ang. flow ) jakiegoś czynnika ( wody, gazu, prądu, informacji, towarów, pasażerów itp. ). Przepływ jest możliwy tylko w kierunku zwrotu krawędzi grafu.

W sieci przepływowej wyróżnia się jeden wierzchołek s, z którego wychodzą przepływy - jest to tzw. źródło (ang. source ), oraz jeden wierzchołek t, do którego zbiegają się przepływy - jest to tzw. ujście (ang. sink ). Możemy wyobrazić sobie, iż czynnik przepływający poprzez sieć jest wytwarzany w źródle s, następnie przemieszcza się poprzez krawędzie grafu docierając różnymi drogami do ujścia t, gdzie jest w jakiś sposób odprowadzany.

Z każdą krawędzią grafu ( w terminologii sieci przepływowych krawędzie nazywamy kanałami - ang. chanels) skojarzony jest parametr określający tzw. przepustowość (ang.capacity ), która oznacza maksymalną ilość czynnika mogącego przez tę krawędź przepływać ( tzn. czynnika przepływającego przez kanał może być mniej od jego przepustowości, lecz nigdy więcej ). Przepustowość jest nieujemną funkcją rzeczywistą oznaczaną zwykle przez c ( u, v  ), gdzie u  i v  ∈ V. Jeśli wierzchołki u  i v  są połączone kanałem, czyli ( u, v  ) ∈ E, to przepustowość tego kanału spełnia warunek c ( u, v  ) ≥ 0. Jeśli wierzchołki u  i v  nie są połączone kanałem, czyli ( u, v  ) ∉ E, to c ( u, v  ) = 0. Interpretacja tego faktu jest bardzo prosta - przepustowość odnosi się tylko do istniejących w sieci kanałów. Jeśli kanał nie istnieje, to nie może wystąpić w nim przepływ, zatem jego przepustowość jest zerowa.

obrazek

Na powyższym rysunku przedstawiamy bardzo prosty przykład sieci przepływowej. Jej graf składa się z 5 wierzchołków: źródła s, trzech wierzchołków pośredniczących A, B i C oraz z ujścia t. Czerwonymi strzałkami zaznaczono kierunki przepływów. Granatowe liczby określają przepustowość kanałów. Zwróć uwagę, że w źródle wszystkie przepływy są wychodzące. Podobnie w ujściu wszystkie przepływy są wchodzące.

Przepływ to funkcja rzeczywista o argumentach będących parą wierzchołków grafu, oznaczana zwykle przez f ( u, v  ). Funkcja przepływu musi spełniać trzy warunki:

Ograniczenia przepustowości (ang. capacity constraints )

Dla każdej pary wierzchołków u  i v  ∈ V zachodzi f ( u, v  ) ≤ c ( u, v  ).

Warunek ten mówi, iż przepływ w kanale ( u, v  ) ∈ E nie może przekroczyć jego przepustowości. Zwróć uwagę, iż z warunku tego i własności przepustowości kanału wynika od razu, iż jeśli pomiędzy wierzchołkami u  i v  nie ma kanału, to przepływ f ( u, v  ) = 0, ponieważ c ( u, v  ) = 0.

Skośna symetria ( ang. skew symmetry )

Dla każdej pary wierzchołków u  i v  ∈ V zachodzi f ( u, v  ) = -f ( v, u  ). Warunek ten oznacza, iż przepływ w odwrotnym kierunku jest ujemny. Z warunku tego wynika od razu, iż f ( u, u  ) = -f ( u, u  ) = 0 – przepływ pomiędzy tym samym wierzchołkiem grafu jest zawsze zerowy.

Zachowanie przepływu ( ang. flow conservation )

Dla każdego wierzchołka u  ∈ V – { s, t } suma wszystkich przepływów f ( u, v  ), v  ∈ V, jest równa zero. Warunek ten oznacza, iż suma wszystkich przepływów wpływających do wierzchołka jest równa sumie przepływów wypływających z wierzchołka.

Funkcję f ( u, v  ) nazywamy przepływem netto (ang. net flow) od wierzchołka u  do wierzchołka v. Funkcja ta może przyjmować wartości dodatnie i ujemne.

Przepływ sieci jest definiowany jako suma przepływów netto ze źródła s  do wszystkich pozostałych wierzchołków sieci:

Ponieważ przepływ netto f ( u, v  ) = 0, jeśli pomiędzy wierzchołkami u  i v  nie istnieje kanał, to przepływ sieci można w prosty sposób określić sumując przepływy netto z wierzchołka s  do wszystkich jego sąsiadów, czyli:

Jeśli graf sieci przepływowej będzie reprezentowany w pamięci komputera za pomocą list sąsiedztwa, to wierzchołki sąsiednie znajdziemy bardzo szybko odczytując je po kolei z listy sąsiedztwa wierzchołka s. Takie podejście pozwala przyspieszyć wyliczanie przepływu sieci.

Na początek:  podrozdziału   strony 

Sieć rezydualna

Załóżmy, że mamy daną sieć przepływową w postaci grafu skierowanego G = ( V, E ), przepustowości c ( u, v  ) oraz przepływów f ( u, v  ), gdzie u, v ∈ V. Dla uproszczenia przyjmijmy, iż przepustowości c ( u, v  ) i przepływy f ( u, v  ) posiadają wartości całkowite (wartości wymierne sprowadza się do całkowitych poprzez przemnożenie przez odpowiednio dobrany współczynnik ).

obrazek

W powyższej sieci przepływowej zaznaczyliśmy dla każdego kanału jego przepływ:przepustowość. Na przykład w kanale A-C jest przepływ równy 3, a przepustowość tego kanału wynosi 5.

Przepustowość rezydualna c f ( u, v  ) (ang. residual capacity) danego kanału ( u, v  ) jest równa różnicy przepustowości oraz przepływu w tym kanale:

c f ( u, v  ) = c ( u, v  ) - f ( u, v  )

Ponieważ:

c ( v, u  ) = 0
f
( v, u  ) = - f ( u, v  )

to

c f ( v, u  ) = 0 - ( -f ( u, v  ) ) = f ( u, v  )

Przepustowości rezydualne liczy się również w kierunku przeciwnym, chociaż w sieci może nie występować kanał zwrotny. W takim przypadku, zgodnie z definicją przepustowości i własnością skośnej symetrii przepływu, mamy:

c f ( v, u  ) = c ( v, u  ) - f ( v, u  )

Przepustowość rezydualna w kierunku zgodnym ze zwrotem kanału jest "zapasem" przepływu, który dodatkowo można przez ten kanał przepuścić. W kierunku przeciwnym jest natomiast równa aktualnemu przepływowi w kanale.

Przepustowości rezydualne indukują tzw. sieć rezydualną (ang. residual network ), która zawiera wszystkie wierzchołki oryginalnej sieci przepływowej oraz krawędzie łączące wierzchołki, dla których przepustowość rezydualna jest większa od zera – oznacza to, iż w sieci rezydualnej nie umieszczamy krawędzi pomiędzy wierzchołkami u  i v, jeśli c f ( u, v  ) = 0. Na poniższym rysunku przedstawiamy sieć rezydualną dla przykładowej sieci przepływowej:

obrazek      obrazek

W otrzymanej przez nas sieci rezydualnej każdy kanał pierwotnej sieci przepływowej jest reprezentowany przez dwa przeciwnie skierowane kanały. Ponieważ sieć rezydualna jest zwykle modyfikowana przez różne algorytmy przepływowe, umówmy się, iż dany kanał nie "istnieje" w sieci rezydualnej, jeśli jego przepustowość rezydualna spadnie do 0 – tzn. fizycznie kanał może istnieć, ale nie można już przez niego przepuszczać więcej przepływu – staje się on jakby nieużyteczny, niedrożny. Takie podejście znakomicie ułatwia tworzenie sieci rezydualnej.

Na początek:  podrozdziału   strony 

Sieci przepływowe o wielu źródłach i wielu ujściach

W sieci przepływowej może występować wiele źródeł oraz wiele ujść:

obrazek

Na szczęście taką sieć można w bardzo prosty sposób sprowadzić do sieci z jednym źródłem i z jednym ujściem. W tym celu dodajemy jeden wierzchołek superźródła S oraz jeden wierzchołek superujścia T. Superźródło S łączymy kanałami z poszczególnymi źródłami s 0, s 1, ... Przepustowość kanałów jest sumą przepustowości kanałów wychodzących ze źródeł w pierwotnej sieci. Z kolei poszczególne ujścia t 0, t 1, ... łączymy kanałami z superujściem T. Przepustowości tych kanałów są sumą przepustowości kanałów dochodzących do ujść. Nasza sieć będzie teraz wyglądała następująco:

obrazek

Przepływ sieci jest równy sumie przepływów sieciowych poszczególnych źródeł i jest generowany przez superźródło:

Na początek:  podrozdziału   strony 

Ograniczenie przepływu przez węzeł sieci

Czasami mamy do czynienia z przypadkiem, gdy ograniczony zostaje maksymalny przepływ przez węzeł – np. bez względu na przepustowości autostrad wchodzących do miasta i wychodzących z niego Rada Miejska postanowiła ograniczyć ruch samochodowy przepływający przez miasto (np. ze względu na ochronę zdrowia mieszkańców ). Zatem otrzymujemy sieć przepływową, w której oprócz przepustowości kanałów mamy również przepustowość węzłów. Sieć taką powinniśmy sprowadzić do zwykłej sieci przepływowej, co ułatwi jej przetwarzanie przez algorytmy przepływowe.

obrazek      obrazek

Zadanie rozwiązujemy w bardzo prosty sposób. Węzeł z ograniczeniem przepływu zastępujemy dwoma węzłami. Do pierwszego z nich podłączamy wszystkie kanały wejściowe. Do drugiego węzła podłączamy wszystkie kanały wyjściowe. Następnie oba węzły łączymy kanałem o przepustowości równej maksymalnemu przepływowi dozwolonemu w pierwotnym węźle. W wyniku otrzymujemy zwykłą sieć przepływową.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 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.