رسم بياني عشوائي

الرسم البياني العشوائي (بالإنجليزية: Random Graph)‏ في الرياضيات، هو الرسم البياني الذي يَنشأ عن طريق عملية عشوائية. ونظرية الرسم البيانى العشوائي تعتبر نقطة التقاطع بين نظريتي الاحتمال والرسم البياني، وتقوم بدراسة خصائص الرسوم البيانية العشوائية المتطابقة.

نماذج الرسم البياني العشوائي

و يتم الحصول على رسم بياني عشوائي من خلال البدء بعدد ن من القمم ومن ثم ايصال بعض الخطوط بينها على نحو عشوائي. وتنتج نماذج الرسوم البيانية العشوائية المختلفة توزيعات احتمالية مختلفة على الرسوم البيانية. ويعتبر النموذج الأكثر دراسة هو النموذج إيردوس - Rényi، حيث يمثل ب مجموعة (ن، ع)، حيث كل خط واصل بين نقطتين يكون له احتمال ع. مستقل عن غيره.وهناك نموذج شديد الصلة ب هذا النموذج، يمثل بالمجموعة (ن، م)، حيث ياخد كل رسم بياني قيمة احتمال متساوى مع بقية الرسوم البيانية الأخرى مع عدد ص من الخطوط.والنموذج الأخير يمكن أن ينظر إليه باعتباره لقطة في وقت معين (م) من العملية العشوائية للرسم البياني، التي تكون عملية عشوائية تبدأ مع النقاط ن وليس لها خطوط واصلة ويضيف في كل خطوة واحدة خط جديد يتم اختياره بشكل موحد من مجموعة الخطوط المفقودة.

و لو بدانا مع مجموعة لانهائية من القمم، ومرة أخرى يكون كل خط له احتمال ع منفصل عن بقية الخطوط، فسوف نحصل على العنصر ل والذي يسمى الرسم البياني العشوائي اللا منتهى.إلا في الحالات النادرة عندما يكون ع 0 أو 1 ،و هنا من المؤكد أن يكون العنصر ل له الخواص التالية :

لأي $n+m$ العناصر n+m a_1,\ldots, a_n,b_1,\ldots, b_m \in V، هناك قمة$c\in V$ تكون متاخمة لكل من وليس متاخمة إلى أي من $b_{1},\ldots ,b_{m}$

كما تبين أنه إذا كانت مجموعة القمم قابلة للعد إذا هناك، طبقا إلى التماثل، فقط رسم بياني واحد تنطبق عليه هذه الخاصية، ويسمى عندها باسم الرسم البياني رادو. وبالتالي أي رسم بياني عشوائي غير قابل للعد يكاد يكون من المؤكد أنه رسم بياني رادو، لهذا السبب بمكن ان يسمى أحيانا ببساطة الرسم البياني العشوائي.

نموذج آخر، والذي يعمم الرسوم البيانية إيردوس - Rényi، هو نموذج random dot-product. والرسم البياني random dot-product يربط متجه حقيقي. مع كل قمة احتمال وجود خط واصل uv بين أي من القمم u و v هو دالة في u.v بالنسبة للقمم الخاصة بهم.

الرسوم البيانية العشوائية لنماذج مصفوفة شبكة الاحتمالات عبر خواص الخطوط الواصلة بين القمم، والتي تمثل احتمال $p_{i,j}$ أن يكون الخط $e_{i,j}$ موجودا لفترة زمنية محددة. هذا النموذج قابل للتوسع للرسوم البيانية الموجهة وغير الموجهة ؛ المرجحة وغير المرجحة ؛ والساكنة أو المتحركة.

الرسم البياني العشوائي العادييشكل حالة خاصة، مع الخصائص التي قد تختلف عن الرسوم البيانية العشوائية بصفة عامة.

خصائص الرسوم البيانية العشوائية

نظرية الرسوم البيانية العشوائية تدرس الخصائص النموذجية لللرسوم البيانية بشكل عشوائي، وتلك التي تعقد مع احتمال كبير لاستخلاصها من الرسوم البيانية لتوزيع معين. على سبيل المثال، قد نسأل عن قيمة معينة ل n و p ما هو احتمال أن تكون المجموعة (n، p) متصلة. في دراسة مثل هذه المسائل، يركزالباحثين في كثير من الأحيان على السلوك المقارب للرسوم البيانية العشوائية، والقيم التي تتلاقى لمختلف الاحتمالات وn تتزايد بسرعة كبيرة جدا. نظرية الطبقاتتمثل الترابط بين الرسوم البيانية العشوائية، ولا سيما الكبيرة منها بلا حدود.

(دوال العتبة، وتطور مجموعة ~)

الرسوم البيانية العشوائية تستخدم على نطاق واسع في الأسلوب احتمالي، حيث واحدة تحاول إثبات وجود الرسوم البيانية مع خصائص معينة. وجود خاصية في الرسم البياني العشوائي يمكن أن يعني في كثير من الأحيان، عبر الشهير Szemerédi فرضية انتظامها، ووجود تلك الخصائص تقريبا على جميع الرسوم البيانية.

تاريخ الرسوم البيانية العشوائية

الرسوم البيانية العشوائية حددت لأول مرة من قبل بول إيردوس وألفريد Rényi في 1959 على الورق «في الرسوم البيانية العشوائية» في سنة النشر. الرياضيات. دبريسين 6، ص 290-297.

انظر أيضًا

• تقطير

مصادر

• Béla Bollobás، الرسوم البيانية العشوائية، 2nd الطبعة، 2001، مطبعة جامعة كامبريدج
• كريستين والنيكل random dot-product: نموذجا للشبكات الاجتماعية، Ph.D. أطروحة، وجامعة جونز هوبكنز، 2007.