גרף מקרי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

המודל[עריכת קוד מקור | עריכה]

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

לפי מודל ארדש-רניי, גרף \ G(n,p) הוא גרף בן n קודקודים, שבו בוחרים עבור כל קשת, בסיכוי p ובאופן בלתי תלוי, האם הקשת קיימת בגרף. המודל בוחר, לפיכך, גרף אחד מבין \ 2^{\tbinom{n}{2}} הגרפים האפשריים, וההסתברות של גרף מסוים בן e קשתות היא \ p^e(1-p)^{\tbinom{n}{2}-e} . כאשר \ p=1/2 , למרחב יש התפלגות אחידה.

המודל \ G(n,M) מתאר מרחב הסתברות אחיד על כל הגרפים עם n קדקודים ובדיוק M קשתות. ישנם גם מספר מודלים לגרפים רגולריים מקריים (גרף רגולרי הוא גרף שבו מכל קדקוד יוצא אותו מספר של קשתות).

האבולוציה של גרף מקרי[עריכת קוד מקור | עריכה]

יש תכונות של הגרף שאותן אפשר לחשב בקלות. לדוגמה, תוחלת מספר המשולשים בגרף \ G(n,p) היא \ \tbinom{n}{3}p^3 , משום שיש \ \tbinom{n}{3} שלשות של קדקודים, וכל אחת מהווה משולש בסיכוי של \  p^3.

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

במאמריהם שהוזכרו לעיל פיתחו ארדש ורניי תיאור "אבולוציוני" של גרף מקרי, הסוקר את ההתפתחות של הגרף - בהסתברות 1 - כאשר n גדל לאינסוף, עבור ערכים משתנים של p. כאשר הדרגה הממוצעת \,c=p(n-1) קבועה, מבנה הגרף תלוי ב-c: בעידן c<1 כל רכיבי הקשירות הם פשוטים וקטנים: כלומר עצים או עצים עם קשת עודפת אחת, וגודלם \ O(\log n). יש הסתברות חיובית לכך שכל רכיבי הקשירות הם עצים. בעידן c>1 יש רכיב קשירות גדול, שמספר קודקודיו לינארי ב-n, ושאר הרכיבים פשוטים וקטנים, באותו מובן. הזמן c=1 הוא "מעבר הפאזה", שבו גודל הרכיב הענק הוא (כתמיד, בהסתברות 1), \ \Theta(n^{2/3}). הגרף נעשה קשיר כשהדרגה הממוצעת מגיעה ל-\ \log(n).

חוקי אפס אחד לגרפים מקריים[עריכת קוד מקור | עריכה]

רונלד פייגין הראה ב-1976 כי לתכונות מסדר ראשון (בשפה שבה היחס היחיד הוא יחס השכנות בגרף) יש יכולת הפרדה חלשה מאד: הסיכוי של כל תכונה כזו, כאשר n שואף לאינסוף והגרפים מוגרלים על-פי המודל G(n,p), הוא או אפס או אחד, באופן שאינו תלוי בקבוע p (כל עוד \ 0<p<1)[1].

סהרון שלח וג'ואל ספנסר הוכיחו ב-1988 שתכונות מסדר ראשון מקיימות את "חוק ה-0-1" (שלפיו ההסתברות של התכונה שואפת לאפס או לאחד כאשר n שואף לאינסוף) עבור \ p = n^{-\alpha} אם \alpha אינו רציונלי, ולעומת זאת אם \alpha רציונלי אז יש תכונות שההסתברות שלהן (התלויה ב-n) אינה שואפת לאף גבול. בהוכחה מסתכלים על התורה המתקבלת מכל הפסוקים המתארים תכונה בהסתברות 1. מראים שלתורה זו יש מודל אחד בן מנייה (זהו הגרף המקרי האינסופי שהתכונה המרכזית שלו היא שלכל שתי קבוצות זרות של צמתים יש צומת שמחובר לכל הצמתים בקבוצה הראשונה ולאף אחד מן הצמתים בקבוצה השנייה). כמסקנה ממשפט לוונהיים-סקולם מקבלים שהתורה שלמה, ולכן כל תכונה מסדר ראשון או שהיא נובעת מהתורה והסתברותה 1, או ששלילתה נובעת, והסתברותה 0.


לקריאה נוספת[עריכת קוד מקור | עריכה]

8 המאמרים של ארדש ורניי:

  • On Random Graphs I, 1959
  • On The Evolution of Random Graphs, 1960
  • On The Evolution of Random Graphs, 1961
  • On The Strength Of Connectedness Of A Random Graph, 1961
  • Asymmetric Graphs, 1963
  • On Random Matrices, 1964
  • On The Existence Of A Factor Of Degree One Of A Connected Random Graph, 1966
  • On Random Matrices II, 1968

קישורים חיצוניים[עריכת קוד מקור | עריכה]

המאמר של סולומונוף ורפופורט:

  • Connectivity Of Random Nets, Ray Solomonoff & Anatol Rapoport, 1951 (pdf)

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Probabilities on finite models R. Fagin, J. Symbolic Logic, 41 (1976), pp. 50–58