"שידוך מלא" ו-"שידוך"

[lalal6]

"שידוך מלא" ו-"שידוך"

שלום,

הגדירו לי באחת מההרצאות בתורת הגרפים את המושגים "שידוך" ו"שידוך מלא" כך:

שידוך:

יהא zz G=(V,E) zz גרף פשוט וסופי.
שידוך ב-G הוא התאמה פונקציה חח"ע ועל בין 2 קבוצות זרות של קדקדים A,B כך שבין כל שניי קדקדים מתאימים יש צלע. (אם A איחוד B שווה ל-V, אז השידוך ייקרא "מושלם").


שידוך מלא:

יהא G גרף שצדדיו V1, V2.
שידוך מלא מ-V1 ל-V2, הוא פונקציה חח"ע מ-V1 ל-V2, כך שבין כל 2 קדקדים מתאימים יש צלע בגרף.

השאלה שלי היא האם בהינתן גרף דו צדדי כלשהו, מותר לי לומר שבמידה ויש שידוך מלא f, אז f היא שידוך?

אני שואל את זה כי זה רלוונטי לי להוכחה של משפט הול שניתנה בהרצאה.

מצורפת כאן ההוכחה (שורה 3 בהוכחה, זה בדיוק מה שאני שואל).

ההוכחה היא בעמוד 4 בלינק הזה:

http://math-wiki.com/images/6/69/GT.L9.pdf

תודה רבה לעונים!!!!

 

[אורי769]

כן

בודאי ששידוך מלא הוא שידוך

 

[lalal6]

בהמשך לאותה שאלה ממקודם

באותה הוכחה...של משפט הול מעמוד 4. מפרידים שם ל-2 מקרים:

מקרה א': לכל תת קבוצה A של V1, מגודל zz |A| = k < m zz מתקיים:

zz |NG(A)| > |A| zz .

כעת מה שלא מובן לי, זה למה אומרים יהי v in V. ל-v לפחות 2 שכנים.

קודם כל, ברגע שאומרים "יהי", הכוונה היא שבהינתן v in V1 כלשהו, ל-v בהכרח יש לפחות 2 שכנים. כלומר לכל v שנבחר, יש לו לפחות 2 שכנים.

למה? למה לכל v in V1 יש לפחות שניי שכנים?

אם ה-v הזה הוא שייך לקבוצה A, אז מאחר ו- zz |NG(A)| > |A| zz אז לפי שובך היונים, קיים לפחות איבר אחד ב-A שיש לו שניי שכנים או יותר (מקווה שמה שכתבתי הרגע מדוייק).
כלומר לא חייב שלכל v ב-A יש שניי שכנים או יותר.

לגבי v-ים ב-V1, שלא שייכים ל-A, מדוע לכל אחד מהם יש 2 שכנים לפחות?



ושאלה נוספת: מדוע במקרה א', כתוב "לכל תת קבוצה A של V1....", בעוד שבמקרה ב' כתוב : "קיימת תת קבוצה A של V1....".??

אודה למי שיוכל לענות על השאלות הללו!

 

[עעעערררר]

ובכן

לשאלה הראשונה: שים לב שאמרו שלכל תת-קבוצה A התנאי מתקיים. אם ניקח את הקבוצה שיש בה רק את הקודקוד v, אז ברור כי |A|=1 , וכן NG(A)zzz היא קבוצת השכנים של v. לכן, יש ל-v לפחות שני שכנים.

לשאלה השנייה: צריך לטפל בכל המקרים. השלילה של "לכל A מתקיים ..." היא "קיים A שעבורו לא מתקיים ..." .
לכן, מכיוון שבמקרה א' הנחנו את הטענה הראשונה, נותר להוכיח כאשר היא לא מתקיימת, כלומר, הטענה השנייה מתקיימת.

 

[lalal6]

אשאל שוב, כי אני די בטוח שלא ענית על שאלותיי

1. מדוע לכל קדקד v in V1, מתקיים של-v יש לפחות 2 שכנים?

2. לגבי החלוקה למקרים. מקרה ב' אינו השלילה של מקרה א' להבנתי.
תנאי הול מדבר על כך שלכל תת קבוצה A של V1 מתקיים : zz |NG(A)| >= |A| zz .

כלומר הוא מדבר על אי שיוויון חלש.

בהפרדה למקרים, להבנתי, הפרידו למקרה שבו האי שיוויון הוא חזק, ולמקרה שבו יש שיויון ממש.

ואז או שכל תת קבוצה של V1 מקיימת אי שיוויון חזק, או שכל תת קבוצה של V1, מקיימת שיוויון ממש.

היכן הטעות שלי?

 

[lalal6]

שוב, מצרף את הלינק.

http://math-wiki.com/images/6/69/GT.L9.pdf

 

[עעעערררר]

ובכן

1. אני יכול להעתיק את התשובה שלי, אך יהיה יותר יעיל אם תפרט מה לא ברור בהסבר שלי.

2. הטעות שלך היא במשפט "או שכל תת קבוצה של V1 מקיימת אי שיוויון חזק, או שכל תת קבוצה של V1, מקיימת שיוויון ממש".
ייתכן שחלק מתתי הקבוצה יקיימו אי שוויון חזק, וחלק יקיימו שוויון.

 

[lalal6]

המשך

מה שלא ברור לי, זה למה שתיקח דווקא את הקבוצה A בגודל 1, שמילה רק את v?

אם למשל תיקח קבוצה A שמכילה 2 איברים: v ו-s.

נניח שקבוצת השכנים שלהם (NG(A היא בגודל 3. אז יתכן של-s יש 2 שכנים, ול-v שכן אחד בלבד, ולא 2 שכנים.


ולגבי ההפרדה למקרים א', ב'.

הם פשוט מוכיחים שם פעם אחת עבור קבוצות שמקיימות אי שיוויון חזק (מקרה א'), ופעם שנייה עבור קבוצות שמקיימות שיוויון (מקרה ב')?

 

[lalal6]

מחדד את השאלה הראשונה

לכל תת קבוצה A של V1 מתקיים: zz |NG(A)| > |A| zz .


בהוכחה כתוב : "יהי v in V1. יש ל-v לפחות 2 שכנים".

מה שאני טוען, זה שלא בהכרח לכל איבר v ב-V1 יש לפחות 2 שכנים. למשל, הדוגמה שנתתי בפוסט הקודם:

תת קבוצה A של V1 בת 2 איברים v,s. כך ש- zz |NG(A)| = 3 > |A| = 2 zz

נניח של-s שניי שכנים. אז ל-v שכן אחד בדיוק. ולכן לא נכון שלכל v in V1 יש ל-v לפחות 2 שכנים, לא?

 

[עעעערררר]

אבל כתוב "לכל"

אז אני יכול לקחת איזו קבוצה שאני רוצה. ואני רוצה לקחת את הקבוצה שיש בה רק v.
לשאלה "למה", התשובה היא "כי אני יכול, וזה עוזר לי בהמשך".

ולגבי ההפרדה, לא!!!!
הם לא מחלקים לקבוצות עם אי שוויון חזק וקבוצות עם שוויון.
הם מחלקים למקרה שבו כל הקבוצות הן עם אי-שוויון חזק, ולמקרה שבו לא כל הקבוצות כאלה (כלומר, יש קבוצה עם שוויון).

 

[lalal6]

מובן עכשיו. תודה !