على الرغم من وجود العديد من الأنواع المختلفة من الرسوم البيانية اعتمادًا على عدد القمم وعدد الحواف والترابط وبنيتها العامة، فإن بعض هذه الأنواع الشائعة من الرسوم البيانية هي كما يلي:
1. الرسم البياني الفارغ
أ رسم بياني فارغ هو رسم بياني لا توجد فيه حواف بين رؤوسه. ويسمى الرسم البياني الفارغ أيضًا بالرسم البياني الفارغ.
مثال
يُشار إلى الرسم البياني الفارغ ذو الرؤوس n بالرمز Nn.
2. الرسم البياني تافهة
أ رسم بياني تافه هو الرسم البياني الذي يحتوي على قمة واحدة فقط.
مثال
في الرسم البياني أعلاه، هناك قمة واحدة فقط 'v' بدون أي حافة. ولذلك، فهو رسم بياني تافهة.
3. رسم بياني بسيط
أ رسم بياني بسيط هو الرسم البياني غير الموجه مع لا حواف متوازية و لا حلقات .
رسم بياني بسيط يحتوي على عدد n من القمم، ودرجة كل قمة هي n -1 على الأكثر.مثال
في المثال أعلاه، الرسم البياني الأول ليس رسمًا بيانيًا بسيطًا لأنه يحتوي على حافتين بين الرؤوس A وB كما أنه يحتوي على حلقة.
الرسم البياني الثاني هو رسم بياني بسيط لأنه لا يحتوي على أي حلقات أو حواف متوازية.
4. الرسم البياني غير الموجه
ان رسم بياني غير موجه هو الرسم البياني الذي حوافه غير موجه .
مثال
في الرسم البياني أعلاه، نظرًا لعدم وجود حواف موجهة، فهو رسم بياني غير موجه.
5. الرسم البياني الموجه
أ مخطط موجه هو الرسم البياني الذي يتم توجيه الحواف بواسطة السهام.
يُعرف الرسم البياني الموجه أيضًا باسم رسوم بيانية .
مثال
في الرسم البياني أعلاه، يتم توجيه كل حافة بواسطة السهم. تحتوي الحافة الموجهة على سهم من A إلى B، مما يعني أن A مرتبط بـ B، لكن B ليس مرتبطًا بـ A.
6. الرسم البياني الكامل
يسمى الرسم البياني الذي يتم فيه ربط كل زوج من القمم بحافة واحدة بالضبط الرسم البياني الكامل . أنه يحتوي على جميع الحواف الممكنة.
يحتوي الرسم البياني الكامل ذو الرؤوس n على حواف nC2 تمامًا ويمثلها Kn.
مثال
في المثال أعلاه، نظرًا لأن كل قمة في الرسم البياني متصلة بجميع القمم المتبقية من خلال حافة واحدة بالضبط، فإن كلا الرسمين البيانيين عبارة عن رسم بياني كامل.
7. الرسم البياني المتصل
أ رسم بياني متصل هو رسم بياني يمكننا من خلاله الانتقال من أي قمة إلى أي قمة أخرى. في الرسم البياني المتصل، توجد حافة أو مسار واحد على الأقل بين كل زوج من القمم.
مثال
في المثال أعلاه، يمكننا الانتقال من أي قمة إلى أي قمة أخرى. وهذا يعني وجود مسار واحد على الأقل بين كل زوج من القمم، وبالتالي فهو رسم بياني متصل.
8. الرسم البياني المنفصل
أ الرسم البياني المنفصل هو رسم بياني لا يوجد فيه أي مسار بين كل زوج من القمم.
مثال
يتكون الرسم البياني أعلاه من مكونين مستقلين منفصلين. وبما أنه من غير الممكن الانتقال من رؤوس مكون واحد إلى رؤوس المكونات الأخرى، فهو رسم بياني غير متصل.
9. الرسم البياني العادي
أ رسم بياني منتظم هو رسم بياني تكون فيه درجة جميع القمم متساوية.
إذا كانت درجة جميع القمم هي k، فإنه يسمى الرسم البياني k-العادي.
مثال
في المثال أعلاه، جميع القمم لها الدرجة 2. لذلك تسمى 2- رسم بياني منتظم .
10. الرسم البياني الدوري
يُعرف الرسم البياني الذي يحتوي على رؤوس 'n' (حيث، n>=3) وحواف 'n' التي تشكل دورة من 'n' بكل حوافها باسم رسم بياني للدورة .
يُعرف الرسم البياني الذي يحتوي على دورة واحدة على الأقل باسم أ رسم بياني دوري .
في الرسم البياني للدورة، درجة كل قمة هي 2.
يُشار إلى الرسم البياني للدورة الذي يحتوي على رؤوس n بالرمز Cn.
أمثلة على آلة مور
مثال 1
في المثال أعلاه، جميع القمم لها الدرجة 2. لذلك فهي جميعها رسوم بيانية دائرية.
مثال 2
وبما أن الرسم البياني أعلاه يحتوي على دورتين، فهو رسم بياني دوري.
11. الرسم البياني الحلقي
يسمى الرسم البياني الذي لا يحتوي على أي دورة باسم الرسم البياني الحلقي .
مثال
وبما أن الرسم البياني أعلاه لا يحتوي على أي دورة فيه، فهو رسم بياني غير دوري.
12. الرسم البياني الثنائي
أ رسم بياني ثنائي هو رسم بياني يمكن من خلاله تقسيم مجموعة القمم إلى مجموعتين بحيث تكون الحواف بين المجموعات فقط، وليس داخلها.
يُسمى الرسم البياني G (V, E) بالرسم البياني الثنائي إذا كان من الممكن تحلل مجموعة قمة الرأس V(G) إلى مجموعتين فرعيتين منفصلتين غير فارغتين V1(G) وV2(G) بطريقة تجعل كل حافة e ∈ E (G) لها مفصل أخير في V1(G) ونقطة أخيرة أخرى في V2(G).
يُعرف القسم V = V1 ∪ V2 بالتقسيم الثنائي لـ G.
مثال 1
مثال 2
13. أكمل الرسم البياني الثنائي
أ رسم بياني ثنائي كامل هو رسم بياني ثنائي يتم فيه ربط كل قمة في المجموعة الأولى بكل قمة في المجموعة الثانية بواسطة حافة واحدة بالضبط.
الرسم البياني الثنائي الكامل هو رسم بياني ثنائي كامل.
Complete Bipartite graph = Bipartite graph + Complete graph
مثال
يُعرف الرسم البياني أعلاه باسم K4,3.
14. الرسم البياني للنجوم
الرسم البياني النجمي هو رسم بياني كامل ثنائي الأطراف، حيث يكون لرؤوس n-1 الدرجة 1 ورأس واحد له الدرجة (n-1). يبدو هذا تمامًا مثل النجم حيث ترتبط القمم (n - 1) بقمة مركزية واحدة.
يُشار إلى الرسم البياني النجمي ذو الرؤوس n بالرمز Sن.
مثال
في المثال أعلاه، من الرؤوس n، جميع الرؤوس (n-1) متصلة برأس واحد. وبالتالي، فهو رسم بياني نجمي.
15 الرسم البياني المرجح
الرسم البياني الموزون هو رسم بياني تم تمييز حوافه ببعض الأوزان أو الأرقام.
طول المسار في الرسم البياني المرجح هو مجموع أوزان جميع الحواف في المسار.
مثال
في الرسم البياني أعلاه، إذا كان المسار a -> b -> c -> d -> e -> g فإن طول المسار هو 5 + 4 + 5 + 6 + 5 = 25.
16. رسم بياني متعدد
الرسم البياني الذي توجد فيه حواف متعددة بين أي زوج من القمم أو توجد فيه حواف من قمة إلى نفسها (حلقة) يسمى متعدد الرسم البياني .
مثال
في الرسم البياني أعلاه، ترتبط المجموعة الرأسية B وC بحافتين. وبالمثل، فإن مجموعتي الرأس E وF متصلتان بثلاثة حواف. ولذلك، فهو رسم بياني متعدد.
17. الرسم البياني المستوي
أ رسم بياني مستو هو رسم بياني يمكننا رسمه في مستوى بحيث لا تتقاطع حافتان منه إلا عند الرأس الذي تصادفانه.
مثال
قد لا يبدو الرسم البياني أعلاه مستويًا لأنه يحتوي على حواف متقاطعة مع بعضها البعض. لكن يمكننا إعادة رسم الرسم البياني أعلاه.
الرسومات المستوية الثلاثة للرسم البياني أعلاه هي:
الرسوم البيانية الثلاثة المذكورة أعلاه لا تتكون من حافتين متقاطعتين، وبالتالي فإن جميع الرسوم البيانية المذكورة أعلاه مستوية.
18. الرسم البياني غير المستوي
الرسم البياني الذي ليس رسمًا بيانيًا مستوًا يسمى رسمًا بيانيًا غير مستو. بمعنى آخر، الرسم البياني الذي لا يمكن رسمه بدون وجود زوج من حوافه المتقاطعة على الأقل يُعرف باسم الرسم البياني غير المستوي.
مثال
الرسم البياني أعلاه هو رسم بياني غير مستو.