ماذا تدرس نظرية الرسم البياني؟ المشاكل الكلاسيكية لنظرية الرسم البياني وحلولها

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

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

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

تعمل الرسوم البيانية كوسيلة ملائمة لوصف العلاقات بين الكائنات. لقد استخدمنا سابقًا الرسوم البيانية كوسيلة لتمثيل العلاقات الثنائية المحدودة بشكل مرئي.

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

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

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

• التعاريف الأساسية

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

• طرق العرض

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

• الأشجار

  التعريف 5.5. الشجرة غير الموجهة عبارة عن رسم بياني غير موجه متصل وغير دوري. التعريف 5.6. الشجرة الموجهة عبارة عن رسم بياني موجه غير كفاف حيث لا تكون نصف درجة أي قمة أكبر من 1 ويوجد رأس واحد بالضبط، يسمى جذر الشجرة الموجهة، ونصف درجة تساوي 0.

• شجرة ممتدة ذات وزن أقل

  تُعرف المشكلة التالية في نظرية الرسم البياني باسم مشكلة شتاينر: يتم إعطاء نقاط n على المستوى؛ تحتاج إلى توصيلها بقطاعات مستقيمة بحيث يكون الطول الإجمالي للقطاعات في حده الأدنى.

• طرق لاجتياز قمم الرسم البياني بشكل منهجي

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

• مشكلة المسار في الرسوم البيانية الموجهة الموزونة

• الرسم البياني التماثل

  بالنسبة للرسم البياني الموجه (V، E)، يمكن اعتبار المجموعة E من الأقواس بمثابة رسم بياني لعلاقة الوصول المباشر الثنائية المحددة في مجموعة القمم. في الرسم البياني غير الموجه (V، E)، مجموعة الحواف E هي مجموعة الأزواج غير المرتبة. لكل زوج غير مرتب (u، v) ∈ E يمكننا أن نفترض أن القمم u و v مرتبطتان بعلاقة ثنائية متماثلة p، أي. (u, v) ∈ Р و (v, u) ∈ Р.

• الفرز الطوبولوجي

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

• عناصر السيكلوماتيكية

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

نظرية الرسم البياني هي فرع من الرياضيات المستخدمة في علوم الكمبيوتر والبرمجة والاقتصاد والخدمات اللوجستية والكيمياء.

ما هو الرسم البياني

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

المفاهيم الأساسية لنظرية الرسم البياني

الرسم البياني الموجه أو الرسم البياني الموجه (انظر الشكل أدناه) له حواف موجهة، تسمى الأقواس، ويتم تصويرها بواسطة الأسهم. يمكن الإشارة إلى القوس من خلال زوج مرتب من القمم التي يربطها، بداية ونهاية.

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

إذا كانت القمم a وb هي نهايات حافة (أو بداية ونهاية قوس) من الرسم البياني، فإن القمم a وb يقال أنها تقع على هذه الحافة (القوس)، وتكون الحافة (القوس) أيضًا الحادث إلى القمم أ و ب. إذا كانت القمم a وb هي نهايات الحافة، فإنهما (a وb) يطلق عليهما اسم متجاورين.

في أغلب الأحيان، نعتبر الرسوم البيانية التي تكون حوافها من نوع واحد - سواء كانت موجهة أم لا.

إذا كانت الحواف لها نفس البداية والنهاية، فإنها تسمى حواف متعددة، ويسمى الرسم البياني الذي توجد فيه رسمًا متعددًا.

تستخدم نظرية الرسم البياني أيضًا مفهوم "الحلقة" - وهي الحافة التي تخرج وتذهب إلى نفس الرأس. الرسم البياني الذي يحتوي على حلقات يسمى الرسم الكاذب.

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

تتميز كل قمة من digraph بما يلي:

• نصف درجة النتيجة. هذا هو عدد الأقواس الخارجة منه.
• نصف درجة النهج. هذا هو عدد الأقواس التي تدخل قمة معينة.

مجموع نصف درجات إدخال الرسم البياني، وكذلك مجموع نصف درجات النتيجة، يساوي إجمالي عدد أقواس الرسم البياني.

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

تسمى القمة ذات الدرجة 0 معزولة.

الرأس المعلق هو رأس من الدرجة 1.

تسمي نظرية الرسم البياني الرسم البياني الفارغ الذي لا توجد فيه حواف. الرسم البياني الكامل هو رسم بياني عادي تكون فيه أي رأسين متجاورتين.

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

الرسوم البيانية: التماثل

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

المسارات والدورات

المسار في الرسم البياني غير الموجه أو غير الموجه هو عبارة عن سلسلة من الحواف، حيث تبدأ كل حافة تالية من الرأس حيث تنتهي الحافة السابقة. المسار البسيط هو المسار الذي تكون فيه جميع القمم، باستثناء البداية والنهاية، مختلفة وحوافها مختلفة. الدورة في الرسم البياني هي مسار تتطابق رؤوس بدايته ونهايته ويتضمن حافة واحدة على الأقل. الدورة في الرسم البياني غير الموجه هي مسار يحتوي على ثلاث حواف مميزة على الأقل. وفي الشكل الثاني تكون الدورة مثلاً المسار (3، 1)، (6، 3)، (1، 6).

تُستخدم نظرية الرسم البياني في البرمجة لإنشاء الرسوم البيانية للخوارزميات.

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

خوارزمية لتحديد دورة أويلر مباشرة.
[فلوري]. دعونا نفكر في رسم بياني متعدد متصل G، جميع رؤوسه لها درجة متساوية، وسنحاول رسمها بضربة واحدة، دون اللجوء إلى التصحيحات في الجزء المرسوم بالفعل من المسار أثناء عملية البناء. يكفي الالتزام بالقاعدة التالية:
1 نخرج من قمة تعسفية أ؛ نقوم بشطب كل حافة مرت.
2 نحن لا نسير أبدًا على طول هذه الحافة، والتي تعتبر في الوقت الحالي برزخًا (أي، عند إزالتها، ينقسم الرسم البياني المتكون من الحواف غير المتقاطعة إلى مكونين متصلين لكل منهما حافة واحدة على الأقل)،

باتباع هذه القاعدة، سنكون دائمًا في وضع مناسب، لأنه عندما نكون عند x = a، فإن الرسم البياني (للحواف غير المتقاطعة) له رأسان من الدرجة الفردية: x وa؛ إذا تجاهلنا القمم المعزولة، فسوف يتبقى لدينا رسم بياني متصل، والذي، بموجب النظرية 1، لديه سلسلة أويلر تبدأ من x.

محتوى
مقدمة
الفصل 1. التعاريف الأساسية
المجموعات والتعيينات متعددة القيم
رسم بياني. المسارات والملامح
الدوائر والدورات
الفصل الثاني: دراسة أولية لشبه الانتظام
شبه النظام المحدد بواسطة الرسم البياني
الرسم البياني الاستقرائي والقواعد
الفصل 3. الوظيفة الترتيبية والوظيفة
جراندي لرسم بياني لانهائي
اعتبارات عامة بخصوص الرسوم البيانية اللانهائية
دالة ترتيبية
وظائف جراندي
العمليات على الرسوم البيانية
الفصل 4. الأعداد الأساسية لنظرية الرسم البياني
رقم سيكلوماتيك
رقم لوني
رقم الاستقرار الداخلي
رقم الاستقرار الخارجي
الفصل 5. حبات الرسم البياني
نظريات الوجود والتفرد
تطبيق لوظائف جراندي
الفصل 6. ألعاب الرسم البياني
لعبة نيم
تعريف عام للعبة (بالمعلومات الكاملة)
الاستراتيجيات
الفصل 7. مشكلة أقصر مسار
العمليات على مراحل بعض التعميمات
الفصل 8. شبكات النقل
مشكلة التدفق الأقصى مشكلة التدفق الأقل
مشكلة التدفق المتوافق مع القيمة المحددة
شبكات النقل التي لا نهاية لها
الفصل 9. نظرية نصف القوى
نصف درجة الخروج والدخول
الفصل 10. مطابقة رسم بياني بسيط
مشكلة المطابقة القصوى
نقص الرسم البياني البسيط
الخوارزمية المجرية
التعميم على الحالة اللانهائية
تطبيق لنظرية المصفوفة
الفصل 11. العوامل
مسارات هاملتونية وخطوط هاميلتونية
العثور على عامل
العثور على رسم بياني جزئي مع نصف درجة معينة
الفصل 12. مراكز الرسم البياني
المراكز
نصف القطر
الفصل 13. قطر الرسم البياني المتصل بقوة
الخصائص العامة للرسوم البيانية المرتبطة بقوة بدون حلقات
قطر الدائرة
الفصل 14. مصفوفة مجاورة الرسم البياني
تطبيق عمليات المصفوفة التقليدية
مشاكل العد
مشكلة القائد
استخدام العمليات المنطقية
الفصل 15. مصفوفات الحوادث
مصفوفات أحادية تماما
أنظمة أحادية تماما
المصفوفات السيكلوماتيكية
الفصل 16. الأشجار وأشجار الأجداد
الأشجار
البحث التحليلي
الأشجار الكبرى
الفصل 17. مشكلة أويلر
دورات أويلر ملامح أويلر
الفصل 18. مطابقة الرسم البياني التعسفي
نظرية الدائرة المتناوبة
العثور على رسم بياني جزئي مع درجات قمة معينة
مطابقة مثالية
تطبيق على رقم الاستقرار الداخلي
الفصل 19. العوامل
دورات هاميلتون والعوامل
شرط ضروري وكاف لوجود العامل
الفصل 20. اتصال الرسم البياني
نقاط المفصلية
الرسوم البيانية دون المفاصل
رسوم بيانية متصلة بـ h
الفصل 21. الرسوم البيانية المستوية
الخصائص الأساسية
تعميم
الإضافات
I. خارج النظرية العامة والألعاب
ثانيا. حول مهام النقل
ثالثا. حول استخدام المفاهيم المحتملة في شبكات النقل
رابعا. المشاكل التي لم يتم حلها والافتراضات غير المثبتة
V. حول بعض المبادئ الأساسية للعد (ج. ريجيت)
السادس. إضافات إلى الترجمة الروسية (A.A. Zykov وG.I. Kozhukhin)
الأدب
نظرية الرسم البياني وكتاب سي. بيرج (خاتمة للترجمة الروسية)
مؤشر الأحرف
فهرس الاسم
دليل الموضوع.

قم بتنزيل الكتاب الإلكتروني مجانًا بتنسيق مناسب وشاهده واقرأه:
تحميل كتاب نظرية الرسم البياني وتطبيقاتها لبيرج ك. - fileskachat.com، تحميل سريع ومجاني.

نظرية الرسم البياني هي فرع من الرياضيات المنفصلة التي تدرس الكائنات الممثلة كعناصر فردية (القمم) والروابط بينها (الأقواس والحواف).

نشأت نظرية الرسم البياني من حل مشكلة جسور كونيجسبيرج في عام 1736 من قبل عالم الرياضيات الشهير ليونارد أويلر(1707-1783: ولد في سويسرا، عاش وعمل في روسيا).

مشكلة حول جسور كونيجسبيرج.

هناك سبعة جسور في مدينة كونيغسبيرغ البروسية على نهر بريغال. هل من الممكن إيجاد طريق للمشي يعبر كل جسر مرة واحدة بالضبط ويبدأ وينتهي في نفس المكان؟

يسمى الرسم البياني الذي يوجد فيه مسار يبدأ وينتهي عند نفس الرأس ويمر على جميع حواف الرسم البياني مرة واحدة بالضبطالرسم البياني أويلر.

يتم استدعاء تسلسل القمم (ربما المتكرر) الذي يمر من خلاله المسار المطلوب، وكذلك المسار نفسهدورة أويلر .

مشكلة ثلاثة بيوت وثلاثة آبار.

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

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

يتمثل جوهر الحل المنشور في تجربة عدد كبير ولكن محدود (حوالي 2000) من الأمثلة المضادة المحتملة لنظرية الألوان الأربعة وإظهار أنه لا توجد حالة واحدة تعتبر مثالًا مضادًا. تم الانتهاء من هذا البحث بواسطة البرنامج في حوالي ألف ساعة من تشغيل الكمبيوتر العملاق.

من المستحيل التحقق من الحل الناتج "يدويًا" - نطاق التعداد يتجاوز نطاق القدرات البشرية. يطرح العديد من علماء الرياضيات السؤال التالي: هل يمكن اعتبار مثل هذا "الدليل البرنامجي" دليلاً صالحًا؟ في النهاية قد تكون هناك أخطاء في البرنامج..

وبالتالي، لا يمكننا الاعتماد إلا على مهارات البرمجة للمؤلفين ونعتقد أنهم فعلوا كل شيء بشكل صحيح.

التعريف 7.1. عدد ز= ز(الخامس, ه) عبارة عن مجموعة من مجموعتين محدودتين: V - تسمى العديد من القمموالمجموعة E من أزواج العناصر من V، أي. EÍV´V، دعا العديد من الحواف، إذا كانت الأزواج غير مرتبة، أو العديد من الأقواس، إذا تم ترتيب الأزواج.

في الحالة الأولى، الرسم البياني ز(الخامس, ه) مُسَمًّى غير موجه، في الثانية - الموجهة.

مثال. رسم بياني بمجموعة الرؤوس V = (a,b,c) ومجموعة الحواف E =((a, b), (b, c))

مثال. رسم بياني مع V = (a,b,c,d,e) و E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (ج، د))،

إذا كانت e=(v 1 ,v 2), еОЕ، فإنهم يقولون أن الحافة هي e يربطالقمم الخامس 1 والخامس 2.

يتم استدعاء القمتين v 1,v 2 مجاورإذا كان هناك حافة تربط بينهما. في هذه الحالة، يتم استدعاء كل من القمم حادثة الحافة المقابلة .

ضلعين مختلفين مجاور، إذا كان لديهم قمة مشتركة. في هذه الحالة، يتم استدعاء كل من الحواف عرضي قمة المقابلة .

عدد رؤوس الرسم البياني زدعونا نشير الخامس، وعدد الحواف هو ه:

.

التمثيل الهندسي للرسوم البيانية هو كما يلي:

1) قمة الرسم البياني هي نقطة في الفضاء (على المستوى)؛

2) حافة الرسم البياني غير الموجه – قطعة؛

3) قوس الرسم البياني الموجه – الجزء الموجه.

التعريف 7.2.إذا حدث في الحافة e=(v 1 ,v 2) v 1 =v 2، فإن الحافة e تسمى حلقة. إذا كان الرسم البياني يسمح بالحلقات، فسيتم استدعاؤه الرسم البياني مع الحلقات أو رسم زائف .

إذا كان الرسم البياني يسمح بوجود أكثر من حافة واحدة بين رأسين، فإنه يسمى multigraph .

إذا تم تسمية كل قمة من الرسم البياني و/أو الحافة، فسيتم استدعاء هذا الرسم البياني ملحوظ (أو محمل ). عادة ما تستخدم الحروف أو الأعداد الصحيحة كعلامات.

التعريف 7.3.رسم بياني ز (الخامس , ه ) مُسَمًّى رسم بياني فرعي (أو جزء ) رسم بياني ز(الخامس,ه)، لو الخامس الخامس, ه ه. لو الخامس = الخامس، الذي - التي ز مُسَمًّى رسم بياني فرعي ممتد ز.

مثال 7 . 1 . نظرا لرسم بياني غير موجه.

التعريف 7.4.يسمى الرسم البياني مكتمل ، لو أي رأساه متصلان بحافة. الرسم البياني الكامل مع نيُشار إلى القمم بـ ك ن .

التهم ك 2 ، ل 3, ل 4 و ك 5 .

التعريف 7.5.رسم بياني ز=ز(الخامس, ه) يسمى ذو فلقتين ، لو الخامسيمكن تمثيلها كاتحاد لمجموعات مفككة، على سبيل المثال الخامس=أب، بحيث يكون لكل حافة الشكل ( الخامس أنا , الخامس ي)، أين الخامس أنا أو الخامس ي ب.

تربط كل حافة قمة من A إلى قمة من B، لكن لا يوجد رأسان من A أو رأسان من B متصلان.

يسمى الرسم البياني الثنائي ثنائي الفلقة كاملة عدد ك م , ن، لو أيتضمن مقمم, بيتضمن نالقمم ولكل الخامس أنا أ, الخامس ي بلدينا ( الخامس أنا , الخامس ي)ه.

وهكذا للجميع الخامس أنا أ، و الخامس ي بهناك حافة تربطهم.

ك 12 ك 23 ك 22 ك 33

مثال 7 . 2 . إنشاء رسم بياني ثنائي كامل ك 2.4 والرسم البياني الكامل ك 4 .

الرسم البياني للوحدةن-مكعب الأبعادفي ن .

رؤوس الرسم البياني عبارة عن مجموعات ثنائية ذات أبعاد n. تربط الحواف القمم التي تختلف في إحداثي واحد.

مثال:

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

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

لحل المشاكل مع مثل هذه المجموعة، تحتاج إلى تعيين كل كائن من هذه المجموعة كشيء. من المقبول عمومًا تسمية هذا الشيء برؤوس الرسم البياني.

من السهل وصف الرسوم البيانية والتعريفات الأساسية بالصور، لذلك يجب تضمين الصور لقراءة هذه الصفحة.

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

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

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

في الأدب، وعلى الإنترنت، وبشكل عام أينما كتب شيء عن الرسوم البيانية، سوف تصادف مفاهيم مثل الأقواس والحواف. يوضح هذا الشكل حواف الرسم البياني. أولئك. هذه هي الحواف الثلاثة E1 وE2 وE3.

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

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

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

لم يتم وصف الكثير، ولكن هذه المعلومة قد تساعد شخصًا ما.