Graph theory

تتناول نظرية الرسوم البيانية الطوبولوجية دراسة الرسوم البيانية المتعلقة بالطوبولوجيا. وتشمل المواضيع، إلى جانب الرسوم التوضيحية المعطاة من الأعلى إلى الأسفل، ما يلي:

• تضمين رسم بياني في سطح، مع مثال على رسم بياني لهيوود في الطارة؛
• تضمين الرسم البياني الماسي في صفحة واحدة ؛
• عدد التقاطعات ، مع مثال على رسم بياني ثنائي الأجزاء كامل مكون من أربعة وسبعة رؤوس${\displaystyle K_{4,7}}$، مع 18 تقاطعًا (بالنقاط الحمراء)؛ و
• تلوين الخريطة، باستخدام نظرية الألوان الأربعة لتلوين كل ولاية في الولايات المتحدة بشكل مختلف ، مع تجاهل البحيرات والمحيطات.

تتناول نظرية المخططات الطوبولوجية دراسة المخططات كفضاءات طوبولوجية . المخطط في الطوبولوجيا هو مجموعة من المُجَسَّمات البسيطة تُسمى المُعَقَّد البسيط أحادي البُعد . ^{[ 20 ]} يدرس هذا المجال الفرعي تضمين المخطط في التضمين السطحي والتضمين بدون روابط ، والمخططات الجزئية ، وعدد التقاطعات ، وتلوين الخرائط، ومخطط الجهد . ^{[ 21 ]}

تمثيل الرسم البياني على سطح هو تمثيلٌ للرسم البياني حيث ترتبط النقاط بالرؤوس، والأقواس البسيطة بالحواف. ترتبط نقاط النهاية بالحافة، والنقاط بالرؤوس الطرفية. لا تتضمن الأقواس نقاطًا مرتبطة برؤوس أخرى، ولا يتقاطع قوسان أبدًا عند نقطة داخلية لأي منهما. يمكن تعميم تمثيل الرسم البياني إلى التمثيل غير المرتبط، حيث لا ترتبط أي دورتين من الرسم البياني في الفضاء الإقليدي ثلاثي الأبعاد، ^{[ 22 ]} وإلى كتاب ، وهو مجموعة من أنصاف المستويات التي تشترك جميعها في نفس الخط كحدود. ^{[ 23 ]}

يُقال إن الرسم البياني صغير إذا أمكن تكوينه من رسم بياني آخر عن طريق حذف الرؤوس والحواف، وعن طريق انكماش الحواف . ^{[ 22 ]} أول نتيجة لنظرية الرسم البياني الصغير هي من نظرية فاغنر ، التي تنص على أن الرسم البياني المحدود يكون مستويًا إذا وفقط إذا لم يتضمن الرسم البياني الصغير الخاص به الرسم البياني الكامل ذي الرؤوس الخمسة.${\displaystyle K_{5}}$ولا الرسم البياني للمنفعة . ^{[ 24 ]} ومن النتائج ذات الصلة نظرية روبرتسون-سيمور ، التي تنص على وجود قاصر ممنوع لكل خاصية من خصائص الرسوم البيانية التي يتم الحفاظ عليها عن طريق الحذف وانكماش الحواف. ^{[ 25 ]}

يُشير عدد التقاطعات إلى الحد الأدنى لعدد حواف التقاطع في الرسم البياني. وقد نشأت هذه الدراسة من عالم الرياضيات المجري بال توران ، الذي طلب تصميمًا لمصنع يُقلل عدد التقاطعات بين المسارات التي تربط أفران الطوب بمواقع التخزين . ويمكن صياغة هذه المسألة رسميًا على أنها طلب عدد التقاطعات في رسم بياني ثنائي الأجزاء كامل . ^{[ 26 ]}

تلوين الرسم البياني هو عملية منهجية لتسمية عناصر الرسم البياني، ويُطلق عليها تقليديًا اسم "الألوان" . في التلوين، لا يوجد عنصران متجاوران لهما نفس اللون. ويتطلب ذلك الحد الأدنى من الألوان، وهو ما يُعرف بالعدد اللوني. تنص نظرية الألوان الأربعة على أنه لا يلزم أكثر من أربعة ألوان لتلوين مناطق أي خريطة بحيث لا يكون لمنطقتين متجاورتين نفس اللون؛ أي لا تشترك أي منطقتين في حدود مشتركة. ^{[ 27 ]} هذه النظرية أقوى من نظرية الألوان الخمسة . وفي هذا السياق، تُعرف مسألة الأرض والقمر بأنها مسألة مفتوحة حاليًا تتعلق بتوسيع مسألة تلوين الخرائط المستوية، والتي تم حلها باستخدام نظرية الألوان الأربعة.

الرسم البياني للجهد هو رسم بياني موجه تُسمى حوافه بشكل عكسي بعناصر مجموعة . يحدد هذا الرسم البياني الرسم البياني المشتق بإيجاز . ^{[ 28 ]} وهو أيضًا طريقة شائعة لتكوين رسم بياني تغطية . ^{[ 29 ]}

نظرية الرسم البياني الجبرية هي دراسة نظرية الرسم البياني التي تتضمن فروعًا رئيسية من الجبر . ومن أهم فروع الجبر المستخدمة الجبر الخطي ونظرية الزمر .

يُطلق على دراسة نظرية المخططات باستخدام الجبر الخطي اسم نظرية المخططات الطيفية . تركز هذه الدراسة على مصفوفة التجاور ، وهي مصفوفة تمثل المخطط، وعلى طيفها ، الذي يركز على كثير الحدود المميز ، والقيم الذاتية، والمتجهات الذاتية لمصفوفة التجاور المعطاة. كما تركز على مصفوفة لابلاس للمخطط، والتي تتضمن مصفوفة الدرجة ( مصفوفة قطرية تمثل درجة الرأس) ومصفوفة التجاور. ^{[ 30 ]}

تركز نظرية الزمر، ولا سيما زمر التشاكل الذاتي ونظرية الزمر الهندسية ، على عائلات متنوعة من الرسوم البيانية بناءً على التناظر في نظرية الرسوم البيانية الجبرية. ^{[ 31 ]} يشمل هذا التناظر الرسوم البيانية المتناظرة ، والرسوم البيانية المتعدية الرؤوس ، والرسوم البيانية المتعدية الحواف ، والرسوم البيانية المتعدية المسافات ، والرسوم البيانية المنتظمة المسافات ، والرسوم البيانية المنتظمة بقوة . ^{[ 32 ]} تنص نظرية فروشت على أن كل زمرة منتهية هي زمرة تناظرات رسم بياني غير موجه منتهٍ، أو بعبارة أدق، يوجد عدد لا نهائي من الرسوم البيانية البسيطة المتصلة غير المتماثلة بحيث تكون زمرة التشاكل الذاتي لكل منها متماثلة مع زمرة منتهية. ^{[ 33 ]}

تدرس نظرية المخططات الجبرية أيضًا الثوابت الجبرية ، ومتعددة الحدود اللونية ، ومتعددة حدود توت للمخطط، وثابت العقدة . ^{[ 32 ]} ثابت المخطط هو خاصية للمخططات تعتمد فقط على البنية المجردة، بدلاً من تسميات أو رسومات المخطط. متعددة الحدود اللونية هي متعددة حدود تحسب عدد تلوينات المخطط كدالة لعدد الألوان. ^{[ 34 ]} متعددة حدود توت هي متعددة حدود بمتغيرين تتعلق باتصال المخطط. ^{[ 35 ]}

تدرس نظرية الرسم البياني الهندسي الرسم البياني المرسوم بخطوط مستقيمة أو حواف منحنية متصلة ذات خصائص هندسية توافقية. وفي هذه الأمثلة، تدرس نظرية الرسم البياني الهندسي ما يلي:

• الرسم البياني الإقليدي كما في شجرة الامتداد الأدنى الإقليدية (أعلى اليسار)؛
• رسم بياني متعدد الأوجه مع مثال على رسم بياني اثني عشري الأوجه لمجسم اثني عشري منتظم (أعلى اليمين)؛
• الرسم البياني لتقاطع المجموعات الهندسية مثل الرسم البياني للعملة مع تعبئة الدوائر (أسفل اليسار)؛ و
• هندسة الوقوع كما في الرسم البياني لهيوود وهو الرسم البياني لليفي لمستوى فانو (أسفل اليمين).

تركز نظرية الرسم البياني الهندسي على الخصائص التوافقية والهندسية للرسم البياني المرسوم في مستوى ذي حواف مستقيمة أو منحنية متصلة في الفضاء الإقليدي . ^{[ 36 ]} وكجزء من الهندسة المنفصلة والهندسة الحسابية ، تدرس نظرية الرسم البياني الهندسي الرسوم البيانية المستوية ، ^{[ 37 ]} وعلاقتها بالمضلعات المحدبة ذات الأبعاد الأعلى ، ^{[ 38 ]} وتقاطع المجموعات ذات الأشكال الهندسية، ^{[ 39 ]} ومجالات فرعية أخرى من الهندسة، مثل هندسة الوقوع والهندسة الإسقاطية . ^{[ 40 ]}

يُطلق على الرسم البياني المستوي الذي تُمثل رؤوسه نقاطًا، وحوافه قطعًا مستقيمة غير متقاطعة في المستوى الإقليدي، اسم الرسم البياني الخطي المستوي . ويمكن تمثيل أي رسم بياني مستوي كرسم بياني خطي مستوي باستخدام نظرية فاري . يُعد الرسم البياني الخطي المستوي حالة خاصة من الرسم البياني الإقليدي. يسمح الرسم البياني الإقليدي بأن تكون أطوال حوافه مساوية للمسافة الإقليدية بين طرفيه. ومن مفاهيمه: الشجرة الممتدة الإقليدية الدنيا، التي تُعنى بتقليل الطول الإجمالي للقطع المستقيمة لعدد محدود من النقاط في أي فضاء إقليدي ؛ ومسألة هادويجر-نيلسون، التي تُعنى بإيجاد أقل عدد من مستويات التلوين بحيث لا تتشابه أي نقطتين على مسافة وحدة واحدة من بعضهما البعض في اللون؛ ومسألة أقصر مسار، التي تُعنى بإيجاد مسار بين رأسين في رسم بياني يُقلل مجموع القيم المُخصصة لحوافه. ^{[ 37 ]}

الرسم البياني المرئي هو رسم بياني تمثل رؤوسه مواقع النقاط، بينما تمثل حوافه الاتصالات المرئية. في المضلع البسيط ، حيث لا تتقاطع حوافه مع نفسها ولا تحتوي على ثقوب، تتصل رؤوس الرسم البياني المرئي بحواف تمثل أضلاع المضلع وأقطاره. تُعرَّف الرؤوس بأنها مواقع النقاط. ^{[ 41 ]} الرسم البياني متعدد السطوح هو رسم بياني غير موجه يشكل رؤوس وحواف متعدد سطوح محدب ثلاثي الأبعاد . ولتحقيق ذلك، يجب أن يستوفي هذا الرسم البياني متطلبات نظرية شتاينيتز ، التي تنص على أن كل متعدد سطوح محدب هو رسم بياني مستوٍ متصل بثلاثة رؤوس . ويبقى الرسم البياني المستوي متصلاً حتى عند إزالة أي رأسين منه. ^{[ 42 ]}

الرسم البياني للتقاطع هو رسم بياني يرتبط فيه كل رأس بمجموعة، وتتصل الرؤوس بالحواف عندما يكون للمجموعات المتناظرة تقاطع غير فارغ . ^{[ 39 ]} يُمثل كل رأس بمجموعة، ويتصل كل رأسين ببعضهما. بالتالي، يمكن تمثيل الرسم البياني للتقاطع للمجموعات المنتهية بأصغر عدد من العناصر المطلوبة، والمعروف باسم عدد التقاطع . يمكن أن يكون الرسم البياني الناتج هندسيًا عندما تكون المجموعات أشكالًا هندسية. على سبيل المثال، الرسم البياني للتقاطع بين القطع المستقيمة في بُعد واحد هو رسم بياني فاصل . الرسم البياني للتقاطع بين الأقراص الوحدوية في المستوى هو رسم بياني للأقراص الوحدوية . تقاطع رصّ الدوائر هو رسم بياني للعملة ، حيث يُمثل كل رأس وحافة دائرة، وكل زوج من الدوائر المتماسّة؛ وبحسب نظرية كوبي-أندرييف-ثورستون، فإن الرسوم البيانية للتقاطع بين الدوائر غير المتقاطعة هي بالضبط الرسوم البيانية المستوية. ^{[ 43 ]} تنص نظرية شاينرمان على أنه يمكن تمثيل كل رسم بياني مستوٍ على أنه رسم بياني لتقاطع القطع المستقيمة في المستوى. ^{[ 44 ]}

يُعد مخطط ليفي مخططًا ثنائي الأجزاء يرتبط ببنية الوقوع والتكوين الإسقاطي . ^{[ 40 ]}

بتطبيق ذلك على تمثيل المعلومات ، ينشأ مجال فرعي آخر في نظرية الرسوم البيانية يُعرف باسم رسم الرسوم البيانية ، والذي يُصوّر تمثيلًا مرئيًا للرسم البياني. غالبًا ما تُرسَم هذه الرسوم البيانية على شكل مخططات العقد والروابط، حيث تُمثَّل رؤوس الرسم البياني بأقراص أو مربعات أو تسميات نصية، بينما تُمثَّل حوافه بقطع مستقيمة أو خطوط متعددة أو منحنيات في المستوى الإقليدي. ^{[ 45 ]} تتضمن العديد من تعريفات رسومات الرسوم البيانية، القائمة على معايير الجودة، عدد التقاطعات، ^{[ 46 ]} والمساحة ، وعرض التناظر عند إيجاد مشكلة التماثل الذاتي لمجموعة الرسم البياني، ^{[ 47 ]} وتقليل الانحناء ، والدقة الزاوية ، ^{[ 48 ]} وعدد الميل . ^{[ 48 ]} من أدوات رسم الرسوم البيانية: تعبئة الدوائر، ^{[ 49 ]} ورسم بياني التقاطع، وغيرها من طرق تمثيل مصفوفة التجاور.

نظرية الرسوم البيانية المتطرفة هي فرع من الرياضيات يقع عند تقاطع التوافقية المتطرفة ونظرية الرسوم البيانية. يدرس هذا المجال العدد الأقصى لحواف الرسم البياني، والمعروف بالعدد المتطرف. ^{[ 50 ]} وقد انطلقت هذه النظرية من نظرية مانتل حول العدد المتطرف للرسم البياني الخالي من المثلثات . ثم عممت نظرية توران نظرية مانتل لتشمل أي رسم بياني غير موجه لا يحتوي على رسم بياني فرعي كامل بحجم معين. وقد عُممت نظرية توران بواسطة نظرية إردوش-ستون ، والتي تُعرف أحيانًا باسم "النظرية الأساسية لنظرية الرسوم البيانية المتطرفة". ^{[ 51 ]}

تدرس نظرية الرسوم البيانية المتطرفة أيضًا مشكلة الرسوم البيانية الفرعية المحظورة ، وكثافة التماثل ، ومبرهنة سيميريدي للانتظام . تقترح مشكلة الرسوم البيانية الفرعية المحظورة إيجاد العدد المتطرف للرسم البياني مع${\displaystyle n}$رؤوس بحيث لا يوجد رسم بياني فرعي متماثل مع الرسم البياني. ^{[ 52 ]} كثافة التماثل هي مُعامل يتعلق بتماثل الرسم البياني . قد تشير الكثافة إلى احتمال أن يكون التطبيق من رؤوس رسم بياني إلى رؤوس رسم بياني آخر مُختار عشوائيًا بشكل منتظم تماثلًا للرسم البياني. يعني التماثل وجود تطبيق بين رسمين بيانيين يحافظ على بنيتهما، أو بشكل مكافئ، دالة بين مجموعات رؤوس الرسمين البيانيين تُسقط الرؤوس المتجاورة على بعضها البعض. ^{[ 53 ]} تنص مبرهنة سيميريدي للانتظام على أنه يمكن تقسيم الرسم البياني إلى عدد محدود من الأجزاء بحيث تكون الحواف بين الأجزاء${\displaystyle \varepsilon }$-عادي.

تركز نظرية الرسوم البيانية العشوائية على الرسوم البيانية باستخدام الأساليب الاحتمالية . وقد أسس هذا المجال الفرعي عالما الرياضيات المجريان بول إردوش وألفريد ريني ، اللذان أنتجت نماذجهما رسومًا بيانية عشوائية، تُعرف باسم نموذج إردوش-ريني . ^{[ 19 ]}

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

• الشجرة الممتدة المنتظمة هي شجرة ممتدة لرسم بياني معين، حيث يكون احتمال اختيار كل شجرة مختلفة متساوياً . وكونها شجرة ممتدة يعني أن الرسم البياني الفرعي هو شجرة تشمل جميع رؤوس الرسم البياني. يمكن توليد الشجرة الممتدة المنتظمة باستخدام طريقة المسار البسيط العشوائي المعروفة باسم المشي العشوائي المحذوف الحلقات ، وذلك بأخذ مسار عشوائي على الرسم البياني المعطى ومحو الحلقات الناتجة عن هذا المسار. ^{[ 54 ]}
• عملية التفرع ، نموذج للسكان حيث يكون لكل فرد عدد عشوائي من الأطفال
• شجرة براونية ، وهي بنية شجرية كسورية تتكون من عمليات تجميع محدودة الانتشار
• الشجرة الثنائية العشوائية هي شجرة ثنائية يتم اختيارها عشوائيًا من توزيع احتمالي معين على الأشجار الثنائية. ^{[ 55 ]} ويشمل ذلك الأشجار التي تتشكل بترتيبات إدخال عشوائية، ^{[ 56 ]} والأشجار التي تتوزع بشكل منتظم بعدد معين من العقد.
• الغابة العشوائية ، مصنف للتعلم الآلي يعتمد على اختيار مجموعات فرعية عشوائية من المتغيرات لكل شجرة واستخدام مخرجات الشجرة الأكثر تكرارًا كتصنيف شامل.
• الشجرة الممتدة الدنيا العشوائية هي شجرة ممتدة لرسم بياني يتم تشكيلها عن طريق اختيار أوزان حواف عشوائية واستخدام الشجرة الممتدة الدنيا لتلك الأوزان. ^{[ 57 ]}
• شجرة تكرارية عشوائية ، أشجار ذات تسميات متزايدة، والتي يمكن توليدها باستخدام قاعدة نمو عشوائية بسيطة.
• استكشاف سريع للشجرة العشوائية ، وهو نمط ملء الفراغ الكسري المستخدم كهيكل بيانات للبحث في المساحات عالية الأبعاد.
• شجرة البحث الثنائية العشوائية (Treap )، هي بنية بيانات تستخدم خيارات عشوائية لمحاكاة شجرة ثنائية عشوائية لتسلسلات التحديث غير العشوائية.

في علوم الحاسوب ، تُعدّ البنى المرتبطة " السببية " و"غير السببية" رسومًا بيانية تُستخدم لتمثيل شبكات الاتصال، وتنظيم البيانات، والأجهزة الحاسوبية، وتدفق العمليات الحسابية، وما إلى ذلك. على سبيل المثال، يمكن تمثيل بنية روابط موقع ويب برسم بياني موجه، حيث تمثل الرؤوس (العُقد) صفحات الويب، وتمثل الحواف الموجهة الروابط من صفحة إلى أخرى. ويمكن اتباع نهج مماثل في مشاكل وسائل التواصل الاجتماعي ^{[ 62 ]} ، والسفر، وعلم الأحياء، وتصميم رقائق الحاسوب، ورسم خرائط تطور الأمراض التنكسية العصبية ^{[ 63 ] [ 64 ]} ، والعديد من المجالات الأخرى. ولذلك، يُعدّ تطوير خوارزميات للتعامل مع الرسوم البيانية ذا أهمية بالغة في علوم الحاسوب. غالبًا ما يتمّ صياغة تحويل الرسوم البيانية وتمثيله بواسطة أنظمة إعادة كتابة الرسوم البيانية . وتُكمّل أنظمة تحويل الرسوم البيانية ، التي تركز على معالجة الرسوم البيانية في الذاكرة وفقًا لقواعد محددة، قواعد بيانات الرسوم البيانية المُصممة لتخزين البيانات ذات البنية الرسومية بشكل آمن ومستدام ، والاستعلام عنها .

أثبتت أساليب نظرية الرسوم البيانية، بأشكالها المختلفة، فائدتها الكبيرة في علم اللغة ، نظرًا لأن اللغة الطبيعية غالبًا ما تتناسب مع البنية المنفصلة. تقليديًا، يتبع بناء الجملة والدلالات التركيبية بنىً شجرية، تكمن قوتها التعبيرية في مبدأ التركيبية ، المُنمذج في رسم بياني هرمي. أما الأساليب المعاصرة، مثل قواعد بنية العبارة الموجهة بالرأس، فتُنمذج بناء جملة اللغة الطبيعية باستخدام بنى السمات المُصنفة ، وهي رسوم بيانية موجهة غير دورية . في الدلالات المعجمية ، وخاصةً عند تطبيقها على الحواسيب، يُصبح نمذجة معنى الكلمة أسهل عندما تُفهم الكلمة من خلال الكلمات ذات الصلة؛ ولذلك تُعد الشبكات الدلالية مهمة في علم اللغة الحاسوبي . مع ذلك، لا تزال أساليب أخرى في علم الأصوات (مثل نظرية الأمثلية ، التي تستخدم الرسوم البيانية الشبكية ) وعلم الصرف (مثل صرف الحالة المحدودة، باستخدام محولات الحالة المحدودة ) شائعة في تحليل اللغة كرسم بياني. في الواقع، أدت فائدة هذا المجال من الرياضيات لعلم اللغويات إلى ظهور منظمات مثل TextGraphs ، بالإضافة إلى العديد من مشاريع "الشبكة"، مثل WordNet و VerbNet وغيرها.

تُستخدم نظرية المخططات أيضًا لدراسة الجزيئات في الكيمياء والفيزياء . ففي فيزياء المادة المكثفة ، يمكن دراسة البنية ثلاثية الأبعاد للهياكل الذرية المُحاكاة المعقدة كميًا من خلال جمع إحصاءات حول خصائص نظرية المخططات المتعلقة بطوبولوجيا الذرات. كما أن " مخططات فاينمان وقواعد الحساب تُوجز نظرية المجال الكمومي بشكل وثيق الصلة بالأرقام التجريبية المراد فهمها". ^{[ 65 ]} في الكيمياء، يُشكل المخطط نموذجًا طبيعيًا للجزيء، حيث تُمثل الرؤوس الذرات والحواف الروابط . ويُستخدم هذا النهج بشكل خاص في المعالجة الحاسوبية للهياكل الجزيئية، بدءًا من برامج تحرير المواد الكيميائية وصولًا إلى البحث في قواعد البيانات. في الفيزياء الإحصائية ، يمكن للمخططات تمثيل الروابط المحلية بين الأجزاء المتفاعلة في النظام، بالإضافة إلى ديناميكيات العمليات الفيزيائية على هذه الأنظمة. وبالمثل، في علم الأعصاب الحاسوبي، يمكن استخدام الرسوم البيانية لتمثيل الروابط الوظيفية بين مناطق الدماغ التي تتفاعل لتكوين عمليات معرفية متنوعة، حيث تمثل الرؤوس مناطق مختلفة من الدماغ، وتمثل الحواف الروابط بين تلك المناطق. تلعب نظرية الرسوم البيانية دورًا هامًا في النمذجة الكهربائية للشبكات الكهربائية، حيث تُربط الأوزان بمقاومة أجزاء الأسلاك للحصول على الخصائص الكهربائية لهياكل الشبكة. ^{[ 66 ]} تُستخدم الرسوم البيانية أيضًا لتمثيل القنوات الدقيقة للوسائط المسامية ، حيث تمثل الرؤوس المسام، وتمثل الحواف القنوات الأصغر التي تربط المسام. تستخدم نظرية الرسوم البيانية الكيميائية الرسم البياني الجزيئي كوسيلة لنمذجة الجزيئات. تُعد الرسوم البيانية والشبكات نماذج ممتازة لدراسة وفهم التحولات الطورية والظواهر الحرجة. يؤدي إزالة العقد أو الحواف إلى تحول حرج حيث تنقسم الشبكة إلى مجموعات صغيرة، وهو ما يُدرس على أنه تحول طوري. يُدرس هذا الانهيار من خلال نظرية الترشيح . ^{[ 67 ]}

تُستخدم نظرية الرسوم البيانية على نطاق واسع في علم الاجتماع ، على سبيل المثال، لقياس مكانة الفاعلين أو لاستكشاف انتشار الشائعات ، لا سيما من خلال استخدام برامج تحليل الشبكات الاجتماعية . وتندرج تحت مظلة الشبكات الاجتماعية أنواع عديدة من الرسوم البيانية. ^{[ 69 ]} فرسوم التعارف والصداقة تصف ما إذا كان الناس يعرفون بعضهم بعضًا. أما رسوم التأثير فتُحدد ما إذا كان بإمكان أشخاص معينين التأثير على سلوك الآخرين. وأخيرًا، تُحدد رسوم التعاون ما إذا كان شخصان يعملان معًا بطريقة معينة، مثل التمثيل معًا في فيلم.

وبالمثل، تُعدّ نظرية الرسوم البيانية مفيدة في علم الأحياء وجهود الحفاظ على البيئة، حيث يُمثّل كل رأس منطقةً تتواجد فيها أنواعٌ مُحدّدة (أو تسكنها)، بينما تُمثّل الحواف مسارات الهجرة أو الحركة بين هذه المناطق. وتُعدّ هذه المعلومات بالغة الأهمية عند دراسة أنماط التكاثر أو تتبّع انتشار الأمراض والطفيليات، أو كيفية تأثير التغييرات في حركة الأنواع على الأنواع الأخرى.

تُستخدم الرسوم البيانية بشكل شائع في البيولوجيا الجزيئية وعلم الجينوم لنمذجة وتحليل مجموعات البيانات ذات العلاقات المعقدة. على سبيل المثال، تُستخدم الطرق القائمة على الرسوم البيانية غالبًا لتجميع الخلايا في أنواع خلوية محددة في تحليل النسخ الجيني للخلايا المفردة . ومن استخداماتها الأخرى نمذجة الجينات أو البروتينات في مسار حيوي ودراسة العلاقات بينها، مثل المسارات الأيضية وشبكات تنظيم الجينات. ^{[ 70 ]} كما تُمثل الأشجار التطورية والشبكات البيئية والتجميع الهرمي لأنماط التعبير الجيني كهياكل رسوم بيانية.

تُستخدم نظرية الرسم البياني أيضًا في علم الاتصال العصبي ؛ ^{[ 71 ]} يمكن اعتبار الجهاز العصبي بمثابة رسم بياني، حيث تكون العقد هي الخلايا العصبية والحواف هي الروابط بينها.

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

تُمثَّل الرسوم البيانية عادةً بصريًا برسم نقطة أو دائرة لكل رأس، ورسم خط بين رأسين إذا كانا متصلين بحافة. ​​إذا كان الرسم البياني موجهًا، يُشار إلى الاتجاه برسم سهم. وإذا كان الرسم البياني مُثقَّلًا، يُضاف الوزن إلى السهم.

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

كان لعمل دبليو تي توت الرائد تأثير كبير على موضوع رسم الرسوم البيانية. ومن بين إنجازاته الأخرى، أنه أدخل استخدام أساليب الجبر الخطي للحصول على رسومات بيانية.

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

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

يُعدّ التمثيل الجدولي مناسبًا جدًا للتطبيقات الحاسوبية. توجد طرق مختلفة لتخزين الرسوم البيانية في نظام الحاسوب. يعتمد هيكل البيانات المستخدم على كلٍّ من بنية الرسم البياني والخوارزمية المستخدمة لمعالجته. نظريًا، يمكن التمييز بين هياكل القوائم والمصفوفات، ولكن في التطبيقات العملية، غالبًا ما يكون الهيكل الأمثل مزيجًا من كليهما. تُفضّل هياكل القوائم عادةً للرسوم البيانية المتفرقة نظرًا لمتطلباتها المنخفضة من الذاكرة. من ناحية أخرى، توفر هياكل المصفوفات وصولًا أسرع لبعض التطبيقات، ولكنها قد تستهلك كميات هائلة من الذاكرة. تُعدّ تطبيقات هياكل المصفوفات المتفرقة الفعّالة على بنى الحواسيب المتوازية الحديثة موضوعًا للبحث الحالي. ^{[ 72 ]}

تتضمن هياكل القوائم قائمة الحواف ، وهي عبارة عن مصفوفة من أزواج الرؤوس، وقائمة التجاور ، التي تسرد بشكل منفصل جيران كل رأس: ومثل قائمة الحواف، يحتوي كل رأس على قائمة بالرؤوس المجاورة له.

تتضمن هياكل المصفوفات مصفوفة الوقوع ، وهي مصفوفة من الأصفار والآحاد، حيث تمثل صفوفها الرؤوس وأعمدتها الحواف، ومصفوفة التجاور ، حيث تُفهرس الصفوف والأعمدة بالرؤوس. في كلتا الحالتين، يشير الرقم 1 إلى عنصرين متجاورين، بينما يشير الرقم 0 إلى عنصرين غير متجاورين. تشير مصفوفة الدرجة إلى درجة الرؤوس. مصفوفة لابلاس هي شكل مُعدّل من مصفوفة التجاور، حيث تتضمن معلومات حول درجات الرؤوس، وهي مفيدة في بعض الحسابات، مثل نظرية كيرشوف حول عدد الأشجار الممتدة للرسم البياني. مصفوفة المسافة ، مثل مصفوفة التجاور، تُفهرس صفوفها وأعمدتها بالرؤوس، ولكن بدلاً من احتواء كل خلية على 0 أو 1، فإنها تحتوي على طول أقصر مسار بين رأسين.

يوجد عدد كبير من المؤلفات حول التعداد البياني : وهي مشكلة عدّ الرسوم البيانية التي تستوفي شروطًا محددة. ويمكن الاطلاع على بعض هذه الأعمال في كتاب هاراري وبالمر (1973).

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

• يُطلق على إيجاد أكبر رسم بياني فرعي كامل اسم مشكلة الزمرة (NP-complete).

تُعدّ مسألة تماثل الرسوم البيانية حالةً خاصةً من حالات تماثل الرسوم البيانية الجزئية . وتطرح هذه المسألة سؤالاً حول ما إذا كان رسمان بيانيان متماثلين. ولا يُعرف ما إذا كانت هذه المسألة من فئة NP-complete، ولا ما إذا كان من الممكن حلّها في وقت متعدد الحدود.

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

• يُطلق على إيجاد أكبر رسم بياني فرعي مستحث بدون حواف أو مجموعة مستقلة اسم مشكلة المجموعة المستقلة (NP-complete).

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

• يكون الرسم البياني مستوياً إذا لم يحتوي كجزئ صغير على الرسم البياني الثنائي الكامل K _3,3 (انظر مسألة الأكواخ الثلاثة ) ولا الرسم البياني الكامل K ₅ .

تُعدّ مشكلة احتواء التقسيم مشكلةً مشابهة، وهي إيجاد رسم بياني ثابت كتقسيم لرسم بياني مُعطى. يُعرَّف التقسيم أو التشاكل المتماثل للرسم البياني بأنه أي رسم بياني يتم الحصول عليه بتقسيم بعض الحواف (أو عدم تقسيم أي منها). يرتبط احتواء التقسيم بخصائص الرسم البياني مثل التسطح . على سبيل المثال، تنص نظرية كوراتوفسكي على ما يلي:

• يكون الرسم البياني مستوياً إذا لم يحتوي كتقسيم فرعي على الرسم البياني الثنائي الكامل K _3,3 ولا الرسم البياني الكامل K ₅ .

مشكلة أخرى في احتواء التقسيم الفرعي هي تخمين كيلمانز-سيمور :

• كل رسم بياني متصل بخمسة رؤوس وغير مستوٍ يحتوي على تقسيم فرعي للرسم البياني الكامل ذي الخمسة رؤوس K ₅ .

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

• فرضية إعادة البناء

تتعلق العديد من المسائل والنظريات في نظرية المخططات بطرق تلوين المخططات المختلفة. عادةً، يكون الهدف هو تلوين المخطط بحيث لا يكون لأي رأسين متجاورين نفس اللون، أو مع قيود مماثلة. يمكن أيضًا النظر في تلوين الحواف (ربما بحيث لا يكون لأي حافتين متطابقتين نفس اللون)، أو غيرها من الاختلافات. من بين النتائج والتخمينات الشهيرة المتعلقة بتلوين المخططات ما يلي:

• نظرية الألوان الأربعة
• نظرية الرسم البياني المثالي القوي
• تخمين إردوس-فابر-لوفاسز
• تخمين التلوين الكلي ، ويسمى أيضاً تخمين بهزاد (غير محلول )
• تخمين تلوين القوائم (غير محلول)
• تخمين هادويغر (نظرية الرسم البياني) (غير محلول)

تُعنى نظريات نمذجة القيود بعائلات من الرسوم البيانية الموجهة المرتبطة بترتيب جزئي . في هذه التطبيقات، تُرتّب الرسوم البيانية حسب درجة التحديد، ما يعني أن الرسوم البيانية الأكثر تقييدًا - والتي تتميز بدرجة تحديد أعلى وبالتالي تحتوي على قدر أكبر من المعلومات - تُدمج ضمن الرسوم البيانية الأكثر عمومية. تشمل العمليات بين الرسوم البيانية تقييم اتجاه علاقة الدمج بين رسمين بيانيين، إن وُجدت، وحساب توحيد الرسم البياني. يُعرَّف توحيد رسمين بيانيين للمدخلات بأنه الرسم البياني الأكثر عمومية (أو حسابه) المتوافق مع المدخلات (أي الذي يحتوي على جميع المعلومات فيها)، إن وُجد مثل هذا الرسم البياني؛ وتُعرف خوارزميات توحيد فعّالة.

بالنسبة لأطر القيود التركيبية البحتة ، يُعد توحيد الرسوم البيانية دالة الإرضاء والدمج الكافية. ومن التطبيقات المعروفة إثبات النظريات تلقائيًا ونمذجة تفصيل البنية اللغوية .

• مشكلة المسار الهاميلتوني
• شجرة ذات امتدادات دنيا
• مشكلة فحص المسار (وتسمى أيضاً "مشكلة ساعي البريد الصيني")
• جسور كونيغسبرغ السبعة
• مشكلة أقصر مسار
• شجرة شتاينر
• مشكلة المنازل الثلاثة
• مسألة البائع المتجول (مسألة صعبة من نوع NP)

هناك العديد من المشاكل التي تنشأ بشكل خاص من التطبيقات التي لها علاقة بمفاهيم مختلفة للتدفقات في الشبكات ، على سبيل المثال:

• نظرية التدفق الأقصى والقطع الأدنى

• مشكلة حارس المتحف

قد تشير مشاكل التغطية في الرسوم البيانية إلى مشاكل تغطية المجموعات المختلفة على مجموعات فرعية من الرؤوس / الرسوم البيانية الفرعية.

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

يُعرَّف التفكيك بأنه تقسيم مجموعة حواف الرسم البياني (مع عدد كافٍ من الرؤوس لكل جزء من التقسيم)، وله طيف واسع من المسائل. غالبًا ما تتمثل المسألة في تفكيك الرسم البياني إلى رسوم بيانية فرعية متماثلة مع رسم بياني ثابت؛ على سبيل المثال، تفكيك رسم بياني كامل إلى دورات هاميلتونية. تُحدد مسائل أخرى عائلة من الرسوم البيانية التي ينبغي تفكيك رسم بياني مُعطى إليها، على سبيل المثال، عائلة من الدورات، أو تفكيك رسم بياني كامل K _{_n} إلى n − 1 شجرة محددة، تحتوي على 1، 2، 3، ...، n − 1 حافة على التوالي.

تتضمن بعض مسائل التفكيك المحددة والمسائل المماثلة التي تمت دراستها ما يلي:

• التشعب الشجري ، وهو تحلل إلى أقل عدد ممكن من الغابات
• غلاف مزدوج دائري ، مجموعة من الدورات تغطي كل حافة مرتين بالضبط
• تلوين الحواف ، وهو عملية تقسيم إلى أقل عدد ممكن من التطابقات
• تحليل الرسم البياني ، وهو عملية تقسيم الرسم البياني المنتظم إلى رسوم بيانية فرعية منتظمة ذات درجات معينة.

تتضمن العديد من المسائل تحديد خصائص عناصر فئات مختلفة من الرسوم البيانية. فيما يلي بعض الأمثلة على هذه المسائل:

• تعداد أعضاء الفصل
• توصيف فئة من حيث البنى الفرعية المحظورة
• تحديد العلاقات بين الفئات (على سبيل المثال، هل تشير إحدى خصائص الرسوم البيانية إلى خاصية أخرى)
• إيجاد خوارزميات فعالة لتحديد الانتماء إلى فئة معينة
• إيجاد تمثيلات لأعضاء فئة معينة

• هارتمان، ألكسندر ك.؛ ويغت، مارتن (2005). "مقدمة في الرسوم البيانية". التحولات الطورية في مسائل التحسين التوافقي: الأساسيات والخوارزميات والميكانيكا الإحصائية . وايلي. ص 25-66 . arXiv : cond-mat/0602129 . doi : 10.1002/3527606734.ch3 . ISBN  978-3-527-60673-3.
• الرسوم البيانية الموجهة: النظرية والخوارزميات والتطبيقات 2007، من تأليف يورغن بانغ-جنسن وغريغوري غوتين
• نظرية الرسم البياني، بقلم راينهارد ديستل