גרף מקרי

בתורת הגרפים, גרף מקרי הוא גרף הנוצר על ידי תהליך אקראי, או נבחר מתוך התפלגות על מרחב הגרפים. תורת הגרפים האקראיים עוסקת בתכונות של הגרף המתקיימות בהסתברות 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)$.

הפניות

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)

• גרפים מקריים באתר 'לא מדוייק'.

חוקרים המלמדים על גרפים אקראיים בישראל

• פרופ' מיכאל קריבלביץ', המחלקה למתמטיקה, אוניברסיטת תל-אביב.
• ד"ר איתן סייג, המחלקה למתמטיקה, אוניברסיטת בן-גוריון.