إنشاء رسم بياني عشوائيًا بناءً على عدد الاتصالات في كل عقدة

Question

أحاول إنشاء رسم بياني يعتمد على بعض البيانات المتوفرة لدي.

ينبغي أن يكون هذا الرسم البياني N العقد التي يكون عدد حواف كل عقدة فيها يساوي رقمًا عشوائيًا P(k), ، حيث k هو "فهرس" العقدة (معظمه تعسفي).

سؤالي هو، هل هناك طريقة فعلية للقيام بذلك؟أعتقد أنني بحاجة إلى مزيد من البيانات التي تحدد الكثافة أو درجة أخرى من الاتصالات (N1->N2->N3)، لكنني لست متأكدًا تمامًا.

Answer 1

أنت تريد بشكل أساسي إنشاء رسم بياني بتسلسل درجات معين (الذي تريده أن يكون عشوائيًا، لكن هذا ليس له صلة)؛وهذا ما يسمى مشكلة في تحقيق الرسم البياني الذي يتم حله على سبيل المثال.بواسطة خوارزمية هافيل-حكيمي بمعنى أن الخوارزمية ستعيد رسمًا بيانيًا (بسيطًا) بتسلسل الدرجة المرغوبة إذا كان ذلك ممكنًا (تسمى هذه التسلسلات رسم بياني).لاحظ أنه لم تنتهي جميع التسلسلات المحدودة $\mathbb N$ هي رسومية على سبيل المثال.لا يمكن رسم أي تسلسل مجموع أعضائه إلى رقم فردي بواسطة ليما المصافحة (والتي تنص على أن مجموع جميع الدرجات في الرسم البياني يساوي ضعف عدد الحواف في الرسم البياني وبالتالي زوجي).علاوة على ذلك، فإن الحلول بشكل عام لن تكون فريدة من نوعها:تسلسل الدرجة $(2, 2, 2, 2, 2, 2)$ على سبيل المثال يمكن أن تتحقق من خلال الرسم البياني للدورة $C_6$ من الحجم $6$ أو الاتحاد المفكك $C_3 \mathop{\dot\cup} C_3$ من الرسوم البيانية دورتين $C_3$ من الحجم $3$ كل.

تحتوي العديد من مكتبات الرسوم البيانية للغات البرمجة على تطبيقات خوارزمية لهذه المشكلة، على سبيل المثال مكتبة بايثون Networkx.