الرسوم البيانية - الفصل 8

إذا كان الشكل كامل ذو قسمين يحتوي على ‪5‬عقد في ‪M‬ و ‪3‬عقد في ‪N‬، فإن رمز هذا الشكل هو ‪K(5,3)‬.

يمكن تقسيم أي شكل كامل ذو قسمين إلى قسمين M و N بحيث تكون كل عقدة في M متصلة بـ جميع العقد في N.

الشكل الكامل ذو قسمين ‪K(3,2)‬ هو نفس الشكل ‪K(2,3)‬.

الشكل الكامل ذو قسمين ‪K(4,4)‬ يحتوي على ‪8‬حواف.

إذا كان الشكل يحتوي على ‪10‬عقد وليس كل عقدة متصلة بكل عقدة أخرى، فإن الشكل ليس كامل ذو قسمين.

إذا كانت مصفوفة الجوار متماثلة، فإن الشكل المقابل هو شكل موجه.

تُستخدم مصفوفة السقوط لتمثيل األشكال غير الموجهة فقط.

في مصفوفة الجوار، يمثل العنصر $a_{ij}$ عدد الحواف بين الرأس $v_i$ و $v_j$.

إذا كانت مصفوفة الجوار تحتوي على قيم 1 فقط، فإن الشكل المقابل هو شكل بسيط.

في مصفوفة السقوط، يمثل العنصر $m_{ij}$ وجود أو عدم وجود حافة بين الرأس $v_i$ والحافة $e_j$.

يمكن أن تكون مصفوفة الجوار لشكال متعدد غير ثنائية.

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

في مصفوفة $a_{ij}$ ، يمثل العنصر $a_{ij}$ عدد الحواف من الرأس $v_i$ إلى $v_j$.

يمكن استخدام مصفوفة الجوار لتمثيل األشكال غير الموجهة فقط.

إذا كان قطر المصفوفة الرئيسي غير صفري، فإن الشكل الممثل يحتوي على حواف ذاتية.

يمكن رسم الشكل في المثال ‪ -8‬بدون تقاطعات.

جميع األشكال املستوية يمكن رسمها بدون تقاطعات.

إذا كان للشكل ‪ 6‬رؤوس، فإن له ‪ 6‬أضلاع أيضًا.

الشكل املستوي له دائمًا عدد من المناطق يساوي عدد الرؤوس ناقص واحد.

يمكن استخدام خوارزمية ديكسترا لإيجاد أقصر مسار بين نقطتين في أي شكل.

يُمكن تمثيل العلاقة المنعكسة باستخدام شكل موجه حيث توجد حلقة حول كل عقدة.

كل علاقة متماثلة هي أيضًا علاقة منعكسة.

إذا كانت العلاقة ليست متماثلة، فإنها دائمًا تكون غير متماثلة.

إذا وجدت علاقة (a, b) و(b, c) في العلاقة، فإن العلاقة الانتقالية تضمن وجود (a, c) في العلاقة.

يمكن استخدام مصفوفة السقوط لتمثيل الشكل الغير موجه.

تُستخدم قائمة الجوار لتمثيل الشكل الكامل k4 بـ 4 صفوف و 4 أعمدة.

يمكن استخدام مصفوفة الجوار لتمثيل 3 رؤوس و 2 حواف.

يحتوي المسار من A إلى B على عدد الأطراف التي تُستخدم لربط النقاط في المسار.

يمكن لعدد الأطراف في المسار أن تكون أقل من عدد الرؤوس في المسار.

تُستخدم مصفوفة السقوط لتمثيل الأشكال الموجهة فقط.

عدد حواف الشكل يساوي عدد الرؤوس تقسيم 2.

كل شكل موجه هو شكل غير موجه

الشكل الكامل k5 يحتوي على 5 حواف

الشكل الدوري C3 له 3 رؤوس و 3 حواف

يتم تسمية الشكل الذي يمكن رسمه على مستوٍ دون تقاطع بالحافة في تمثيل المستوى للشكل.

الشكل "K4" مستويّ.

الشكل "Q3" الذي يُوضَّح في النصّ ليس مستويّ.

يُمكن أن يُقسّم تمثيل المستوى لشكل إلى مناطق متعددة.

جميع المناطق المُنشأة في تمثيل المستوى لشكل تكون محدودة.

صيغة أويلر (Euler's Formula) تستعمل لحساب "v" في الشكل البسيط المستوي المتصل.

في الشكل البسيط المستوي المتصل صيغة أويلر (Euler's Formula) هي "r = e + v - 2".

في شكلٍ مستويٍّ وبسيطٍّ ومتصلٍّ ذي "21" عقدةٍ (v) درجة كلّ عقدةٍ هي "3" . عندها يكون عدد الحواف "e" يساوي "30".

في الشكل الذى به "21" عقدة (v) من الدرجة "3" ، فإنّ عدد المناطق "r" يساوي "12".

يقصد بالأشكال المميزة (weighted graphs) أن كلّ عقدةٍ لها قيمة مُحددة.

تُستخدم الأشكال المميزة في مسائل "أقصر مسار" بين عقدتين.

الوزن "weight" لبقية المسار من "P" إلى "Q" هو "16".

يُستخدم "الشنكل" لتمثيل العلاقات بين الأشياء ويساعد على فهم "الطوبولوجيا" في الأنظمة.

تُستخدم الأشكال المميزة في "كافة" الأنظمة التي تتعامل مع "الشبكات" (مثل "شبكات الحاسوب" و "الشبكات الاجتماعية").

يُمكن استخدام الأشكال المميزة "فقط" في "الشبكات" وكافة الأنظمة التي تتعامل مع "المسارات" بين عقدتين.

في الشكل المُعطى ، يوجد مسارٌ من العقدة "a" إلى العقدة "d" بطول 2.

يُمكن التعبير عن عدد المسارات بين العقدتين Vi و Vj بطول r باستخدام مصفوفة Ar ، حيث A هي مصفوفة الجوار للشكل .

مصفوفة الجوار للشكل هي مصفوفة مربعة.

في الشكل G ، إذا كانت العقدة Vi مرتبطة بالعقدة Vj ، فإن عنصر المصفوفة Aij سيُساوي 1 في مصفوفة الجوار .

المصفوفة B التي تُستخدم لحساب عدد المسارات تُعرف بمصفوفة الجوار للشكل .

عدد المسارات من العقدة a إلى العقدة d بطول 1 هو 1 ، وذلك باستخدام الشكل المُعطى .

المتتابعة ( a, e, a, d, b, c, a ) تمثّل مسارًا دوريًا في الشكل G المُعطى .

المتتابعة ( c, b, d, a, e, c ) تُعتبر مسارًا بسيطاً في الشكل G المُعطى .

من خلال دراسة الشكل G المُعطى ، يُمكن نستنتج أن الشكل متصل .

الشكل K4 لا يُمكن رسمه بطريقة تُصبح مستوية .