כמה דברים ספציפיים לגבי הוכחה בשיטה ההסתברותית
ראיתי את המשפט הבא:
אם (G=(V,E גרף בעל דרגה מינימלית gama>=1 וגם V|=n|, אזי יש ב-G
קבוצה שולטת בגודל לכל היותר:
zz n[ln(1+gama)+1]/(1+gama) zz. (*)
1) ראשית, עוד לפני ההוכחה, לא ברור לי למה זה הגודל של הקבוצה השולטת המקסימלית. הרי הקבוצה השולטת המקסימלית היא פשוט קבוצת כל קדקדי הגרף G - כלומר הקבוצה V.
לגבי ההוכחה..ארשום את ההתחלה שלה שהיא בעצם רלוונטית לשאלות שלי..
נגריל קדקדים לתוך הקבוצה השולטת. X תיהיה תת קבוצה מקרית של V
כך שקדקד v נבחר לX בהסתברות p ולא נבחר בהסתברות 1 מינוס p.
נגדיר קבוצה:
zz Yx = {v in V | v isnt in X and v doesnt have neighbour in X zz
כמובן שמתקיים ש X U Yx היא קבוצה שלטת.
נסתכל על (|E(|XUYx.
אני רוצה להבין שניי דברים..
2) מה אומר הביטוי הזה..בעצם אפצל את השאלה לשניים:
א'. הביטוי בתוך הערך המוחלט זה קדקדים בקבוצה מקרית ספציפית X שהוגרלה איחוד עם כל הקדקדים שהם לא באותה קבוצה X ושאין להם שכן ב-X (שזה בעצם כל הקדקדים בגרף כך שיש בינם לבין כל קדקד מ-X לפחות קשת אחת)?
ב'. מה המשמעות של התוחלת של הגודל הזה? תוחלת זה ממוצע משוקלל..מה זה הממוצע המשוקלל כאן..ממוצע של מה? ממוצע על פני מי/מה?
3) בהוכחה מראים שהתוחלת הזו קטנה או שווה להביטוי (*).
המשמעות של זה היא שבטוח יש קבוצה שולטת בגרף שהגודל שלה הוא לכל היותר (*), כי אחרת (=אין קבוצה שולטת בגרף שהגודל שלה הוא לכל היותר (*)),
אז כל קבוצה שולטת בגרף היא בעלת מספר קדקדים שגדול מ(*) ואז זה יסתור את זה שהתוחלת קטנה מ(*)?
תודה מראש
ראיתי את המשפט הבא:
אם (G=(V,E גרף בעל דרגה מינימלית gama>=1 וגם V|=n|, אזי יש ב-G
קבוצה שולטת בגודל לכל היותר:
zz n[ln(1+gama)+1]/(1+gama) zz. (*)
1) ראשית, עוד לפני ההוכחה, לא ברור לי למה זה הגודל של הקבוצה השולטת המקסימלית. הרי הקבוצה השולטת המקסימלית היא פשוט קבוצת כל קדקדי הגרף G - כלומר הקבוצה V.
לגבי ההוכחה..ארשום את ההתחלה שלה שהיא בעצם רלוונטית לשאלות שלי..
נגריל קדקדים לתוך הקבוצה השולטת. X תיהיה תת קבוצה מקרית של V
כך שקדקד v נבחר לX בהסתברות p ולא נבחר בהסתברות 1 מינוס p.
נגדיר קבוצה:
zz Yx = {v in V | v isnt in X and v doesnt have neighbour in X zz
כמובן שמתקיים ש X U Yx היא קבוצה שלטת.
נסתכל על (|E(|XUYx.
אני רוצה להבין שניי דברים..
2) מה אומר הביטוי הזה..בעצם אפצל את השאלה לשניים:
א'. הביטוי בתוך הערך המוחלט זה קדקדים בקבוצה מקרית ספציפית X שהוגרלה איחוד עם כל הקדקדים שהם לא באותה קבוצה X ושאין להם שכן ב-X (שזה בעצם כל הקדקדים בגרף כך שיש בינם לבין כל קדקד מ-X לפחות קשת אחת)?
ב'. מה המשמעות של התוחלת של הגודל הזה? תוחלת זה ממוצע משוקלל..מה זה הממוצע המשוקלל כאן..ממוצע של מה? ממוצע על פני מי/מה?
3) בהוכחה מראים שהתוחלת הזו קטנה או שווה להביטוי (*).
המשמעות של זה היא שבטוח יש קבוצה שולטת בגרף שהגודל שלה הוא לכל היותר (*), כי אחרת (=אין קבוצה שולטת בגרף שהגודל שלה הוא לכל היותר (*)),
אז כל קבוצה שולטת בגרף היא בעלת מספר קדקדים שגדול מ(*) ואז זה יסתור את זה שהתוחלת קטנה מ(*)?
תודה מראש
