גרפים - משפט טורן

[student47]

גרפים - משפט טורן

1. ראשית, אם אפשר קצת מוטיבציה לדבר הזה ובמה בדיוק זה שונה מרמזי? זה נראה לי קצת דומה משום מה..

2. האם יש דימיון/קשר בין המושג "סגור ביחס לתכונה כלשהי", לבין רמזי או לבין טורן?

3. הוכחתי טענה שאומרת שמספר הצלעות המקסימלי בגרף פשוט מסדר n שנמנע מעגלים מאורך אי זוגי, הוא (round down(n^2/4.
עשיתי את זה ע"י כך שגרף ללא מעגלים באורך אי-זוגי הוא גרף דו"צ. ואז המרתי את השאלה המקורית, לשאלה: מה מספר הצלעות המקסימלי
בגרף דו"צ מסדר n, והגעתי לכך שהתשובה היא: (round down(n^2/4.
העניין הוא שראיתי שכתוב שהגרף הפשט מסדר n שנמנע מעגלים מאורך אי זוגי, ועם מספר מקסימלי של צלעות, הוא גרף דו"צ סימטרי (כלומר |V1|=|V2|).
אבל אם n אי זוגי, יוצא שב-V1 יש m קדקדים, וב-V2 יש m+1 קדקדים. כלומר הגודל של V1 ושל V2 לא שווה. יכול להיות שיש אצלי טעות? או שהטענה המודגשת היא פשוט לא נכונה?

4. ההוכחה שמספר הצלעות המקסימלי בגרף פשוט מסדר n שנמנע מעגלים מאורך אי זוגי, הוא (round down(n^2/4, לא מוכיחה גם את המקרה הפרטי
של משפט טורן? הרי המקרה הפרטי של משפט טורן, אומר ש: (ex(n,K3)=round down (n^2/4.
K3 זה גרף מלא מסדר 3. שזה משולש בעצם.
משולש הוא מעגל מאורך אי זוגי. אז מדוע ההוכחה שמספר הצלעות המקסימלי בגרף פשוט מסדר n שנמנע מעגלים מאורך אי זוגי הוא
(round down(n^2/4, לא מוכיחה את המקרה הפרטי של משפט טורן (שאומר שהגרף הפשוט המירבי מסדר n, שנמנע משולשים
הוא בעל (round down(n^2/4 צלעות)?

5. ממש בהמשך ישיר לשאלה 4, אצלי כתוב שעל מנת להוכיח את המקרה הפרטי של משפט טורן (שמודגש בשאלה הקודמת), מספיק להוכיח את הטענת עזר הבאה:
לכל גרף ללא משולשים G פשוט מסדר n, קיים גרף דו"צ פשוט H מאותו סדר שמס' צלעותיו מקיים: zz |E(H)| >= |E(G)| zz.

אני מצרף לינק של ההוכחה שנתנו למקרה הפרטי של משפט טורן:

http://math-wiki.com/images/2/24/GT.L10.pdf

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

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

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

 

[ןן גיל ןן]

ראית את תשובתי בעמוד הקודם?

 

[student47]

עכשיו ראיתי..אבל

קודם כל ענית על שאלה אחת מבין השאלות ששאלתי.

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

האמת שלא הבנתי את התשובה שלך אני חושב.

שוב אסביר מה לא מובן לי:

המקרה הפרטי של משפט טורן אומר: מספר הצלעות המקסימלי בגרף פשוט G מסד n שנמנע מעגלים באורך 3, הוא zz round down(n^2/4) zz

כעת, אם הוכחתי שמספר הצלעות המקסימלי בגרף פשוט מסדר n שנמנע מעגלים מאורך אי זוגי (ולכן בפרט נמנע מעגלים מאורך 3), הוא
zz round down (n^2/4)zz , אז למה זה לא מוכיח את הטענה המודגשת (המקרה הפרטי של משפט טורן).
הרי המקרה הפרטי של משפט טורן מדבר על מעגלים ספציפים..כאלה מאורך 3. והטענה כאן מדברת על מעגלים מאורך אי זוגי.
למה הטענה הזו היא לא הכללה של הטענה המודגשת?

תודה על התייחסותך.

 

[1ca1]

אם הוא נמנע ממעגלים מאורך 3, אין זה אומר שהוא נמנע ממעגלים

באורך גדול יותר, כגון 5 או 7. הרי כל העניין במעגל מאורך גדול יותר זה שהוא "לא מכיל בשום צורה" מעגל באורך קטן יותר.
אתה צודק שהכתיבה שם מחורבנת בסימון שלה (F באר?), אבל אם תסתכל על הדוגמא הקודמת, מדובר על גרף שלא מכיל מעגלים בכלל, ואז הסיקו שזה עץ. כלומר הכוונה בדוגמא הפשוטה - אין מעגלים אי-זוגיים בכלל.
&nbsp
ההוכחה ה"פשוטה" שלך אומרת שאתה לא מכיל אף מעגל שהוא, אז אתה לכל היותר n^2/4 צלעות. סבבה.
עכשיו מי אמר שאותו חסם מתאים אם נתון שאתה רק לא מכיל מעגלים מאורך 3? לכאורה הייתי יכול לקבל גרף גדול יותר.
&nbsp
נ.ב. גם אם לכאורה זו היתה הוכחה פשוטה, כשקוראים למשהו במתמטיקה משפט, זה אומר שיש שם הוכחה לא טריוויאלית.
ישנם משפטים מאוד מאוד קשים במתמטיקה, שלמקרים פרטיים שלהם יש הוכחות פשוטות (אולי הדוגמא המפורסמת ביותר היא המשפט האחרון של פרמה ו-n=3,4 למשל).
בד"כ כשאתה רואה בספר הוכחה של משהו, ואז עוברים למשפט חדש ומראים הוכחה של מקרה פרטי של המשפט החדש, שייתכן והיה אפשר להסיק אותה ביתר קלות בצורה אחרת אבל עדיין הראו את ההוכחה, לרוב יש מחשבה מאחורי סדר ההצגה, ולרוב ישתמשו במקרה הפרטי, או שיכלילו את דרך ההוכחה שלו למקרה הכללי, למרות שלכאורה למקרה הפרטי בלבד היתה דרך קיצור.
בקיצור, מאחר שהחפירה התארכה, אם מציגים לך הוכחות שונות לאותו הדבר (שזה לא המקרה המדובר כאן, עד כמה שאני מבין, עדיף ללמוד מספר מקצועי ד"א), לרוב הן יביואו ללמד אותך שיטות או דרכי חשיבה, וחשוב לדעת אותן.
למשל, אם תלמד בעתיד תחום שנקרא תורת החבורות, יש שם משפט (מיוחס לז'ורדן) שאומר ש-A5 (סוג של חבורה) היא פשוטה.
הוכחתי את זה באיזה 3 צורות שונות בתרגול ונתתי אפילו עוד סוג של הוכחה לשיעורי הבית, מאחר שכל הוכחה נתנה את הכיוון שלה למשפט (וזה משפט חשוב, וגם כל הוכחה יכולת להכליל לכיוונים אחרים).

 

[student47]

לא אמרתי שאם הוא נמנע מעגלים מאורך 3 אז הוא נמנע מעגלים

מאורך גדול יותר.
למעשה מה שאמרתי, זה בדיוק הפוך. שאם הוא נמנע מעגלים מאורך אי זוגי, אז בפרט הוא נמנע מעגלים מאורך 3 (כי 3 זה מס' אי זוגי)

 

[1ca1]

אנחנו אומרים את אותו הדבר

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

 

[student47]

תגובה ל-1ca1

יש 3 דברים שאני לא ממש הבנתי עד הסוף.

1. קודם כל, כשאתה משתמש במושג "חסם". אתה מתכוון ל-round down (n^2/4)?
אם כן, אז למה אתה קורא לזה חסם? זה הרי מספר מדוייק לא? זה בדיוק מספר הצלעות המקסימלי בגרף שנמנע מעגלים מאורך אי זוגי.
או שאני לא מבין מה פירוש המושג "חסם", או שיש אצלי איזשהי אי הבנה אחרת.

2. דבר שני, לא ממש ברור לי למה מכך שנמנע מעגלים אי זוגיים גורר נמנע מעגלים מאורך 3, נובע ש"החסם בטורן הפרטי, חוסם מלמעלה את החסם בהוכחה הפשוטה".
האי הבנה אצלי כאן, נובעת להערכתי מכמה דברים: הדבר הראשון, זה בדיוק מה ששאלתי בהתחלה..השימוש במונח חסם לא מובן לי.
הדבר השני, זה שגם בהוכחה של טורן הפרטי, וגם ב"הוכחה הפשוטה" מקבלים בדיוק את אותו מספר צלעות מקסימלי : round down (n^2/4).

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

תודה מראש

 

[1ca1]

תשובות

1. במקרה הזה כן, חסם זה ביטוי שחוסם משהו, כמו כל דבר במתמטיקה.
אתה בעצמך יכול לראות את ההגדרה בדף שאתה עצמך הבאת - מספר הצלעות המקסימלי האפשרי, הרי ברור שגרף שמורכב מקודקודים בלבד ללא צלעות גם מקיים את הטענה, קאפיש?
&nbsp
2. זה שמתקבל אותו המספר לא קשור לשאלה.
הנה שאלה ראשונה - מהו הראשוני המינימלי?
שאלה שנייה - מהו הראשוני הזוגי היחיד?
התשובה לשניהם היא 2, אבל אין קשר בין השניים.
אתה מנסה לקשור תפוחים לתפוזים, אז פרט לעובדה שבשניהם יש תפוח, אין קשר ישיר ביניהם.
&nbsp
3. אוקיי צריך קצת סדר.
נראה לי החפירה שלך כאן על המקרה הפרטי של משפט טוראן הכניסה גם לי וגם לך רעש לעניין.
נמנע ממעגלים אי-זוגיים => נמנע ממעגל מאורך 3.
ולכן אם יש לך חסם, נקרא לו S, על נמנע ממעגל מאורך 3, הוא יחסום גם את נמנע ממעגלים איזוגיים.
הדבר המפתיע כאן (שקורא רק במקרה של אורך 3, אם אתה מכיר את משפט טוראן הפרטי), שאותו חסם S, שווה בדיוק לחסם של נמנע ממעגלים איזוגיים. אז אתה צודק שאין כאן כיוון שני (כי אין כאן טענה אמ"מ).

 

[1ca1]

על מנת לפשט את הדברים

תקרא על משפט טוראן בויקיפדיה, ותראה מה אתה מקבל עבור מעגלים באורך 5, ותראה שזה ביטוי שונה.
אין צורך להתפס לאותו ביטוי, אני בטוח שאפשר לחשוב על עוד מיליארד שאלות בקומבינטוריקה שהתשובה להם היא round(n^2/4), חלקם קשורות לנושא האקסטרמלי הזה וחלקן לא.

 

[student47]

תודה