גרף מקרי

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

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

לתכונות מסדר ראשון (בשפה שבה היחס היחיד הוא יחס השכנות בגרף) יש יכולת הפרדה חלשה מאד: הסיכוי של כל תכונה כזו, כאשר n שואף לאינסוף והגרפים מוגרלים על-פי המודל G(n,p), הוא או אפס או אחד, באופן שאינו תלוי בקבוע p (כל עוד \ 0<p<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)