From a780b7bd16080669f711c3a55ea8dacbd6e27810 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 16 Oct 2014 15:20:23 +0200 Subject: [PATCH] =?utf8?q?Bipcon:=20Oprava=20p=C5=99eklepu?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 3-bipcon/3-bipcon.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 3d4068d..eaa49c9 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -9,7 +9,7 @@ kter \h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}} Nejprve si nadefinujme operaci {\I ¹tìpení grafu,} která zadaný graf $G=(V,E)$ -se v¹emi vrcholy sudého stupnì a sudým poètem hran v~ka¾dé komponentì souvilosti +se v¹emi vrcholy sudého stupnì a sudým poètem hran v~ka¾dé komponentì souvislosti rozlo¾í na~disjunktní podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$, v~nich¾ bude pro ka¾dý vrchol~$v$ platit ${\rm deg}_{G_1}(v) = {\rm deg}_{G_2}(v) = {\rm deg}_G(v)/2$. Tuto operaci mù¾eme snadno -- 2.39.2