به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
ارسال شده اردیبهشت ۲۱, ۱۴۰۲ در مطالب ریاضی توسط Dana_Sotoudeh (2,124 امتیاز)
ویرایش شده تیر ۷, ۱۴۰۲ توسط Dana_Sotoudeh
620 بازدید

قضیه هال: اگر یک گراف دو بخشی با بخش های $X,Y$ باشد، آنگاه گراف $G$ دارای تطابقی است که همه رئوس $X$ را بپوشاند $ \Leftrightarrow $ شرط هال برقرار باشد($ \forall S \subseteq X; |N(S)| \geq |S|$).

برهان:

لزوم شرط) اگر $M$ تطابق باشد که همه رئوس $X$ را بپوشاند، آنگاه برای هر $ \ S \subseteq X$ باید حداقل به اندازه تعداد اعضای $S$ در $Y$ همسایه وجود داشته باشد. به عبارتی دیگر: $$ \forall S \subseteq X;|N(S)| \geq |S| $$

کفایت شرط) برهان خلف

فرض کنید برای هر $ S \subseteq X $ و $ |N(S)| \geq |S| $ ولی $G$ شامل تطابقی که همه رئوس $X$ را بپوشاند، نباشد.

تطابق $M$ را یک تطابق ماکسیمم در $G$ در نظر میگیریم.

طبق فرض خلف $M$ همه رئوس $X$ را نمی پوشاند. در نتیجه راس $x_0 \in X$ وجود دارد که $M$-ناآلوده است.

مجموعه $Z$ را مجموعه رئوسی در نظر میگیریم که با مسیرهای $M$-متناوب به $x_0 $ در ارتباط اند و قرار می دهیم:

$$ Z \cap X=S , Z \cap Y=T , Z=S \cup T $$

ادعا: $M$ یک تطابق کامل از $T$ به $S- {x_0}$ است و $T=N(S)$

رئوس در $T$ با یال هایی که در $M$ نیست و رئوس $S$ با یال های $M$ به $x_0 $ متصل می شوند.

تطابق $M$ ماکسیمم است $ \Leftarrow $ مسیر $M$-افزوده وجود ندارد. $\Leftarrow$ هر راس در $T$، $M$-آلوده است. پس$T \subseteq N(S) $

عضو دلخواه $y \in N(S) $ $\Leftarrow$ یک مسیر متناوب از $x_0 $ به $y$ وجود دارد. $\Leftarrow$ $y \in T$. پس $T \supseteq N(S) $.

در نتیجه: $$|T|=|N(S)|=|S-{x_0}| =|S|-1< |S| $$ عبارت بالا با فرض قضیه در تناقض است. پس: تطابق ماکزیمم در گراف $G$ وجود دارد که رئوس $X$ را میپوشاند.

توضیحات تصویر

نتیجه قضیه هال: هر گراف دوبخشی $k$-منتظم($k>0 $) دارای تطابق کامل است.

فرض کنید $G$ یک گراف $k$-منتظم دوبخشی با بخش های $X,Y$ باشد.

$ |E(G)|=k|X| , |E(G)|=k|Y| \Rightarrow |X|=|Y|$

هر تطابق که رئوس $X$ را آلوده کند $\Leftarrow$ همه رئوس $Y$ را آلوده می کند. $\Leftarrow$ تطابق کامل است.

حال کافی است ثابت کنیم گراف $G$ در شرط هال صدق می کند.

$$S \subseteq X \Rightarrow $$ $N(S)$تعداد یال های خارج شده از $S$ به =$k|S|$

$N(S)$تعداد یال های خارج شده از =$k|N(S)|$

چون تعداد یال های خارج شده از $N(S)$ ناکمتر از سال های خارج شده از $S$ به $N(S)$ است، پس $ |N(S)| \geq |S|$ و شرط هال برقرار است.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...