From 2bb2972f62b45b749ad05b12bfda1d4262057b4e Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 20 Oct 2011 23:37:15 +0200 Subject: [PATCH] Dinicuv algoritmus: Oziveno z historie --- old/2-dinic/2-dinic.tex => 3-dinic/3-dinic.tex | 2 +- {old/2-dinic => 3-dinic}/Makefile | 2 +- {old/2-dinic => 3-dinic}/dinic-cestashranouzpet.eps | 0 {old/2-dinic => 3-dinic}/dinic-cistasit.eps | 0 {old/2-dinic => 3-dinic}/dinic-neprocistenasit.eps | 0 5 files changed, 2 insertions(+), 2 deletions(-) rename old/2-dinic/2-dinic.tex => 3-dinic/3-dinic.tex (99%) rename {old/2-dinic => 3-dinic}/Makefile (68%) rename {old/2-dinic => 3-dinic}/dinic-cestashranouzpet.eps (100%) rename {old/2-dinic => 3-dinic}/dinic-cistasit.eps (100%) rename {old/2-dinic => 3-dinic}/dinic-neprocistenasit.eps (100%) diff --git a/old/2-dinic/2-dinic.tex b/3-dinic/3-dinic.tex similarity index 99% rename from old/2-dinic/2-dinic.tex rename to 3-dinic/3-dinic.tex index 244427c..d451f01 100644 --- a/old/2-dinic/2-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -1,6 +1,6 @@ \input lecnotes.tex -\prednaska{2}{Dinicùv algoritmus}{(zapsala Markéta Popelová)} +\prednaska{3}{Dinicùv algoritmus}{(zapsala Markéta Popelová)} Na~minulé pøedná¹ce jsme si~ukázali Fordùv-Fulkersonùv algoritmus. Tento algoritmus hledal maximální tok tak, ¾e zaèal s~tokem nulovým a~postupnì ho zvìt¹oval. Pro~ka¾dé zvìt¹ení potøeboval v~síti najít cestu, na~které mají v¹echny hrany kladnou rezervu (po takovéto cestì mù¾eme poslat více, ne¾ po~ní aktuálnì teèe). Ukázali jsme, ¾e pokud takováto cesta existuje, jde tok vylep¹it (zvìt¹it). Zároveò pokud tok jde vylep¹it, pak takováto cesta existuje. Dokázali jsme, ¾e pro~racionální kapacity je algoritmus koneèný a~najde maximální tok. diff --git a/old/2-dinic/Makefile b/3-dinic/Makefile similarity index 68% rename from old/2-dinic/Makefile rename to 3-dinic/Makefile index c183fb0..fc07c0a 100644 --- a/old/2-dinic/Makefile +++ b/3-dinic/Makefile @@ -1,3 +1,3 @@ -P=2-dinic +P=3-dinic include ../Makerules diff --git a/old/2-dinic/dinic-cestashranouzpet.eps b/3-dinic/dinic-cestashranouzpet.eps similarity index 100% rename from old/2-dinic/dinic-cestashranouzpet.eps rename to 3-dinic/dinic-cestashranouzpet.eps diff --git a/old/2-dinic/dinic-cistasit.eps b/3-dinic/dinic-cistasit.eps similarity index 100% rename from old/2-dinic/dinic-cistasit.eps rename to 3-dinic/dinic-cistasit.eps diff --git a/old/2-dinic/dinic-neprocistenasit.eps b/3-dinic/dinic-neprocistenasit.eps similarity index 100% rename from old/2-dinic/dinic-neprocistenasit.eps rename to 3-dinic/dinic-neprocistenasit.eps -- 2.39.2