גרף מקרי

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

מודל מתמטי

ישנם מודלים רבים לתהליך היוצר גרף מקרי. את המודל הראשון הציעו ריי סולומונוף ואנאטול רפופורט ב-1951, אך זה לא זכה להתייחסות רחבה בספרות. את המודל השימושי והנפוץ ביותר הציגו פול ארדש ואלפרד רניי בסדרה של 8 מאמרים שפורסמו בשנים 1959-1968. לפי מודל ארדש-רניי, גרף $\ G(n,p)$ הוא גרף בן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} קודקודים, שבו בוחרים עבור כל קשת, בסיכוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ובאופן בלתי תלוי, האם הקשת קיימת בגרף. המודל בוחר, לפיכך, גרף אחד מבין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^{\tbinom{n}{2}} } הגרפים האפשריים, וההסתברות של גרף מסוים בן $e$ קשתות היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p^e(1-p)^{\tbinom{n}{2}-e} } . כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=1/2 } , למרחב יש התפלגות אחידה בדידה.

המודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ G(n,M)} מתאר מרחב הסתברות אחיד על כל הגרפים עם $n$ קדקודים ובדיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} קשתות. ישנם גם מספר מודלים לגרפים רגולריים מקריים (גרף רגולרי הוא גרף שבו מכל קדקוד יוצא אותו מספר של קשתות).

מודל נוסף שהציגו ארדש ורניי הוא של גרף על מספר בן מניה ולא סופי של קודקודים.^[1] במודל זה כל זוג קודקודים מחובר בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2} (ולמעשה אפשר לבחור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0<p<1} ). מתברר כי תהליך זה מוביל בהסתברות $1$ לטיפוס איזומורפיזם יחיד המכונה "גרף רדו". לגרף זה תכונות אוניברסליות חשובות, וכך למשל כל גרף בן מניה משתכן בו.^[2]

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

יש תכונות של הגרף שאותן אפשר לחשב בקלות. לדוגמה, תוחלת מספר המשולשים בגרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ G(n,p)} היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tbinom{n}{3}p^3 } , משום שיש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \tbinom{n}{3} } שלשות של קדקודים, וכל אחת מהווה משולש בסיכוי של $\ p^{3}$ .

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

במאמריהם שהוזכרו לעיל פיתחו ארדש ורניי תיאור "אבולוציוני" של גרף מקרי, הסוקר את ההתפתחות של הגרף - בהסתברות 1 - כאשר n גדל לאינסוף, עבור ערכים משתנים של p. כאשר הדרגה הממוצעת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,c=p(n-1)} קבועה, מבנה הגרף תלוי ב-c: בעידן c<1 כל רכיבי הקשירות הם פשוטים וקטנים: כלומר עצים או עצים עם קשת עודפת אחת, וגודלם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(\log n)} . יש הסתברות חיובית לכך שכל רכיבי הקשירות הם עצים. בעידן c>1 יש רכיב קשירות גדול, שמספר קודקודיו ליניארי ב-n, ושאר הרכיבים פשוטים וקטנים, באותו מובן. הזמן c=1 הוא "מעבר הפאזה", שבו גודל הרכיב הענק הוא (כתמיד, בהסתברות 1), הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \Theta(n^{2/3})} . הגרף נעשה קשיר כשהדרגה הממוצעת מגיעה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \log(n)} .

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

רונלד פייגין הראה ב-1976 כי לתכונות מסדר ראשון (בשפה שבה היחס היחיד הוא יחס השכנות בגרף) יש יכולת הפרדה חלשה מאד: הסיכוי של כל תכונה כזו, כאשר n שואף לאינסוף והגרפים מוגרלים על-פי המודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(n,p)} , הוא או אפס או אחד, באופן שאינו תלוי בקבוע p (כל עוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 0<p<1} )^[3].

שהרן שלח וג'ואל ספנסר הוכיחו ב-1988 שתכונות מסדר ראשון מקיימות את "חוק ה-0-1" (שלפיו ההסתברות של התכונה שואפת לאפס או לאחד כאשר n שואף לאינסוף) עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p = n^{-\alpha}} אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} אינו רציונלי, ולעומת זאת אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\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

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

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

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

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

30713494גרף מקרי

[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

[1]

[2]

[3]

נושאים בתורת הגרפים
הגדרות	צומת • קשת • דרגה • מסלול • מרחק
מבנים	גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס
בניות וטיפוסים	גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך
תכונות	גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי

גרף מקרי

תוכן עניינים

מודל מתמטי

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

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

לקריאה נוספת

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

הערות שוליים

תפריט ניווט

גרף מקרי

מודל מתמטי

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

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

לקריאה נוספת

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

הערות שוליים

תפריט ניווט

חיפוש