Krawędź wielokrotna w grafie

[hutsalo]

Jak się liczy krawędzie wielokrotne w grafie? Jak jedną całość czy jako dwie odrębne krawędzie? No bo krawędź wielokrotna to krawędź o wspólnym początku i końcu czyli defacto tworze dwie krawędzie, ale te dwie krawędzie są liczone jako jedna całość czy odrębnie?

[3a174ad9764fefcb]

Mówiąc o grafach najczęściej mamy na myśli grafy proste, które opisujemy przez podanie zbioru wierzchołków \(V\) i zbioru krawędzi \(E\subseteq \{\{x,y\}: x,y\in V, x\ne y\}\). Krawędź jest tu dwuelementowym podzbiorem zbioru wierzchołków.

Pewnym uogólnieniem jest graf skierowany. Tam krawędzie definiujemy jako pary uporządkowane: \(E\subseteq V\times V\). Wtedy pomiędzy dwoma wierzchołkami mogą być dwie krawędzie: jedna w jedną stronę, druga w drugą. Jednak tego jeszcze nie nazywamy krawędzią wielokrotną.

W obu powyższych definicjach nie ma miejsca na krawędzie wielokrotne. Żeby mieć krawędzie wielokrotne, musimy mieć inną definicję. Jeden sposób to określenie grafu przez macierz incydencji, której elementami będą dowolne liczby naturalne, zamiast samych zer i jedynek jak w zwykłych grafach. Inny sposób to określenie grafu poprzez funkcję \(f:V\times V\to\mathbb{N}\), która każdej parze wierzchołków przypisuje krotność krawędzi pomiędzy nimi.

Zamiast definiować graf o krawędziach wielokrotnych, można równoważnie użyć zwykłego grafu (powiedzmy że skierowanego) i określić funkcję \(f:E\to\mathbb{N}\). Taką funkcję nazywa się przepustowością, a graf z tak określoną funkcją nazywa się siecią przepływową. W praktyce krawędź podwójna w grafie może oznaczać dwie drogi pomiędzy miastami. Dwie drogi zamieniliśmy tu na jedną drogę o podwójnej przepustowości. Można też określić przepustowości niebędące liczbami naturalnymi, więc podejście z przepustowością jest ogólniejsze od krawędzi wielokrotnych.