שאלה על גרפים מישוריים

S

student47

New member

• 22/11/14

• #1

שאלה על גרפים מישוריים

שאלה ראשונה:
למה לא נכון להוכיח שגרף הוא מישורי ע"י כך שאציירו במישור ואראה שלא מתקיים: m<=3n-6?

שאלה שנייה:
למה לכל גרף מישורי G מסדר n עם m צלעות ו-k רכיבי קשירות מתקיים:
לכל שיכון נאות של G, מספר הפאות f מקיים: n-m+f = k+1?

אודה על עזרתכם.

 

א

אורי769

New member

• 23/11/14

• #2

תשובות

1. לא ברור מה אתה שואל. אם אתה מצייר גרף במישור אז הוא כן מישורי. בגרף מישורי אכן מתקיים ש-m<=3n-6. אם אתה מראה ש-m>3n-6 אז הגרף לא מישורי. אבל אז אין צורך לצייר אותו. בקיצור - לא הבנתי.
2. זה אינדוקציה פשוטה על נוסחת אויילר n-m+f=2.

 

S

student47

New member

• 23/11/14

• #3

למה m<=3n-6 זה לא תנאי מספיק למישוריות?

 

א

אורי769

New member

• 23/11/14

• #4

האם אתה מכיר דוגמא לגרף לא מישורי?

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

כעקרון, אין שום סיבה לחשוב שמה שכתבת הוא נכון. לוגית
אם A אז B
לא אומר ש
אם B אז A
במקרה שלנו A = הגרף הוא מישורי. B = הגרף מקיים m=<3n-6.

 

S

student47

New member

• 24/11/14

• #5

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

השאלה הייתה:
לכל גרף מישורי G מסדר n עם m צלעות ו-k רכיבי קשירות מתקיים:
לכל שיכון נאות של G , מספר הפאות f מקיים: n-m+f = k + 1.

אנסה להוכיח:

נסמן ב-m_i את מספר הצלעות ברכיב קשירות ה-i-י כאשר zz 1 <= i <= k zz .
נסמן ב-n_i את מספר הצלעות ברכיב קשירות ה-i-י " " " " " " ".
נסמן ב-f_i את מספר הפאות ברכיב קשירות ה-i-י " " " " " " ".

מתקיים: zz sum (i = 1 to k) m_i = m zz
zz sum (i = 1 to k) n_i = n zz
zz sum (i = 1 to k) f_i = f + k zz
(כי חזרנו על הפאה האינסופית k פעמים).

ממשפט אוילר, בכל רכיב קשירות i, מתקיים: zz n_i - m_i + f_i = 2 zz

אבל יש k רכיבי קשירות ולכן מתקיים: n - m + f + k = 2k (אפשר לומר שכפלנו את השיוויון האחרון ב-k) .

לכן: n - m + f = k

אמור לצאת לי k+1 באגף ימין..

איפה השגיאה אצלי??

תודה מראש !!

 

א

אורי769

New member

• 24/11/14

• #6

יש לך שלוש שגיאות

1) זו לא אינדוקציה (אני מניח ששמת לב)
2) אם n_i-m_i+f_i = 2 לכל i אז בסכום יוצא n-m+f = 2k (התוספת של ה-k אצלך מיותרת). מאידך, גם זה לא התוצאה הרצויה לנו.
3) אם בגרף יש שני רכיבי קשירות G = G1 U G2 אז אכן קודקוד שייך לאחד מרכיבי הקשירות בלבד. גם צלע. אבל מה עם הפאות... הייתכן ששני רכיבי קשירות יחלקו ביניהם פיאה?

 

S

student47

New member

• 24/11/14

• #7

ובכן

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

שניי רכיבי קשירות חולקים את הפאה האינסופית.

 

S

student47

New member

• 24/11/14

• #8

אולי כך...עוד ניסיון

לגרף G יש k רכיבי קשירות. נניח שלכל i בין 1 ל-k כולל, לרכיב Xi יש n_i קדקדים, f_i פאות ו-m_i צלעות.

כל רכיב קשירות X_i הוא גרף קשיר ולכן לפי משפט הפאון של אוילר:
n_i-m_i+f_i = 2.
נחבר את הרכיבי קשירות ע"י k-1 קשתות.

נקבל:
zz (n_1 + n_2 +..+n_k) - (m_1 + m_2 +..+m_k) + (f_1 + f_2 +..+f_k) = 2k zz נסמן שיוויון זה ב-*.

n_1+..+n_k = n
m_1+..+m_k = m
f_1+..+f_k = f + k -1 (האם אני יכול להגיד את זה, ואם כן, איך אי מנמק את זה).

ע"י הצבה ב-*, אני מקבל את השיוויון שביקשו.

אם גם זה לא נכון, אז אני אצטרך כנראה לראות את ההצעה שלך, כי אני לא מצליח .

תודה!

 

א

אורי769

New member

• 24/11/14

• #10

זאת הוכחה קבילה

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

 

S

student47

New member

• 25/11/14

• #11

את הטענה על סכום ה-f_i אני לא מצליח להצדיק

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

לגבי הטענה על סכום ה-f_i...אני לא ממש יודע להסביר אותה : /

 

S

student47

New member

• 25/11/14

• #12

בעצם אולי כך אצדיק:

חיברנו את k רכיבי הקשירות ע"י k-1 צלעות.
ואז מאוילר: zz n1+..+nk - (m1 +..+mk) + (f1+..+fk) = 2k zz
האמת שכשאני חושב על זה עכשיו, השיוויון הזה בכלל לא נכון. למה הוא נכון? הרי חיברתי את k רכיבי הקשירות עם k-1 צלעות.
איפה זה מתבטא בשיוויון הזה? ולמה נכון לומר שצד ימין שווה ל-2k.

לגבי השיוויון: f1+..+fk = f+k-1.
זה נכון כי הסכום בצד ימין כולל את כל הפאות בגרף המקורי G. כלומ את f, ו-f כולל בתוכו גם פאה אינסופית אחת.
כל fi כולל בתוכו גם את הפאה האינסופית של הרכיב קשירות ה-i-י.
סך הכל סכמנו את הפאה האינסופית k פעמים, בצד שמאל, ובצד ימין סכמנו אותה פעם אחת כשהיא כלולה בתוך f, ועוד k. לכן בצד ימין
סכמנו אותה k+1 פעמים, ולכן מפחיתים 1 כדי שיהיה שיוויון במספר הפאות האינסופיות.

נראה לי שהצדקתי את הטענה על ה-fi.
אבל למה הטענה האדומה נכונה?

 

א

אורי769

New member

• 26/11/14

• #13

בא נסתכל על זה קצת אחרת

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

כעת נניח G מישורי עם k רכיבי קשירות. נוסיף k-1 צלעות שיחברו את רכיבי הקשירות ונקבל את גרף H. מה אויילר אומר על H? מה זה אומר על G?

 

א

אורי769

New member

• 24/11/14

• #9

פחות או יותר

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