גרפים מקריים

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

תורת הגרפים המקריים היא חלק מתורת הגרפים, העוסק במרחבים הסתברותיים של גרפים. ישנם מודלים רבים של מרחבי הסתברות שכאלה, אך המודל השימושי ביותר עד כה הוצג לראשונה על ידי פול ארדש ואלפרד רניי בשנת 1959 ופותח על ידיהם בסדרה של 8 מאמרים שפורסמו עד שנת 1968. מודל זה מסומן $\ G(n,p)$ כאשר המספר הטבעי n מסמן את מספר הקדקודים בגרף (מתייחסים אליהם כאל קדקודים מסומנים), והמספר p שמקיים $\ 0<p<1$ מסמן את ההסתברות של כל זוג קדקודים שונים להיות מחוברים בקשת (כאשר מניחים שאין תלות בין זוג לזוג). גודלו של מרחב ההסתברות $\ G(n,p)$ הוא לכן $\ 2^{\binom{n}{2}}$ , וההסתברות של גרף מסוים עם e קשתות הוא $\ p^e(1-p)^{\binom{n}{2}-e}$ . בפרט, כאשר $\ p=\frac{1}{2}$ זהו מרחב הסתברות עם התפלגות אחידה: לכל גרף בו יש הסתברות $\ \left(\frac{1}{2}\right)^{\binom{n}{2}}$ .

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

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

יש לציין כי מודל של גרפים מקריים הוצג כבר ב־1951 על ידי ריי סולומונוף ואנאטול רפופורט, אך לא זכה להדים רבים.

[עריכה] הפניות

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