رسم بياني عشوائي
الرسم البياني العشوائي (Random Graph) في الرياضيات، هو عبارة عن الرسم البياني الذي يتكون من خلال عملية عشوائية. ونظرية الرسم البيانى العشوائي تعد نقطة التقاطع بين نظريتي الاحتمال والرسم البياني، وتقوم بدراسة خصائص الرسوم البيانية العشوائية المتطابقة.
نماذج الرسم البياني العشوائي
و يتم نيل رسم بياني عشوائي عبر البدء بعدد ن من القمم ومن ثم ايصال بعض الخطوط بينها على نحو عشوائي. وتنتج نماذج الرسوم البيانية العشوائية المختلفة توزيعات احتمالية مختلفة على الرسوم البيانية. ويعتبر النموذج الأكثر دراسة هو النموذج إيردوس - Rényi، حيث يمثل ب مجموعة (ن، ع)، حيث كل خط واصل بين نقطتين يكون له احتمال ع. مستقل عن غيره.وهناك نموذج شديد الصلة ب هذا النموذج، يمثل بالمجموعة (ن، م)، حيث ياخد كل رسم بياني قيمة احتمال متساوى مع بقية الرسوم البيانية الأخرى مع عدد ص من الخطوط.والنموذج الأخير يمكن أن ينظر إليه باعتباره لقطة في وقت معين (م) من العملية العشوائية للرسم البياني، التي تكون عملية عشوائية تبدأ مع النقاط ن وليس لها خطوط واصلة ويضيف في كل خطوة واحدة خط جديد يتم اختياره بشكل موحد من مجموعة الخطوط المفقودة.
و لو بدانا مع مجموعة لانهائية من القمم، ومرة أخرى يكون كل خط له احتمال ع منفصل عن بقية الخطوط، فسوف نحصل على العنصر ل والذي يسمى الرسم البياني العشوائي اللا منتهى.إلا في الحالات النادرة عندما يكون ع 0 أو 1 ،و هنا من المؤكد أن يكون العنصر ل له الخواص التالية
:لأيالعناصر n+m a_1,\ldots, a_n,b_1,\ldots, b_m \in V، هناك قمة تكون متاخمة لكل من وليس متاخمة إلى أي منكما تبين أنه إذا كانت مجموعة القمم قابلة للعد إذا هناك، طبقا إلى التماثل، فقط رسم بياني واحد تنطبق عليه هذه الخاصية، ويدعى عندها باسم الرسم البياني رادو. وبالتالي أي رسم بياني عشوائي غير قابل للعد يكاد يكون من المؤكد أنه رسم بياني رادو، لهذا السبب بمكن ان يسمى أحيانا ببساطة الرسم البياني العشوائي.
نموذج آخر، والذي يعمم الرسوم البيانية إيردوس - Rényi، هو نموذج random dot-product. والرسم البياني random dot-product يربط متجه حقيقي. مع كل قمة احتمال وجود خط واصل uv بين أي من القمم u و v هو دالة في u.v بالنسبة للقمم الخاصة بهم.الرسوم البيانية العشوائية لنماذج مصفوفة شبكة الاحتمالات عبر خواص الخطوط الواصلة بين القمم، والتي تمثل احتمالأن يكون الخطموجودا لفترة زمنية محددة. هذا النموذج قابل للتوسع للرسوم البيانية الموجهة وغير الموجهة ؛ المرجحة وغير المرجحة ؛ والساكنة أو المتحركة.الرسم البياني العشوائي العادييشكل حالة خاصة، مع الخصائص التي قد تختلف عن الرسوم البيانية العشوائية بصفة عامة.
خصائص الرسوم البيانية العشوائية
نظرية الرسوم البيانية العشوائية تعلم الخصائص النموذجية لللرسوم البيانية بشكل عشوائي، وتلك التي تعقد مع احتمال كبير لاستخلاصها من الرسوم البيانية لتوزيع معين. على سبيل المثال، قد نسأل عن قيمة معينة ل n و p ما هو احتمال أن تكون المجموعة (n، p) متصلة. في دراسة مثل هذه المسائل، يركز الباحثين في كثير من الأحيان على السلوك المقارب للرسوم البيانية العشوائية، والقيم التي تتلاقى لمختلف الاحتمالات وn تتزايد بسرعة كبيرة جدا.
نظرية الطبقات تمثل الترابط بين الرسوم البيانية العشوائية، ولا سيما الكبيرة منها بلا حدود.(دوال العتبة، وتطور مجموعة ~)الرسوم البيانية العشوائية تستعمل على نطاق واسع في الأسلوب احتمالي، حيث واحدة تحاول إثبات وجود الرسوم البيانية مع خصائص معينة. وجود خاصية في الرسم البياني العشوائي يمكن أن يعني في كثير من الأحيان، عبر الشهير Szemerédi فرضية انتظامها، ووجود تلك الخصائص تقريبا على جميع الرسوم البيانية.
تاريخ الرسوم البيانية العشوائية
الرسوم البيانية العشوائية تم تحديدها لاول مرة من قبل بول إيردوس وألفريد Rényi في سنة 1959 على الورق "في الرسوم البيانية العشوائية" في سنة النشر. الرياضيات. دبريسين 6، ص 290-297.
المراجع
areq.net
التصانيف
نظرية المخططات عشوائي الرسوم البيانية العلوم البحتة رياضيات