שאלה בגרפים

[student47]

שאלה בגרפים

A קבוצת קשתות שולטת במעגלים בעלת גודל מינימלי בגרף (G=(V,E אם"ם E-A עץ פורש של G

אני מנסה להוכיח את הכיוון מימין לשמאל.

נגדיר T = E-A
ב-T אין מעגלים כי אם היה מעגל ב-T אז אף אחת מהקשתות שלו לא הייתה ב-A. סתירה לכך ש-A שולטת במעגלים.

מדוע T פורש את G? חשבתי אולי לנסות להוכיח בשלילה..להגיד שנניח ש-T לא פורש את G.
לכן קיים (v in V(G שצלעות T לא נוגעות בו...איך אני יכול להתקדם מכאן בשביל להגיע לסתירה?

 

[student47]

נא לנתעלם מהפוסט הקודם. זו השאלה שלי:

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

כעת אני מעוניין להוכיח ש-A היא קבוצה שולטת מינימלית.
כאן אני קצת תקוע. ניסיתי כך:
נניח בשלילה ש-A קבוצה שולטת שאינה מינימלית. אזי קיים מעגל C ב-G כך שיש בו לפחות 2 צלעות ששייכות ל-A.

אבל זה מוזר...כי אם אני לוקח גרף כזה: 3 מעגלים: מעגל A, מעגל B ומעגל C, כך של-A ול-B יש צלע אחת בדיוק (e1) משותפת ול-A ול-C יש צלע אחת בדיוק (e2) משותפת, וגם אין צלע שמשותפת לשלושת המעגלים.
אז {e1,e2} זו קבוצה שולטת במעגלים מינימלית, וגם A הוא מעגל שיש בו 2 צלעות ששייכות לקבוצה השולטת (e1 ו-e2).

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

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

 

[אורי769]

תשובות

1. לא. הטענה המודגשת אינה מסקנה של מינימליות או אי מיניליות של A.
2.
3. המינימליות של A היא במובן של מינימליות ביחס להכלה. כלומר, כל תת-קבוצה ממש של A אינה שולטת במעגלים.

 

[student47]

ובכן

אז לפיכך, אם אני מניח בשלילה ש-A קבוצה שולטת במעגלים שאינה מינימלית, זה אומר שקיימת תת קבוצה ממש של A ששולטת במעגלים?
אם כן, אז זה אומר שב-A יש קשת (לפחות אחת) ששייכת למעגל C כלשהו (נסמנה (e = (u,v), כך שאם אסיר את e מ-A, תתקבל קבוצה שהיא עדיין שולטת במעגלים. נסמנה 'A.
'A שולטת במעגלים. כלומר היא מתקבלת ע"י הפחתת צלעות של עץ פורש מסוים, מקבוצת צלעות הגרף. מי הם הצלעות של העץ הזה? הצלע e + הצלעות של העץ הפורש T שכשהפחתנו מצלעות הגרף, את צלעות T, קיבלנו את A.
אבל זה לא עץ, כי e סוגרת מעגל בעץ T.

מה שכתבתי פה נכון? או שאני מתבלבל?
אני בכיוון?
אם לא, אשמח להכוונה.

 

[student47]

כלומר אני מקבל סתירה לכך ש

קבוצה שולטת במעגלים מתקבלת מהפחתת צלעותיו של עץ פורש כלשהו, מצלעות הגרף.
כי כאמור, 'A שולטת במעגלים. לכן היא בהכרח מתקבלת מהפחתת צלעותיו של עץ פורש. מי זה העץ הזה? העץ T + הצלע e. כלומר קיבלתי קבוצה שולטת 'A ע"י הפחתת קבוצת צלעות שאינה עץ (כי e סוגרת מעגל בעץ T), מקבוצת צלעות הגרף.

אני צודק?

 

[אורי769]

תשובות

ניכר שאתה אינטואיטיבית מבין את ההוכחה אבל לא מצליח לנסח אותה. גם יש לך כאן טיעון מעגלי. קבוצה שולטת במעגלים מוגדרת ע"י שליטה במעגלים ולא ע"י עצים. לכן הדבר הטבעי הוא קודם כל לעבוד עם הגדרות. הדבר הנוסף שיכול מאד לעזור לך זה לעבוד מסודר. לכתוב במסודר מה נתון ומה צריך להוכיח. אח"כ למלא את מה שביניהם. לעתים הרישום המסודר הזה כשלעצמו הוא חצי מהדרך להוכחה. בא נראה...
נתון: T עץ פורש. A=E-T. צריך להוכיח ש-A קבוצה שולטת במעגלים מינימלית.
את העובדה ש-A שולטת במעגלים הוכחת. נשאר להוכיח מינימליות.
מה זה אומר?
זה אומר שצריך להוכיח שכל A' שהיא חלקית ממש ל-A אינה שולטת במעגלים.
מה זה אומר?
זה אומר שצריך להוכיח שלכל A' שהיא חלקית ממש ל-A קיים מעגל כלשהו C ש-A' לא שולטת עליו.
מה זה אומר?
זה אומר שצריך להוכיח שלכל A' שהיא חלקית ממש ל-A קיים מעגל כלשהו C השייך כולו למשלים של A'.
שים לב שכל מה שכתבתי כאן זה נטו עבודה עם הגדרות. לא הוכחתי שום דבר. עכשיו נוכיח...
ניקח A' שהיא חלקית ממש ל-A. כאמור צריך להוכיח שהמשלים של A' מכיל מעגל. מה אתה אומר.. איך מוכיחים את זה?

 

[student47]

ובכן

A שולטת במעגלים, ולכן A מתקבלת מהסרת צלעות עץ פורש T מקבוצת צלעות G.

'A תתקבל מהסרת צלעות אותו עץ פורש (T), ומהסרת הצלעות ב-A שאינן ב-'A. (יש לפחות אחד כזו, כי 'A חלקית ממש ל-A).

כלומר קבוצת הצלעות המוסרות מ-G, שלאחר הסרתן תתקבל 'A, היא קבוצה שנסמנה ב-B. הקבוצה B שווה למשלים של 'A. כמו כן, B מקיימת:
1. צלעותיה מכילות את צלעות העץ הפורש T של הגרף G.
2. צלעותיה מכילות צלעות (לפחות אחת) של A שאינן ב-'A.

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

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

ותודה רבה על העזרה!

 

[אורי769]

תשובה

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

"A שולטת במעגלים, ולכן A מתקבלת מהסרת צלעות עץ פורש T מקבוצת צלעות G"

למה? אתה הופך כאן את היוצרות. A מתקבלת מהסרת צלעות של עץ פורש T כי ככה היא הוגדרה. זה כתוב שחור על גבי מסך בתגובה הפותחת שלך. A היא שולטת במעגלים כי אתה הוכחת את זה. זה ש-A היא שולטת במעגלים היתה מסקנה של זה שהיא משלימה של עץ פורש T ולא להיפך.

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

 

[student47]

התבלבלתי..צודק תודה רבה לך על העזרה