Dla podanej sieci...

[mistakers]

Siemka,
jak zabrać się za takie zadanko, co powinienem wiedzieć z teorii bo to zrobić.
Dla podanej sieci przepływów wyznaczyć maksymalny przepływ i minimalny przekrój(V1-źródło, V6-ujście)

i do tego jest tabelka ale, że nie wiem jak ją tu zrobić więc napiszę tak:

V1->V2(4), V1->V3(2)
V2->V3(2), V2->V4(1), V2->V5(2)
V3->V5(3)
V4->V6(4)
V5->V6(3)

[norwimaj]

Powinieneś wiedzieć, co to jest sieć residualna oraz znać twierdzenie o maksymalnym przepływie i minimalnym przekroju. Dobrze jest też wiedzieć, jak na podstawie maksymalnego przepływu można znaleźć minimalny przekrój. Można jako ten przekrój wziąć podział wierzchołków na osiągalne i nieosiągalne ze źródła w sieci residualnej maksymalnego przepływu.

Można takie zadanie rozwiązać stosując jakikolwiek algorytm znajdowania maksymalnego przepływu, chociaż w tym przykładzie można też zgadnąć.

Widać że przekrój \(\displaystyle{ \{V_1,V_2,V_3,V_5\}, \{V_4,V_6\}}\) ma przepustowość \(\displaystyle{ 4}\). Można też wskazać przepływ o wartości \(\displaystyle{ 4}\):
\(\displaystyle{ V_1\overset{2}{\to}V_2\\
V_1\overset{2}{\to}V_3\\
V_2\overset{1}{\to}V_3\\
V_2\overset{1}{\to}V_4\\
V_3\overset{3}{\to}V_5\\
V_4\overset{1}{\to}V_6\\
V_5\overset{3}{\to}V_6}\)