דיאגמת הסה - קומבינטוריקה ותורת הגרפים

[nir9696]

דיאגמת הסה - קומבינטוריקה ותורת הגרפים

היי, בשתי השאלות שצירפתי, בעצם מדובר פחות או יותר באותה שאלה - אחת תוך שימוש בשיקולים קומינטוריים, והשנייה, תוך שימוש בתורת הגרפים.
לגבי השאלה הראשונה, הצלחתי להגיע לתשובה, אך אני רק לא בטוח בהסבר הדרך שפעלתי בה (אני בטוח שהיא נכונה, אבל עדיין...). כלומר, הגעתי לתשובה באמצעות חוקיות שמצאתי ע"י ציור של כמה דיאגרמות הסה, וכך גם כתבתי בתשובה [אולם לא הסברתי מדוע הגרפים מתנהגים על-פי החוקיות הזו]. אני מצרף בתגובה את הפתרון שלי לשאלה הראשונה. האם ההסבר שכתבתי מספיק?

אותו הדבר לגבי השאלה השנייה. אני יודע לומר שדיאגרמת הסה של יחס ההכלה על A הוא k-רגולרי, על-פי שרטוט של דיאגרמות ממש, אבל אין איזשהו הסבר מניח את הדעת למה זה כך (הרי זה קשור לאופי המיוחד של דיאגרמת הסה, אשר בנוי מ"קומות").
לגבי ג' בשאלה השנייה - אני יודע שכתבו שצריך להראות שגרף הוא דו-צדדי ע"י חלוקה של הצמתים לשני צדדים. כלומר חלוקה של הצמתים לשני צדדים לפי "זוגיות" הקומה. אך אותי מעניין האם אפשר להוכיח זאת גם באופן פורמאלי.
חשבתי להניח בשלילה כי קיים בגרף מעגל אי-זוגי, ואז להגיע לסתירה, אבל הסתבכתי...

אשמח לדעתכם ולעזרתכם!

 

[nir9696]

הפתרון של השאלה הראשונה

 

[1ca1]

תשובה

אז קודם כל צריך לנחש את k.
אם תסתכל על הקבוצה הריקה, תקבל שהדרגה צריכה להיות |A|.
עכשיו נוכיח שזה |A|.

בהינתן תת-קבוצה B של A בגודל |B|.
כמה קבוצות יש מעליה וכמה מתחתיה (כמובן שכנות)?
יש לנו |B| שכנות למטה (תבחר איבר ותוריד אותו, וקיבלת תת-קבוצה שכנה מלמטה).
לגבי שכנים למעלה, יש לך |A\B|, כי תבחר איבר מ-A\B ותוסיף ל-B וקיבלת שכן.
סה"כ |A| שכנים.

שיקול פשוט לחישוב - יש V קודקודים, ולכן יש לנו |A|V קשתות (בספירה כפולה).
עכשיו כל קשת מכוסה בדיוק פעמיים (פעם שהיא יוצאת מהשכן למטה ופעם מהשכן למעלה). סה"כ יש לך 0.5|A|V קשתות.
אני משאיר לך לחשב את V.

גרף דו"צ - דרך אחת היא לחלק את הקבוצות שבצד ימין זה תתי-קבוצות מגודל זוגי וצד שמאל זה גודל אי-זוגי.
מההגדרה הקשתות רק חוצות בין הצדדים (כי אם אתה מוסיף או מוריד איבר, אתה משנה את הזוגיות).

 

[nir9696]

תודה רבה! רק

לגבי התשובה שצירפתי לשאלה הראשונה (אשר שם אני לא יכול להיעזר בשיקולים של תורת הגרפים) ה"ניחושים" שלי תקפים, כלומר זיהוי החוקיות לפי דיאגרמות ממש ואז הגעה לנוסחה? או שיש הסבר קומבינטורי מספק יותר?

לגבי מה כתבת על השאלה השנייה, הבנתי וגם כתבתי כפי שאתה מציע בפתח ההודעה. אבל תודה על החידוד לגבי מספר השכנים

 

[1ca1]

אי אפשר לקרוא את מה שצירפת

אבל אם הגעת לאותה נוסחא, אז זה כנראה בסדר.

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

אני אוהב יותר את הפתרון דרך הגרפים.

 

[עריסטו]

אפשר גם באינדוקציה

אם יש לנו את הדיאגרמה של n איברים, איך נבנה ממנה את זו של n+1 איברים? נצייר עוד עותק של דיאגרמת n. נוסיף קשת בין כל קדקוד בדיאגרמה הראשונה לקדקוד המתאים בדיאגרמה השניה. לכל קדקוד בדיאגרמה השניה נוסיף את האיבר n+1.

 

[nir9696]

יש סיכוי

שתוכל להבהיר מה זו הדיאגרמה השניה ומה זו הראשונה ולפרט קצת יותר על האינדוקציה?

 

[nir9696]

הסבר

לא הבנתי כ"כ איך קשורה לפה הכלה והדחה...
ומה זו שרשרת\שרשרת מלאה?

 

[1ca1]

תגובה

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

אתה צודק לגבי הכלה הדחה, מה שהתכוונתי הוא שצריך לספור רק את הקשתות ה"יוצאות מעלה", ולזה צריך קצת להיזהר (כאשר ה"בסיס" שלך קטן ממחצית מאיברי הקבוצה, מצבך טוב ויש יותר קשתות מעלה, כאשר הבסיס דווקא גדול יותר, יש פחות מכך, צריך לעשות את החשבון נכון).

 

[nir9696]

עדיין

לא בטוח שהבנתי מה זה שרשרת (אולי אני מכיר את זה בשם אחר...)\שרשרת עולה...

ממש מצטער

 

[סיגמה535]

שרשראות

אם X היא קבוצה, יחס R על X נקרא יחס סדר (חלקי) אם הוא רפלקסיבי, אנטיסימטרי חלש וטרנזיטיבי (את זה אתה אמור לדעת).

שים לב שלפי ההגדרה הזו, לא בהכרח ניתן להשוות בין כל שני איברים. תת קבוצה של X תקרא שרשרת אם כל שני איברים בה ניתנים להשוואה.
כך, למשל, אם A קבוצה, יחס ההכלה ב P(A) הוא יחס סדר (בדוק זאת).

אם ניקח למשל את A להיות {1,2}, אז הקבוצה {{1},{1,2}} החלקית ל P(A) היא שרשרת. עם זאת, הקבוצה {{1},{2},{1,2}} אינה שרשרת (יש בה איברים שאינם ניתנים להשוואה).

מקווה שזה ברור יותר.

 

[nir9696]

האמת

שהרבה יותר ברור הכרתי את זה תחת השם "סדר מלא" ולא "שרשרת". טוב לדעת!

 

[סיגמה535]

לא מדויק

אם בקבוצה X כל שני איברים ניתנים להשוואה, אז היחס נקרא מלא.
תת קבוצה של X שבה כל שני איברים ניתנים להשוואה נקראת שרשרת.

 

[סיגמה535]

הפתרון שלך נראה נכון.

במקום להשתמש במונח "צירופים" כל כך הרבה, ניתן להשתמש בטיעון פשוט יותר.
עבור כל קבוצה, נספור את הקשתות שיוצאות מהקבוצה "כלפי מטה" (או מעלה, זה יוצא אותו דבר). לכל תת קבוצה של A בת m איברים, יוצאות m קשתות כלפי מטה (מדוע?).
לכן מספר הקשתות הוא:

sum_{m=0}^k {m \cdot {k choose m}

(סכום מ 0 עד k (מספר האיברים ב A) של m כפול ("k מעל m") ).
שזה פחות או יותר מה שאתה הגעת אליו. אני די בטוח (לפי ההנחיות בשאלה) שהפיתוח של הסכום הזה מופיע בספר, ואין צורך לפתחו מחדש.

 

[nir9696]

ממש ממש תודה!

עזרת לי מאוד!