קומבינטוריקה - גרפים

[csstud]

יהי G גרף פשוט לא מכוון עם n צמתים ו- m קשתות.

צ"ל שאם m גדול מ (n בריבוע חלקי 4) אז בגרף G יש משולש (כלומר 3 צמתים שכולם מחוברים בקשתות זה לזה)

 

רמז: להניח בעזרת אינדוקציה שהטענה נכונה לכל גרף G' עם פחות מ- n צמתים, ולהסתכל על שני צמתים כלשהם.

 

 

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

[snorlax]

אתה בכיוון.

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

אם לא, תסתכל על הגרף שמתקבל בלי 2 הצמתים האלה והקשתות שמחוברות אליהם.

בגרף הזה יש http://www.codecogs.com/gif.latex?n-2 צמתים ומספר הקשתות שלו גדול או שווה ל http://www.codecogs.com/gif.latex?m-(n-1)

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

[incog]

פתרון: נוכיח באינדוקציה על n בסיס (פשוט)
נניח נכונות על גרפים בגודל n ונוכיח על גרפים בגודל n+1
ניקח שתי צמתים שמחוברים בקשת v1,v2  ונסתכל על הגרף בעל n-2 הצמתים שלא כולל אותם (ואת הקשתות היוצאות מהן) , נסמן אותו ב-G', ואת מספר הצמתים בו ב-m'.
אם יש בו יותר מ- n-2)^2/4)  קשתות אז על פי הנחת האינדוקציה יש שם משולש וסיימנו.

אחרת יש שם פחות מ- n-2)^2/4)  קשתות. נסמן ב-m''  את הקשתות שיוצאות מ- v_1 ו- v_2 ליתר n-2 הצמתים. אזי מתקיים כי:
m'+m''+1=m
לכן מכיוון ש: m>(n-2)^2/4 ו- m'<(n-2)^2/4
תקבל ש: m''>n
וכעת משובך היונים מקבלים שבהכרח יש צומת v_3 שמחובר גם ל-V1 וגם ל-v_2 ולכן יש לך מעגל...

[csstud]

תודה לשניכם :)

 

snorlax - לא הבנתי למה מספר הקשתות גדול או שווה לm-n+1 8-[

[snorlax]

יש קשת אחת בין 2 הצמתים

בגלל שהגרף פשוט ובגלל שאמרנו שאין להם עוד צומת שכן יכולות להיות רק עוד n-2 קשתות משניהם לשאר הצמתים (לא יכולות להיות 2 קשתות מכל אחד מהם לאותו צומת)

 

http://www.codecogs.com/gif.latex?%7Bm%7D'%20%5Cgeq%20m%20-%20(n-2)%20-%201%20=%20m%20-n%20+1

 

http://www.codecogs.com/gif.latex?%7Bm%7D'%5Cgeq%20m-n+1

[csstud]

יש קשת אחת בין 2 הצמתים

בגלל שהגרף פשוט ובגלל שאמרנו שאין להם עוד צומת שכן יכולות להיות רק עוד n-2 קשתות משניהם לשאר הצמתים (לא יכולות להיות 2 קשתות מכל אחד מהם לאותו צומת)

 

http://www.codecogs.com/gif.latex?%7Bm%7D'%20%5Cgeq%20m%20-%20(n-2)%20-%201%20=%20m%20-n%20+1

 

http://www.codecogs.com/gif.latex?%7Bm%7D'%5Cgeq%20m-n+1

אוי נכון.. תודה!