הוכחות מתמטיות/מתמטיקה בדידה/בגרף דו צדדי d-רגולרי יש זיווג מושלם

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

קפיצה אל: ניווט, חיפוש

G = (V1,V2,E) גרף דו צדדי d-רגולרי אזי ב \displaystyle G זיווג מושלם.

הוכחה: בכל תת קבוצה S \subset V_1 חלות |S|\,d צלעות. וכן ב \displaystyle \Gamma(S) חלות |\Gamma(S)|\,d צלעות.

מאחר והגרף d-רגולרי, כל צלע שחלה ב \displaystyle S חלה גם ב \displaystyle \Gamma(S)

ולכן כמובן ש \displaystyle |d\,\Gamma(S)| \ge |d\,S| ומאחר ש d מספר טבעי: \displaystyle |\Gamma(S)| \ge |S|


מקור: http://he.wikibooks.org/wiki/%D7%94%D7%95%D7%9B%D7%97%D7%95%D7%AA_%D7%9E%D7%AA%D7%9E%D7%98%D7%99%D7%95%D7%AA/%D7%9E%D7%AA%D7%9E%D7%98%D7%99%D7%A7%D7%94_%D7%91%D7%93%D7%99%D7%93%D7%94/%D7%91%D7%92%D7%A8%D7%A3_%D7%93%D7%95_%D7%A6%D7%93%D7%93%D7%99_d-%D7%A8%D7%92%D7%95%D7%9C%D7%A8%D7%99_%D7%99%D7%A9_%D7%96%D7%99%D7%95%D7%95%D7%92_%D7%9E%D7%95%D7%A9%D7%9C%D7%9D