From 3c7cfac598bf4f9182df3accbb73fc8e0643dca5 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 30 Jan 2007 16:59:41 +0100 Subject: [PATCH] Degree Split vyzaduje, aby graf mel sudy pocet hran, coz samozrejme regularni bipartitni grafy splnuji. --- 3-bipcon/3-bipcon.tex | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index eb96fa3..497e179 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -9,13 +9,14 @@ kter \h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}} Nejprve si nadefinujme operaci {\I Degree Split,} která dostane jako vstup libovolný -$2k$-regulární graf $G=(V,E)$ a rozdìlí ho na~podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$, které budou +$2k$-regulární graf $G=(V,E)$ se sudým poètem hran a rozdìlí ho na~podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$, které budou oba $k$-regulární. Tuto operaci mù¾eme snadno provést v~lineárním èase tak, ¾e si graf rozdìlíme na~komponenty, v~ka¾dé nalezneme eulerovský tah a jeho sudé hrany dáme do~$G_1$ a liché do~$G_2$. To nám pomù¾e ke~snadnému algoritmu pro nalezení maximálního párování ve~$2^d$-regulárním -bipartitním grafu.\foot{V¹imnìte si, ¾e takové párování bude v¾dy perfektní (viz Hallova vìta).} +bipartitním grafu.\foot{V¹imnìte si, ¾e takové párování bude v¾dy perfektní (viz Hallova vìta), +a ¾e takový graf má v¾dy sudý poèet hran.} Staèí provést Degree Split na~dva $2^{d-1}$-regulární grafy, na~libovolný jeden z~nich aplikovat dal¹í Degree Split atd., a¾ se dostaneme k~$1$-regulárnímu grafu, který je perfektním párováním v~$G$. To v¹e jsme schopni stihnout v~lineárním èase, -- 2.39.2