الرسم البياني الموجه. تعريف مثال مصفوفة تجاور الرسم البياني الموجه

الحافة زوج مرتب من الرؤوس. يتم استدعاء الرسم البياني الذي يشير إلى اتجاه كل من حوافه الموجهة.

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

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

فمثلا، في الرسوم البيانية الخوارزميةتتوافق رؤوس الرسم البياني العملية التي يتم إجراؤها، والأقواس (الحواف الموجهة) تتوافق مع تبعيات البيانات(أي ما هي المدخلات اللازمة لإجراء العملية).

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

تانيا ناتاشا

حتى تتمكن دائمًا من الاختيار ، وإلا فإنك تحتاج إلى إعادة النظر في نظام التفضيلات.

اتجاه واحد.

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

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

في لغة نظرية الرسم البياني ، تمت صياغتها على النحو التالي: في أي حالة يمكن توجيه حواف الرسم البياني G بحيث يكون هناك مسار موجه يربط بينهما بالنسبة لأي زوج من الرؤوس؟

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

سيتم استدعاء الحافة E = (A ، B) حافة الاتصال، أو برزخإذا كان هذا هو المسار الوحيد من A إلى B (أو العكس).

تقسم حافة التوصيل جميع رؤوس الرسم البياني إلى مجموعتين: تلك التي يمكن الوصول إليها من A دون المرور على طول الحافة E ، وتلك التي يمكن الوصول إليها من B دون المرور على طول E. يتكون الرسم البياني في هذه الحالة من جزأين G 1 و G 2 متصلان فقط بالحافة E (الشكل أ و أ + 1).

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

إذا كانت الحافة E i = (A i، B i) غير متصلة ، فهناك مسار آخر يربط A i و B i ولا يمر عبر E i. لذلك ، ستسمى هذه الحافة بالحافة الدورية.

شكل 2 ربط التين. 2 + 1 نهائي (متصل) شكل 2 + 2 دوري

ضلع ضلع

نظرية 1 اذا كان ز- رسم بياني متصل ، فمن الممكن دائمًا توجيه الحواف الدورية من جي ، مع ترك الحواف المتصلة غير موجهة بحيث يمكن توصيل أي زوج من الرؤوس في هذا الرسم البياني بمسار موجه.

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

يمكننا إثبات هذه النظرية بإظهار طريقة لتوجيه الرسم البياني بشكل صحيح. دعنا نختار جي حافة تعسفية E \ u003d (أ ، ب) . اذا كان ه - حافة الاتصال ، ستبقى على الوجهين ، وبعد ذلك سيكون من الممكن الانتقال منها لكن إلى في والعودة (الشكل 2 + 3).

شكل 2 + 3 شكل. 2 + 4

اذا كان ه هي حافة دورية ، ثم يتم تضمينها في بعض الدورات من، حيث يمكنك ضبط الاتجاه الدوري (الشكل 2 + 4).

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

اذا كان ه - ربط الضلع AB ، ثم سيبقى ذو وجهين. ثم لأي قمة X عدد ح يمكن للمرء أن يجد سلسلة موجهة ص توصيل X مع A. ، وهو ما يعني (من خلال الحافة ه ) ، ومع في . العودة من الأعلى في على الحافة ه يمكنك الذهاب إلى لكن ، وبعد ذلك - على طول سلسلة التوجيه ض - من لكن إلى X (الشكل أ + 5). إرفاق ه إلى ح ، حصلنا عليه بالفعل عظمعدد جي بالخصائص المطلوبة. إذا كانت الحافة E \ u003d (أ ، ب) هو دوري ، إنه ينتمي إلى بعض الدورات من . وضعنا الاتجاه ل من من لكن قبل في وعلى طول من إلى القمة الأولى د من من مملوكة من قبل ح (الشكل أ + 6).

أرز. أ + 5 شكل. أ + 6

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

درجات الرأس.

بالنسبة للرسوم البيانية الموجهة ، لدينا في كل رأس الرقم p (A) الصادر والرقم p * (A) للحواف الواردة. الرقم الإجماليالأضلاع تساوي:

N \ u003d p (A 1) + p (A 2) + ... + p (A n) \ u003d p * (A 1) + p * (A 2) + ... + p * (A n)

متوفرة أنواع مختلفةالرسوم البيانية لدرجات الرؤوس لها بعض الخصائص الخاصة. العد يسمى متجانس، إذا كانت درجات جميع رؤوسها تساوي نفس العدد r: لكل رأس A:

ص (أ) = ص * (أ) = ص

تمرين

أنشئ رسومًا بيانية موجهة متجانسة لدرجة r = 2 بحيث تكون n = 2،6،7،8 رؤوسًا.

علاقات.

العلاقات والرسوم البيانية.

أي نظام رياضي يتعامل مع مجموعة من العناصر أو العناصر. (علامات: الجبر والهندسة)

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

كل هذه العلاقات تتعلق بموضوعين ، لذلك يطلق عليهم العلاقات الثنائية، أو ببساطة علاقات، على سبيل المثال ، هناك أنواع أخرى من العلاقات العلاقات الثلاثيةتتعلق بثلاثة أشياء. (على سبيل المثال ، النقطة A تقع بين النقطتين B و C).

دعونا نقدم تعريفًا عامًا للعلاقة الثنائية R: аRв - в يتعلق بـ R إلى a.

على سبيل المثال ، العلاقة أ> ب تعني أن ب ينتمي إلى مجموعة كل الأرقام الأصغر من أ

في الواقع ، كل رسم بياني موجه G يحدد بعض العلاقة في مجموعة رؤوسه. يمكن كتابة هذه النسبة على النحو التالي: аGв. هذا يعني أن للرسم البياني حافة موجهة تنتقل من أ إلى ب.

شروط خاصة.

دعنا نعطي بعض العلاقة R. إذا كان العنصر a في علاقة R بنفسه ، فإنه يتوافق مع حلقة في الرسم البياني

العلاقة R التي من أجلها يتم استيفاء الشرط لأي، يسمى عاكس.

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

لكل علاقة R ، يمكن تعريفها النسبة العكسية R *، على افتراض أن аR * в إذا وفقط إذا аRв.

يمكن أن نرى من تعريف العلاقة العكسية أنه إذا كان الرسم البياني G المقابل لـ R له حافة (أ ، ب) ، فيجب أن يكون للرسم البياني G * المقابل لـ R * حافة (ج ، أ). بمعنى آخر ، الرسم البياني G * معكوس لـ G ، أي رسم بياني بنفس حواف G ، لكن متجهًا عكسيا.

تسمى العلاقة متماثل، إذا من аRв يتبع вРа.

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

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

نسبة بشكل عابر، إذا كان يتبع الشرطين aRb و bRc أن aRc.

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

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

علاقات التكافؤ.

علاقة التكافؤ ، التي يشار إليها عادةً بـ ~ ، لها الخصائص الثلاث التالية:

واحد). الانعكاسية: أ ~ أ ؛

2). التناظر: من a ~ إلى z إلى ~ a ؛

3). الانتقال: من a ~ إلى ~ c a ~ c.

في الواقع ، علاقة التكافؤ هي تعميم لخاصية المساواة.

تقدم علاقة التكافؤ قسمًا في مجموعة الرؤوس فئات التكافؤ المنفصلة.

لنفترض أن B i هي مجموعة رؤوس الرسم البياني للتكافؤ G التي تكافئ الرأس i. ثم يتم توصيل جميع الرؤوس التي تنتمي إلى B i بواسطة حواف ، أي في i - الرسم البياني الكامل G i. في كل رأس من هذا الرسم البياني توجد حلقة ينقسم الرسم البياني G إلى مجموعة من المكونات المتصلة G i.

طلب جزئى.

موقف سلوك طلب جزئىهو (على سبيل المثال المجموعات):

واحد). الانعكاسية: أ Ê أ

2). انتقالية: إذا كانت A Ê B و B C A C.

3). المطابقة: إذا كان A Ê B و B Ê Az A = B

علاقات الدمج الصارمة -

واحد). منع الانعكاسية: لا يحدث ÉA أبدًا ؛

2). الانتقال: إذا كان A É B و B É C ، ثم A É C

ترتيب العلاقة(بالمعنى الدقيق للكلمة) يسمى الترتيب الصارم ، أ> ب ، والذي ، بالإضافة إلى الشروط السابقة ، ينطبق أيضًا على ما يلي:

شرط الاكتمال.بالنسبة لأي عنصرين غير متطابقين في و a ، يتم استيفاء واحدة من العلقتين a> b أو b> a دائمًا.

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

رسومات مسطحة.

شروط الرسوم البيانية المستوية.

الكونت كوراتوفسكي K 3.3

رسم بياني مشكلة ثلاثة منازل وثلاثة آبار

الكونت كوراتوفسكي ك 5

هذان الرسمان البيانيان غير مسطحين!

تمديد الرسم البياني- تم وضع رؤوس جديدة على بعض الحواف ، بحيث تكون هذه الحواف

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

عملية عكسية، حيث يتم إزالة الرؤوس الفاصلة من السلاسل الأولية ، يسمى ضغطرسم بياني.

نظرية كوراتوفسكي

لكي يكون الرسم البياني مسطحًا ، من الضروري والكافي ألا يحتوي على أي رسم بياني في حد ذاته يمكن ضغطه على رسم بياني K 3.3 أو رسم بياني K 5.

صيغة أويلر

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

ويترتب على تعريف الرسوم البيانية المضلعة أنها متصلة. كما نطلب عدم وجود مضلع داخل مضلع آخر. تشكل حواف حدود كل مضلع دورة ، تسمى أحيانًا الحد الأدنى من الدورة. يسمى جزء المستوى المحاط بالمضلع وجه الرسم البياني. الرسم البياني لديه أيضا الحد الأقصى للدورة C 1, المحيطة بالكلالرسم البياني بكل أوجهه. سننظر في جزء المستوى الذي يقع خارج C 1 أيضًا كوجه لرسم بياني بحد C 1 - بلا نهايةوجه F ¥.

للدلالة به

عدد الرؤوس والحواف والوجوه مضلع الفضاء..

نظرية أويلر

ج - ص + ص = 2

دليل - إثبات:الصيغة واضحة للمضلع ذي الحواف n. في الواقع ، n من الرؤوس والحواف n ، بالإضافة إلى وجهين F 1 F ¥

نضيف وجهًا جديدًا إلى رسم بياني به وجوه r عن طريق الرسم على طول الوجه F ¥ بعض السلاسل الأولية التي تربط رأسين من الرسم البياني الأقصى. وجه. لكن بعد ذلك

ج '- ص' + ص '= (ج + ص - 1) - (ص + ص) + (ص + 1) = ج - ف + ص (= 2!)

من خلال فرضية الاستقراء.

تمثيلات المصفوفة.

1. مصفوفة الحوادث

أ). لرسم بياني غير موجه مصفوفة الوقوعهي مصفوفة تتوافق صفوفها مع الرؤوس وأعمدتها تتوافق مع الحواف. عنصر المصفوفة يساوي 1 إذا كان الرأس يقع على حافة. خلاف ذلك ، يأخذ عنصر المصفوفة القيمة 0.

ب). بالنسبة للرسم البياني الموجه ، يكون عنصر مصفوفة الوقوع هو +1 عندما تكون قمة الرأس الواقعة على القوس هي الرأس الأولي للقوس (أي أن القوس ينشأ من هذا الرأس). العنصر هو -1 عندما يدخل القوس في الرأس. إذا لم يكن الرأس يقع على القوس ، فعندئذٍ يكون عنصر المصفوفة 0.

2. مصفوفة الدورات C.

أ). بالنسبة للرسم البياني غير المباشر ، تتوافق صفوف مصفوفة الدورة مع الدورات البسيطة للرسم البياني ، وتتوافق الأعمدة مع حوافها. عنصر المصفوفة a ij = 1 إذا كانت الدورة С i تحتوي على الحافة e j. وإلا فإن ij = 0.

ب). بالنسبة للرسم البياني الموجه ، فإن ij = 1 أو -1 أو 0 ، اعتمادًا على ما إذا كان اتجاه الدورة C i والقوس e j هو نفسه أو عكسه ، أو أن هذه الدورة لا تحتوي على القوس e j على الإطلاق.

3. مصفوفة تجاور الرأس (أو ببساطة مصفوفة الجوار) V هي مصفوفة تتوافق صفوفها وأعمدتها مع الرؤوس ، وعنصر المصفوفة a i في حالة الرسم البياني غير المباشر يساوي عدد الحواف التي تربط الرؤوس i و j . بالنسبة للرسم البياني الموجه ، فإن العنصر a ij يساوي عدد الحواف الموجهة من الرأس i إلى الرأس j.

النظريات الأساسية المتعلقة تمثيلات المصفوفةالرسوم البيانية.

1) الترتيب (الحد الأقصى لعدد الأعمدة المستقلة خطيًا) لمصفوفة السقوط A لرسم بياني متصل (موجه وغير موجه) برؤوس n تساوي (n-1).

2). رتبة مصفوفة الدورة C لرسم بياني متصل بحواف m ورؤوس n هي (m-n + 1).

مثال على استخدام مصفوفة مجاورة.

يوضح التعيين التالي أن الرسمين البيانيين G 1 و G 2 متماثلان

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

أ 2 \ u003d PA 1 P "، أين

ف = ، أو p ij = d p (i) ، j (رمز Kronecker)

و R "هي المصفوفة المنقولة.

يمكن أن يكون العثور على المصفوفة P أمرًا صعبًا.

يعني تماثل G 1 و G 2 أن A 1 و A 2 لهما نفس القيم الذاتية. ومع ذلك ، فإن هذا الشرط غير كافٍ (المثال أدناه).

يترك الخامس ، دهي مجموعات تعسفية ، و الخامس؟؟.للدلالة به الخامس 2مجموعة ديكارتي مربع الخامس.

رسم بياني موجه أو باختصار Digraph جيدعا الثلاثي الخامس ، د ، ج) : أين ج- بعض رسم الخرائط للمجموعة D في المجموعة الخامس 2. مجموعة العناصر الخامسو دتسمى ، على التوالي ، رؤوس وأقواس الديغراف جي. مجموعات من الرؤوس والأقواس للمخطط جيبشكل ملائم بواسطة VGو دي جيعلى التوالى. اذا كان F- القوس إذن ج(F) زوج مرتب ( و ،)، أين و : ضد J V.. قوس Fالخروج من القمة وويذهب إلى القمة الخامس؛ بدوره وو الخامستسمى رؤوس نهاية القوس F؛ في المستقبل سوف نكتب F= (وأحيانًا - F = الأشعة فوق البنفسجيةإذا لم يكن هناك خطر الارتباك).

عند كتابة مخطط رقمي تعسفي ، عادةً ما يتم تمثيله كـ جي = (الخامس ، د).

عادة ما يتم تصوير Digraphs باستخدام رسوم بيانية مشابهة للرسومات البيانية. الفرق الوحيد هو أن الخط الذي يصور القوس له اتجاه.

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

على التين. 8 يُظهر Digraph وقاعدتها

الشكل 8

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

حيث

هذا الطريق يسمى (الخامس حول , الخامس ر) - طريق قياسي ؛ القمم الخامس او الخامس رتسمى ، على التوالي ، الرؤوس الأولية والنهائية لمثل هذا المسار. اذا كان الخامس ا = الخامس ر، ثم يسمى or-route بإغلاق. عدد الأقواس التي يتألف منها النموذج هو طول النموذج.

يسمى المسار بدون أقواس متكررة بـ orchain. السلسلة البسيطة هي سلسلة لا تحتوي على رؤوس متكررة (ربما باستثناء نفس رؤوس البداية والنهاية). يسمى orchain البسيط المغلق بالدورة أو الكفاف.

من السهل التحقق من وجوده (و ، الخامس؛) - orroute يضمن وجود ( و ،) - أورسيبي.

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

رسم بياني جييُطلق عليه `` قابل للتوجيه '' إذا كان هو أساس بعض digraph متصل بقوة.

نظرية 1.3. رسم بياني متصل جيقابل للتوجيه فقط إذا لم تكن كل حوافه جسراً.

دليل - إثبات. دع العد جيهي قاعدة Digraph حو جييحتوي على جسر ه. ثم في حهناك قوس F= أين و ،- ينتهي الضلع ه. من الواضح في حرقم ( u ، v) - الطرق. لذلك ، الرسم البياني جيغير قابل للتوجيه.

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

يترك جيهو Digraph التعسفي. درجة النتيجة degvالقمم الخامسهو عدد كل الأقواس التي لها الخامسكبداية. وبالمثل درجة الدخول degvهو عدد جميع الأقواس التي يكون رأسها الخامسإنها النهاية. تحتوي على Digraph صالقمم و رسيتم استدعاء الأقواس ( ن ، ت) هو digraph.

الدرجات الخارجية والدرجات الداخلية مرتبطة بالطريقة الواضحة التالية.

ليما 1. يترك جي- افتراضى ( ن ، ت) هو digraph. ثم

هذا التأكيد مشابه لـ Lemma 1 من Sec. 1.1 ؛ وغالبًا ما يشار إليها باسم المصافحة orlemma.

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

مفاهيم أساسية

رسميا ، Digraph D = (V ، E) (displaystyle D = (V ، E))يتكون من العديد ك (displaystyle V)، التي تسمى عناصرها القممو مجموعات E (displaystyle E)أزواج مرتبة من القمم u، v ∈ V (\ displaystyle u، v \ in V).

قوس (ش ، ت) (displaystyle (u ، v)) عرضيالقمم u (displaystyle u)و ك (displaystyle v). في نفس الوقت يقولون ذلك u (displaystyle u) - الذروة الأوليةالأقواس و ك (displaystyle v) - الذروة النهائية.

الاتصال

طريقفي الرسم البياني يسمى التسلسل المتناوب للرؤوس و أقواس، طيب القلب v 0 (v 0 ، v 1) v 1 (v 1 ، v 2) v 2. . . v n (displaystyle v_ (0) (v_ (0) ، v_ (1)) v_ (1) (v_ (1) ، v_ (2)) v_ (2) ... v_ (n))(يمكن تكرار القمم). طول الطريق- عدد الأقواس فيه.

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

دائرة كهربائيةهناك مغلق طريق.

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

ديجراف متصل بقوة، أو ببساطة قوي، إذا كانت جميع رؤوسها متبادلة قابل للتحقيق; طريقة واحدة متصلة، أو ببساطة من جانب واحدإذا كان لأي رأسين يمكن الوصول إلى أحدهما على الأقل من الآخر ؛ متصل بشكل فضفاض، أو ببساطة ضعيف، في حالة تجاهل اتجاه الأقواس ، يتم الحصول على رسم بياني متصل (متعدد) ؛

أقصى قوييسمى الرسم البياني الفرعي مكون قوي; مكون من جانب واحدو مكون ضعيفيتم تعريفها بطريقة مماثلة.

تركيزديجراف د (displaystyle D)يسمى digraph الذي تكون رؤوسه مكونات قوية د (displaystyle D)، والقوس في د ⋆ (displaystyle D ^ (star))يشير إلى وجود قوس واحد على الأقل بين الرؤوس المدرجة في المكونات المقابلة.

تعريفات إضافية

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

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

صورة وخصائص جميع الرسوم البيانية ذات العقد الثلاثة

عنوان تفسيري: من- ضعيف، نظام التشغيل- من جانب واحد ، SS- قوي، ح- رسم بياني موجه ، جي- أرجوحة شبكية ، تي- هي بطولة

0 أقواس	1 قوس	2 قوس	3 أقواس	4 أقواس	5 أقواس	6 أقواس
فارغة ، N ، G	N ، G		نظام التشغيل	نسخة	نسخة	كامل ، CC
		OS ، N ، G	CC ، N ، T	نسخة
		C ، N ، G	OS ، N ، G ، T	نظام التشغيل
		C ، N ، G	نظام التشغيل

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

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

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

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

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

فيما يلي بعض الرموز المهمة المستخدمة في نظرية الرسم البياني:

• G = (V ، E) ، هنا G رسم بياني ، V رؤوسها ، و E هي حواف ؛
• | الخامس | - الترتيب (عدد الرؤوس) ؛
• | ه | - حجم الرسم البياني (عدد الحواف).

في حالتنا (الشكل 1) | V | = 5 ، | E | = 10 ؛

عندما يمكن الوصول إلى أي رأس آخر من أي رأس ، يسمى هذا الرسم البياني غير موجهرسم بياني متصل (الشكل 1). إذا كان الرسم البياني متصلاً ، ولكن هذا الشرط غير مستوفٍ ، فسيتم استدعاء هذا الرسم البياني الموجهةأو digraph (الشكل 2).

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

في الرسم البياني ، على عكس الرسم البياني غير الموجه ، من الممكن الانتقال من الرأس h إلى الرأس s بدون رؤوس وسيطة ، فقط عندما تترك الحافة h وتدخل s ، ولكن ليس العكس.

الرسوم البيانية الموجهة لها الرموز التالية:

G = (V ، A) ، حيث V هي رؤوس ، A هي حواف موجهة.

النوع الثالث من الرسوم البيانية - مختلطالرسوم البيانية (الشكل 3). لديهم حواف موجهة وغير اتجاهية. بشكل رسمي ، يتم كتابة الرسم البياني المختلط على النحو التالي: G = (V ، E ، A) ، حيث يشير كل حرف بين قوسين أيضًا إلى ما كان يُنسب إليه سابقًا.

في الرسم البياني في الشكل 3 ، يتم توجيه بعض الأقواس [(هـ ، أ) ، (هـ ، ج) ، (أ ، ب) ، (ج ، أ) ، (د ، ب)] ، والبعض الآخر غير موجه [( ه ، د) ، (هـ ، ب) ، (د ، ج) ...].

قد يبدو رسمان بيانيان أو أكثر للوهلة الأولى مختلفين في هيكلهما ، والذي ينشأ بسبب اختلاف تمثيلهما. لكن ليس هذا هو الحال دائما. لنأخذ رسمين بيانيين (الشكل 4).

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

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

في أي من الرسوم البيانية التي درسناها ، من الممكن تحديد مسار ، علاوة على ذلك ، أكثر من مسار. طريقعبارة عن سلسلة من الرؤوس ، كل منها متصل بالرأس التالية بواسطة حافة. إذا تزامنت الرؤوس الأولى والأخيرة ، فإن هذا المسار يسمى دورة. يتم تحديد طول المسار بعدد الحواف التي يتكون منها. على سبيل المثال ، في الشكل 4.a ، المسار هو التسلسل [(هـ) ، (أ) ، (ب) ، (ج)]. هذا المسار عبارة عن رسم بياني فرعي ، نظرًا لأن تعريف الأخير ينطبق عليه ، أي: الرسم البياني G '= (V'، E ') هو رسم بياني فرعي للرسم البياني G = (V ، E) فقط إذا كان V' و E ' تنتمي إلى V ، E.

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

يقدم هذا الفصل النتائج الرئيسية لنظرية الرسوم البيانية الموجهة. تتم مناقشة الأسئلة المتعلقة بوجود سلاسل أويلر الموجهة ودورات هاميلتون. يتم أيضًا النظر في الأشجار الموجهة وارتباطها بسلاسل أويلر الموجهة.

5.1 التعريفات والمفاهيم الأساسية

لنبدأ بتقديم بعض التعريفات والمفاهيم الأساسية المتعلقة بالرسوم البيانية الموجهة.

يتكون الرسم البياني الموجه من مجموعتين: مجموعة محدودة V ، تسمى عناصرها الرؤوس ، ومجموعة محدودة E ، تسمى عناصرها الحواف أو الأقواس. يرتبط كل قوس بزوج مرتب من الرؤوس.

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

في التمثيل الرسومي للرسم البياني الموجه ، يتم تمثيل الرؤوس بنقاط أو دوائر ، ويتم تمثيل الحواف (الأقواس) بأجزاء.

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

على سبيل المثال ، إذا كانت تلك الخاصة بهم) ، فيمكن تمثيل الرسم البياني الموجه بالشكل. 5.1 في هذا الرسم البياني - الأقواس المتوازية و - الحلقة.

أرز. 5.1 الرسم البياني الموجه.

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

يسمى القوس الخارج من قمته الأولية ويدخل قمته النهائية. يُقال أن الرأس يكون معزولًا إذا لم يكن به أقواس عرضية.

درجة الرأس هي عدد الأقواس التي تقع عليها. الدرجة الداخلية للرأس هي عدد الأقواس التي تدخل V] والدرجة الخارجية هي عدد الأقواس الصادرة. تشير الرموز و b "إلى الحد الأدنى للدرجة الخارجية والداخلية للرسم البياني الموجه. وبالمثل ، تشير الرموز إلى الحد الأقصى للدرجة الخارجية والداخلية ، على التوالي.

يتم تعريف مجموعات أي قمة على النحو التالي:. على سبيل المثال ، في الرسم البياني في الشكل. 5.1

لاحظ أن الحلقة تزيد من نصف درجات دخول وخروج هذا الرأس. التأكيد التالي هو نتيجة لحقيقة أن كل قوس يزيد بمقدار 1 مجموع نصف درجات كل من مدخلات ومخرجات الرسم البياني الموجه.

نظرية 5.1. في الرسم البياني الموجه مع الأقواس

مجموع بالدرجات = مجموع الدرجات الخارجية = م.

يتم تعريف الرسوم البيانية الفرعية والمخططات الفرعية الناتجة عن الرسم البياني الموجه بنفس الطريقة كما في حالة الرسوم البيانية غير الموجهة (القسم 1.2).

يُطلق على الرسم البياني غير المباشر الناتج عن إزالة الاتجاه من أقواس الرسم البياني الموجه G الرسم البياني الأساسي غير الموجه G ويُشار إليه بالرمز.

المسار الموجه للرسم البياني الموجه هو سلسلة محدودة من الرؤوس

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

يُقال أن المسار الموجه مفتوحًا إذا كانت رؤوس نهايته مختلفة ، وإلا يطلق عليه مغلق.

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

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

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

يقال إن الرسم البياني الموجه يكون غير دائري أو بدون محيط إذا لم يكن له حدود. على سبيل المثال ، الرسم البياني الموجه في الشكل 1 لا دوري. 5.2

أرز. 5.2 رسم بياني موجه غير دوري.

أرز. 5.3 رسم بياني موجه متصل بقوة.

يُطلق على تسلسل الرؤوس في الرسم البياني الموجه G مسارًا في G إذا كان مسارًا في الرسم البياني الأساسي غير المباشر ، على سبيل المثال ، التسلسل في الرسم البياني في الشكل. 5.2 هو طريق ، لكنه غير موجه.

يتم تعريف سلسلة ومسار ودورة الرسم البياني الموجه بالمثل.

يقال أن الرسم البياني الموجه متصل إذا كان الرسم البياني الأساسي غير موجه متصلًا.

يسمى الرسم البياني الفرعي للرسم البياني الموجه G أحد مكونات الرسم البياني G إذا كان أحد مكونات الرسم البياني

يقال إن رؤوس الرسم البياني الموجه G مرتبطة بقوة إذا كانت هناك مسارات موجهة من وإلى G. إذا كان مرتبطًا بقوة ، فمن الواضح أنه مرتبط بقوة. كل رأس متصل بقوة بنفسه.

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

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

يُطلق على الرسم البياني الفرعي الأقصى المتصل بقوة في الرسم البياني الموجه G مكونًا متصلًا بقوة من G.

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

أرز. 5.4. الرسم البياني وتكثيفه.

على سبيل المثال ، الرسم البياني الموجه في الشكل. الشكل 5.4 ، يحتوي على ثلاثة مكونات متصلة بقوة مع مجموعات الرؤوس وتشكيل قسم من مجموعة قمة الرسم البياني الموجه.

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

وبالتالي ، على الرغم من أن الخاصية "شديدة الارتباط" تستلزم تقسيم مجموعة قمة الرسم البياني ، إلا أنها قد لا تولد تقسيم مجموعة الأقواس.

يتم تعريف الاتحاد والتقاطع وجمع الوسيط 2 والعمليات الأخرى على الرسوم البيانية الموجهة بنفس الطريقة تمامًا كما في حالة الرسوم البيانية غير الموجهة (القسم 1.5).

الرسم البياني الناتج عن تقلص جميع أقواس المكونات المتصلة بقوة في الرسم البياني الموجه G يسمى الرسم البياني المكثف لـ G. تكاثف الرسم البياني الموضح في الشكل. 5.4 ، أ ، مبين في الشكل. 5.4 ب.

تتوافق رؤوس الرسم البياني مع المكونات المتصلة بقوة في الرسم البياني G وتسمى الصور المكثفة للمكونات.

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

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

يقال إن الرسم البياني الموجه G متصل بشكل ضئيل إذا كان متصلاً بقوة ، وإزالة أي قوس يحرمه من ممتلكاته المتصلة بقوة.

أرز. 5.5 الحد الأدنى من الرسم البياني الموجه المتصل.

الحد الأدنى من الاتصال ، على سبيل المثال ، الرسم البياني الموضح في الشكل. 5.5

من الواضح أن الرسوم البيانية المتصلة بالحد الأدنى لا يمكن أن تحتوي على أقواس وحلقات متوازية.

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

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