imported>Virant: /* חוקי אפס אחד לגרפים מקריים */ קישורים פנימיים

2026-03-24T02:33:42Z

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

דף חדש

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

==מודל מתמטי==

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

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

מודל נוסף שהציגו ארדש ורניי הוא של גרף על מספר בן מניה ולא סופי של קודקודים.{{הערה|Erdős, P.; Rényi, A. (1963), "Asymmetric graphs", '''Acta Mathematica Academiae Scientiarum Hungaricae''', 14: 295–315}} במודל זה כל זוג קודקודים מחובר בהסתברות <math>1/2</math> (ולמעשה אפשר לבחור כל <math>0<p<1</math>). מתברר כי תהליך זה מוביל בהסתברות <math>1</math> לטיפוס [[איזומורפיזם]] יחיד המכונה "גרף רדו". לגרף זה תכונות אוניברסליות חשובות, וכך למשל כל גרף בן מניה משתכן בו.{{הערה|Cameron, Peter J. (1997), "[https://arxiv.org/abs/1301.7544 The random graph]", '''The mathematics of Paul Erdős''', II, Algorithms Combin., 14, Berlin: Springer, pp. 333–351}}

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

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

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

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

==חוקי אפס אחד לגרפים מקריים==
רונלד פייגין הראה ב-1976 כי לתכונות [[שפה מסדר ראשון|מסדר ראשון]] (בשפה שבה היחס היחיד הוא יחס השכנות בגרף) יש יכולת הפרדה חלשה מאד: הסיכוי של כל תכונה כזו, כאשר n שואף לאינסוף והגרפים מוגרלים על-פי המודל <math>G(n,p)</math>, הוא או אפס או אחד, באופן שאינו תלוי בקבוע p (כל עוד <math>\ 0<p<1</math>){{הערה|[http://researcher.ibm.com/researcher/files/us-fagin/jsl76.pdf Probabilities on finite models ] R. Fagin, J. Symbolic Logic, 41 (1976), pp. 50–58}}.

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

== לקריאה נוספת ==

8 המאמרים של ארדש ורניי:
<div class="mw-content-ltr">
* '''[http://www.renyi.hu/~p_erdos/1959-11.pdf 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
</div>

== קישורים חיצוניים ==
המאמר של סולומונוף ורפופורט:
* {{דף שער בספרייה הלאומית|987007563131005171|גרפים אקראיים}}
* {{MathWorld}}
<div class="mw-content-ltr">
* '''Connectivity Of Random Nets''', Ray Solomonoff & Anatol Rapoport, 1951 [http://world.std.com/~rjs/50.pdf (pdf)]
</div>

==הערות שוליים==
{{הערות שוליים}}

{{תורת הגרפים}}

{{בקרת זהויות}}

[[קטגוריה:תורת הגרפים]]
[[קטגוריה:פאול ארדש]]
[[nl:Complexe netwerken#Random netwerken]]

גרף מקרי - היסטוריית גרסאות

imported>Virant: /* חוקי אפס אחד לגרפים מקריים */ קישורים פנימיים