גרף מקרי

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

מודל מתמטי

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

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

מודל נוסף שהציגו ארדש ורניי הוא של גרף על מספר בן מניה ולא סופי של קודקודים.^[1] במודל זה כל זוג קודקודים מחובר בהסתברות ${\displaystyle 1/2}$ (ולמעשה אפשר לבחור כל ${\displaystyle 0<p<1}$). מתברר כי תהליך זה מוביל בהסתברות ${\displaystyle 1}$ לטיפוס איזומורפיזם יחיד המכונה "גרף רדו". לגרף זה תכונות אוניברסליות חשובות, וכך למשל כל גרף בן מניה משתכן בו.^[2]

האבולוציה של גרף מקרי

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

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

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

חוקי אפס אחד לגרפים מקריים

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

שהרן שלח וג'ואל ספנסר הוכיחו ב-1988 שתכונות מסדר ראשון מקיימות את "חוק ה-0-1" (שלפיו ההסתברות של התכונה שואפת לאפס או לאחד כאשר n שואף לאינסוף) עבור ${\displaystyle \ p=n^{-\alpha }}$ אם ${\displaystyle \alpha }$ אינו רציונלי, ולעומת זאת אם ${\displaystyle \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

קישורים חיצוניים

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

• גרפים אקראיים, דף שער בספרייה הלאומית
• גרף מקרי, באתר MathWorld (באנגלית)

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

הערות שוליים

1. Erdős, P.; Rényi, A. (1963), "Asymmetric graphs", Acta Mathematica Academiae Scientiarum Hungaricae, 14: 295–315
2. Cameron, Peter J. (1997), "The random graph", The mathematics of Paul Erdős, II, Algorithms Combin., 14, Berlin: Springer, pp. 333–351
3. Probabilities on finite models R. Fagin, J. Symbolic Logic, 41 (1976), pp. 50–58