نموذج رياضي. خوارزمية لاستخراج المكونات المتصلة بقوة

لنفترض أن G (V ، X) يكون رسمًا كاذبًا ودع القمم v و w (v¹w) من هذا الرسم البياني متصلة بواسطة مسار. ثم يوجد بالضرورة مسار أدنى يربط بين هذه الرؤوس. تشير إلى طول هذا الطريق د (ت ، ث). قمنا أيضًا بتعيين d (v ، v) = 0 لأي قمة رأس vнV ؛ د (ت ، ث) = إذا لم يكن هناك طريق بين v و w.

تسمى القيمة d (v ، w) المحددة بهذه الطريقة لأي رؤوس v و w للرسم البياني G (V ، X) المسافة بين v و w.

عدد المسافات في الرسم البياني برؤوس n يساوي عدد التركيبات C n 2.

دع الرسم البياني G (V ، X) متصلاً. دعونا نحدد المفاهيم التالية لذلك:

قطر الرسم البياني: د (G) = maxd (v، w).

الانحراف (أقصى إزاحة) للقمة: ص (ت) = ماكسد (ت ، ث) ؛

نصف قطر الرسم البياني:ص (G) = دقيقة ص (ت) ؛

مركز الرسم البياني: أي رأس vОV مثل r (v) = r (G).

يُطلق على قطر الرسم البياني وانحرافات الرؤوس ونصف قطر الرسم البياني ومراكز الرسم البياني الخصائص المترية للرسم البياني.

مثال. أوجد الخصائص المترية للرسم البياني التي يقدمها الرسم التخطيطي:

دعونا نجد جميع المسافات ، مع الأخذ في الاعتبار أن d (v، w) = d (w، v).

عدد المسافات في الرسم البياني المعطى С 5 2 = 5! / 3! 2! = 10: د (ع 1 ، ع 2) = 1 ، د (ع 1 ، ع 3) = 2 ، د (ع 1 ، ع 4) = 2 ، د (ع 1 ، ع 5) = 3 ، د (ت 2، v 3) = 1، d (v 2، v 4) = 1، d (v 2، v 5) = 2، d (v 3، v 4) = 1، d (v 3، v 5) = 2، د (ع 4، ع 5) = 1.

قطر الرسم البياني د (G) = 3.

الانحرافات المركزية في الرأس: r (v 1) = 3 ، r (v 2) = 2 ، r (v 3) = 2 ، r (v 4) = 2 ، r (v 5) = 3.

نصف قطر الرسم البياني r (G) = 2.

مراكز الرسم البياني v 2، v 3، v 4.

3. الحد الأدنى من المسارات في الرسوم البيانية المحملة

يسمى الرسم البياني G (V ، X) محملاً إذا كانت هناك على مجموعة حواف الرسم البياني وظيفة تسمى دالة الوزن التي ترتبط بكل حافة x нX من الرسم البياني برقم l (x). تسمى القيمة l (x) طول القوس.

يمكن إعطاء الكمية l (x) معنى مختلف: تكاليف النقل ووقت السفر والمسافة بين النقاط واستهلاك البنزين وما إلى ذلك.

يُطلق على مجموع أطوال الحواف المضمنة في المسار طول المسار.

لاحظ أنه إذا كانت كل x н X l (x) = 1 ، فيمكن اعتبار الرسم البياني غير محمل.

يُطلق على المسار في الرسم البياني G (V ، X) من الرأس v إلى الرأس w (v¹w) الحد الأدنى إذا كان له الحد الأدنى للطول بين جميع المسارات في الرسم البياني G (V ، X) من الرأس v إلى الرأس w.

نحن نقصر أنفسنا على الرسوم البيانية التي لها l (x)> 0.

عند البحث عن الحد الأدنى للمسار في رسم بياني محمل بـ l (x)> 0

نستخدم نفس العبارة المستخدمة في الرسم البياني غير المحمل ، وهي:

أي مسار بسيط هو مسار بسيط.

ضع في اعتبارك الآن مشكلة إيجاد الحد الأدنى من المسار في الرسم البياني المحمل.

دع الرسم البياني G (V ، X) يتم تحميله ، عدد الرؤوس n ³ 2 ، من الضروري إنشاء مسار أدنى من v 1 إلى v n.

دعونا نعطي خوارزمية.

الخطوة 1. قم بتعيين الفهرس a (v i) لكل رأس: a (v 1) = 0، a (v i) = ¥، i ¹ 1. لون الرأس v 1 وقم بتعيين v = v 1.

الخطوة 2. لكل رأس غير ملون v j قم بتغيير الفهرس وفقًا للقاعدة:

أ (ت ي) = دقيقة (أ (ت ت) ، أ (ت) + ل (ت ، ت ج)).

لون الرأس الذي يكون a (v j) هو الأصغر له .. ولون أيضًا الحافة المؤدية إلى العقدة المحددة. هذه الخطوةقمة الرأس الخامس ي. ضع v = v j.

الخطوة 3. إذا كانت v = v j ، قم بإنهاء الإجراء منذ أقصر طريق من v 1 إلى v n. إذا كانت v ¹ v n ، فانتقل إلى الخطوة 2.

تعليق. الخطوة 2 مستحيلة إذا كان كل a (v j) =. في هذه الحالة ، لا يمكن الوصول إلى الرأس v n.

دعونا نطبق الخوارزمية أعلاه على الرسم البياني الذي يقدمه الرسم التخطيطي. لنجد فيه أقصر طريق من v 1 إلى v 6.

الخطوة 1. تلوين قمة الرأس v 1. قم بتعيين مؤشرات للرؤوس: a (v 1) = 0، a (v 2) = a (v 3) =… = a (v n) =. وضعنا v 1 = v.

أ (ت 2) = دقيقة (¥ ، 0 + 4) = 4 ،

أ (ع 3) = دقيقة (¥ ، 0 + 7) = 7 ،

أ (ت 4) = دقيقة (¥ ، 0 + 3) = 3 ،

أ (ت 5) = دقيقة (¥ ، 0 +) = ،

أ (ع 6) = دقيقة (¥ ، 0 +) =.

نلون الرأس ع 4 والحافة (ع 1 ، ع 4).

الخطوة 3. بما أن الرأس v 6 غير ملون ، فإننا نقوم بالخطوة 2 ، مع ضبط v = v 4.

أ (ت 2) = دقيقة (4 ، 3 + ¥) = 4 ،

أ (ع 3) = دقيقة (7 ، 3 + ¥) = 7 ،

أ (ت 5) = دقيقة (¥ ، 3 + 3) = 6 ،

أ (ع 6) = دقيقة (¥ ، 3 +) =.

نقوم بتلوين الرأس v 2 والحافة (v 1 ، v 2).

الخطوة 3. بما أن الرأس v 6 غير ملون ، فإننا نقوم بالخطوة 2 ، مع ضبط v = v 2.

أ (ت 3) = دقيقة (7 ، 4 + 3) = 7 ،

أ (ت 5) = دقيقة (6 ، 4 + 2) = 6 ،

أ (ع 6) = دقيقة (¥ ، 4 + ¥) =.

نلون الرأس v 5 والحافة (v 4 ، v 5).

الخطوة 3. بما أن الرأس v 6 غير ملون ، فإننا نقوم بالخطوة 2 ، مع ضبط v = v 5.

أ (ع 3) = دقيقة (7 ، 6 + ¥) = 7 ،

أ (ع 6) = دقيقة (¥ ، 6 + 2) = 8.

نقوم بتلوين الرأس v 3 والحافة (v 1 ، v 3).

الخطوة 3. بما أن الرأس v 6 غير ملون ، فإننا نقوم بالخطوة 2 ، مع ضبط v = v 3.

أ (ع 6) = دقيقة (8 ، 7 + 2) = 8.

نلون الرأس v 6 والحافة (v 5 ، v 6).

بما أن الرأس v 6 ملون ، فإننا نوقف الشغل. حصلنا على الحد الأدنى للمسار v 1 v 4 v 5 v 6 ، وطوله يساوي 8.

لاحظ أن هذا في هذه القضيةليس الطريق الأدنى الوحيد للرؤوس v 1 و v 6 ، لأن في الخوارزمية كان من الممكن تلوين الحافة (v 4، v 5) بدلاً من الحافة (v 2، v 5) ، ثم سنحصل على مسار آخر بنفس الطول.

4. المهام على الأشجار

يسمى الرسم البياني غير دوري إذا لم تكن هناك دورات.

يسمى الرسم البياني بدون دورات الغابة.

الشجرة عبارة عن رسم بياني غير دائري متصل.

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

للقيام بذلك ، نتذكر قواعد ضرب المصفوفات. دعونا نعطي مصفوفات عشوائية مع عناصر عددية: مصفوفة $ A $ من البعد $ n \ مرات m $ مع العناصر $ a_ (ik) $ والمصفوفة $ B $ من البعد $ m \ مرات q $ مع العناصر $ b_ (kj) $ . تسمى المصفوفة $ C $ ذات البعد $ n \ مرات q $ منتج المصفوفة $ A $ و $ B $ (الترتيب مهم) إذا تم تعريف عناصرها $ c_ (ij) $ على النحو التالي: $ c_ (ij) = \ sum \ limits_ (k = 1) ^ m (a_ (ik) b_ (kj)) $. حاصل ضرب المصفوفات مكتوب بالطريقة المعتادة $ AB = C $. كما ترى ، يتطلب حاصل ضرب المصفوفات الاتساق في أحجام العاملين الأول والثاني (عدد أعمدة مصفوفة العامل الأول يساوي عدد صفوف مصفوفة العامل الثاني). يختفي هذا المطلب إذا أخذنا في الاعتبار المصفوفات المربعة من نفس الترتيب ، وبالتالي ، يمكننا النظر في القوى التعسفية لمصفوفة مربعة. هذه إحدى مزايا المصفوفات المربعة على المصفوفات المستطيلة. ميزة أخرى هي أنه يمكننا تقديم تفسير بياني لعناصر درجة مصفوفة التقارب.

دع مصفوفة التقارب $ A $ تكون بالشكل: $ A = \ left (((\ begin (array) (* c) (a_ (11)) & (a_ (12)) & (...) & ( a_ (1n)) \\ (a_ (21)) & (a_ (22)) & (...) & (a_ (2n)) \\ (...) & (...) & (.. .) & (...) \\ (a_ (n1)) & (a_ (n2)) & (...) & (a_ (nn)) \\ end (array))) \ right) $، وقوته $ k $ th - $ A ^ k = \ left (((\ begin (array) (* c) (a_ (11) ^ ((k))) & (a_ (12) ^ ((k) )) & (...) & (a_ (1n) ^ ((k))) \\ (a_ (21) ^ ((k))) & (a_ (22) ^ ((k))) & ( ...) & (a_ (2n) ^ ((k))) \\ (...) & (...) & (...) & (...) \\ (a_ (n1) ^ ((k))) & (a_ (n2) ^ ((k))) & (...) & (a_ (nn) ^ ((k))) \\ end (array))) \ right) $ ، حيث $ k = 2،3، ... $ من الواضح أن $ A ^ k $ ، مثل المصفوفة $ A $ ، سيكون مصفوفة متماثلة.

دع $ k = 2 $. ثم $ a_ (ij) ^ ((2)) = \ sum \ limits_ (k = 1) ^ n (a_ (il) a_ (lj)) $ ($ i، j = 1،2، ...، n $) ، وكل مصطلح $ a_ (il) a_ (lj) $ يساوي $ 0 $ أو $ 1 $. الحالة عندما يكون $ a_ (il) a_ (lj) = 1 $ يعني أن هناك حافتين في الرسم البياني: الحافة $ \ (i، l \) $ (منذ $ a_ (il) = 1) $ والحافة $ \ (l، j \) $ (منذ $ a_ (lj) = 1 $) ومن هنا المسار $ \ ((\ (i، l \)، \ (l، j \)) \) $ من $ i $ - الرأس th إلى $ j $ - الجزء الثاني (مسار ذو حافتين). هنا نحن نتكلميتعلق الأمر بالمسار ، وليس السلسلة ، حيث يتم الإشارة إلى الاتجاه - من الرأس $ i $ -th إلى المستوى $ j $ -th. وبالتالي ، فإن $ a_ (ij) ^ ((2)) $ يعطينا عدد جميع المسارات على الرسم البياني (في التفسير الهندسي للرسم البياني) بطول 2 من الرأس $ i $ th إلى $ j $ th واحد.

إذا كان $ k = 3 $ فإن $ A ^ 3 = A ^ 2A = AA ^ 2 = AAA $ و $ a_ (ij) ^ ((3)) = \ sum \ limits_ (l_1 = 1) ^ n (a_ (il_1 )) a_ (l_1 j) ^ ((2)) = $ $ \ sum \ limits_ (l_1 = 1) ^ n (a_ (il_1)) \ left ((\ sum \ limits_ (l_2 = 1) ^ n (a_ (l_1 l_2) a_ (l_2 j))) \ right) = $ $ \ sum \ limits_ (l_1 = 1) ^ n (\ sum \ limits_ (l_2 = 1) ^ n (a_ (il_1))) a_ (l_1 l_2) a_ (l_2 j) = \ sum \ limits_ (l_1، l_2 = 1) ^ n (a_ (il_1) a_ (l_1 l_2) a_ (l_2 j)) $.

المصطلح $ a_ (il_1) a_ (l_1 l_2) a_ (l_2 j) $ ، إذا كان يساوي 1 ، يحدد مسار الطول 3 الذي ينتقل من الرأس $ i $ إلى الرأس $ j $th و يمر عبر القمم $ l_1 $ و $ l_2 $. ثم يعطينا $ a_ (ij) ^ ((3)) $ عدد المسارات ذات الطول 3 التي تربط بين الرؤوس $ i $ th و $ j $ th. في الحالة العامةيحدد $ a_ (ij) ^ ((k)) $ عدد المسارات التي يبلغ طولها $ k $ التي تربط بين الرؤوس $ i $ th و $ j $ th. علاوة على ذلك ، $ a_ (ij) ^ ((k)) = \ sum \ limits_ (l_1، l_2، ...، l_ (k - 1) = 1) ^ n (a_ (il_1) a_ (l_1 l_2) .. .) a_ (l_ (k - 2) l_ (k - 1)) a_ (l_ (k - 1) j) $.

من الواضح أن الكمية $ a_ (ii) ^ ((k)) $ تعطينا عدد المسارات المغلقة بطول $ k $ بداية وتنتهي عند الرأس $ i $. وبالتالي ، فإن المسار الذي يبلغ طوله 2 ، $ a_ (il) a_ (li) $ ، يعني المسار الذي يمر على طول الحافة $ \ (i، l \) $ من الرأس $ i $ إلى الرأس $ l $ والعودة. لذلك $ a_ (ii) ^ ((2)) = s_i $ ، أي العناصر القطرية للمصفوفة $ A ^ 2 $ تساوي قوى الرؤوس المقابلة.

ضع في اعتبارك الآن ، جنبًا إلى جنب مع المصفوفة $ A $ ، المصفوفة $ \ dot (A) $ ، التي تختلف عن المصفوفة $ A $ فقط من حيث أن عناصرها (الأرقام 0 أو 1) تعتبر عناصر من عناصر الجبر المنطقي. لذلك ، سيتم تنفيذ الإجراءات باستخدام مثل هذه المصفوفات وفقًا لقواعد الجبر المنطقي. نظرًا لأن عمليات إضافة وضرب المصفوفات بالعناصر المنطقية يتم تقليلها إلى عمليات الجمع والضرب لعناصر هذه المصفوفات وفقًا لقواعد الحساب المنطقي ، نأمل ألا يؤدي ذلك إلى صعوبات. المصفوفة التي تحتوي على عناصر منطقية تسمى المصفوفة المنطقية Boolean matrix. من الواضح أن عمليات جمع وضرب المصفوفات المنطقية مغلقة في مجموعة المصفوفات المنطقية ، أي ستكون نتيجة هذه العمليات مرة أخرى مصفوفة منطقية.

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

ستكون نتيجة إضافة مصفوفتين متماثلتين منطقيتين من نفس الترتيب مصفوفة متماثلة منطقية من نفس الترتيب مع أصفار في تلك الأماكن حيث يحتوي كلا المصطلحين على أصفار والآحاد في تلك الأماكن حيث يكون لمصطلح واحد على الأقل وحدة. في تفسير الرسم البياني ، تسمى هذه العملية العملية إضافة الرسم البياني. مجموع رسمين بيانيين, يُطلق على نفس مجموعة الرؤوس التي لها نفس الترقيم رسمًا بيانيًا رأساه i و j غير متجاورتين إذا كانت غير متجاورة لكلا الرسمين البيانيين التلخيصيين ، والرأسمان i و j متجاورتان إذا كانتا متجاورتين على الأقل. رسم بياني تلخيصي واحد.

دعونا الآن نفسر القوة الثانية لمصفوفة التقارب المنطقي $ \ dot (A) ^ 2 $ بإدخالات $ \ dot (a) _ (ij) ^ ((2)) = \ sum \ limits_ (l = 1) ^ n (\ dot (a) _ (il) \ dot (a) _ (lj)) $. من الواضح أن $ \ dot (a) _ (ij) ^ ((2)) = 1 $ إذا كان مصطلح واحد على الأقل $ \ dot (a) _ (il) \ dot (a) _ (lj) $ يساوي إلى 1 و $ \ dot (a) _ (ij) ^ ((2)) = 0 $ إذا كانت جميع المصطلحات تساوي 0. إذا كانت المصفوفة $ \ dot (A) $ هي المصفوفة المجاورة لبعض الرسوم البيانية ، أي هي مصفوفة متماثلة (0،1) بقطر رئيسي صفري ، ثم المصفوفة $ \ dot (A) ^ 2 $ ، بشكل عام ، ليست مصفوفة مجاورة للرسم البياني بالمعنى الذي اعتمدناه ، نظرًا لأن كل المصفوفة العناصر القطرية تساوي 1 (إذا لم يكن للرسم البياني رؤوس معزولة). من أجل النظر إلى مثل هذه المصفوفات مثل المصفوفات المتجاورة ، يجب علينا ، عند النظر في الروابط بين رؤوس بعض الأنظمة المتصلة التي تعرف هذا النظام على أنه رسم بياني ، أن نقبل اتصال بعض الرؤوس ببعضها البعض. تسمى "الحافة" التي تحدد اتصال قمة معينة مع نفسها عقدة. سوف نستمر ، كما في السابق ، من خلال الرسم البياني لكلمة الرسم البياني سوف نفهم الرسم البياني بدون حلقات ، وحول الرسم البياني مع الحلقات ، إذا لم يكن هذا واضحًا من السياق ، فسنقول ذلك - رسم بياني به حلقات.

ضع في اعتبارك المجموع $ \ dot (A) ^ () = \ dot (A) + \ dot (A) ^ 2 $. تعطينا المصفوفة $ \ dot (A) ^ () $ رسمًا بيانيًا تم الحصول عليه من الرسم الأصلي عن طريق "تشبعه" بوصلات إضافية تقابل مسارات الطول 2. أي أن القمم $ i $ و $ j $ متجاورتان في الرسم البياني الجديد إذا كانت متجاورة في الرسم البياني الأصلي أو كانت هذه الرؤوس متصلة ببعض المسارات بطول 2 ، والرؤوس $ i $ و $ j $ غير متجاورتين إذا كانت غير متجاورة في الرسم البياني الأصلي وكانت هناك لا يوجد مسار بطول 2 يربط بين هذه الرؤوس.

$ \ dot (A) ^ () = \ dot (A) + \ dot (A) ^ 2 + \ dot (A) ^ 3 $ يتم تعريفه بالمثل. هذا هو ، في الرسم البياني التي قدمتها المصفوفة$ \ dot (A) ^ () $ الرؤوس $ i $ و $ j $ متجاورتان إذا كانا متجاورين في الرسم البياني $ \ dot (A) ^ () $ أو كانت هذه الرؤوس متصلة ببعض المسارات بطول 3 في الرسم البياني الأصلي والرؤوس $ i $ و $ j $ غير متجاورتين إذا كانت غير متجاورة في الرسم البياني $ \ dot (A) ^ () $ ولا يوجد مسار طول 3 يربط بين هذه الرؤوس في الرسم البياني الأصلي . وهلم جرا.

بشكل عام $ \ dot (A) ^ ([k]) = \ sum \ limits_ (i = 1) ^ k (\ dot (A) ^ i) $. من السهل ملاحظة أن كل $ \ dot (A) ^ ([k]) $ مقابل $ k \ ge n - 1 $ ، حيث $ n $ هو ترتيب المصفوفة $ \ dot (A) $ ، متساوية . في الواقع ، إذا كانت الرؤوس $ i $ و $ j $ متصلة ، فهناك مسار (سلسلة) يربط بين هذه الرؤوس ، وبالتالي ، هناك مسار بسيط (سلسلة بسيطة) يربط بين هذه الرؤوس. أقصى مسار بسيط ممكن في الرسم البياني $ n $ -vertex له طول $ n-1 $ (مسار بسيط يربط جميع الرؤوس المميزة للرسم البياني). لذلك ، إذا كان في المصفوفة $ \ dot (A) ^ () $ يوجد 1 في المكان $ (i، j) $ ، ثم في نفس المكان في المصفوفة $ \ dot (A) ^ ([k]) $ لـ $ k \ ge n - سيكون 1 $ أيضًا 1 ، حيث تم تضمين المصفوفة $ \ dot (A) ^ () $ كمصطلح منطقي في تعريف المصفوفة $ \ dot (A) ^ ([k] ) $. إذا كان في المصفوفة $ \ dot (A) ^ () $ هناك 0 بدلاً من $ (i، j) $ ، فهذا يعني أنه لا توجد سلسلة بسيطة في الرسم البياني تربط $ i $ -th و $ j $ - وبالتالي ، لا توجد سلسلة على الإطلاق تربط هذه الرؤوس. ومن ثم ، في الحالة قيد النظر وفي المصفوفة $ \ dot (A) ^ ([k]) $ مقابل $ k \ ge n - 1 $ ، سيكون المكان ($ i $ ، $ j) $ 0. هذا يثبت تأكيدنا على المساواة بين جميع المصفوفات $ \ dot (A) ^ ([k]) $ لـ $ k \ ge n - 1 $ للمصفوفة $ \ dot (A) ^ () $ وبالتالي لكل منها آخر.

المصفوفة $ \ dot (A) ^ () $ تسمى مصفوفة إغلاق المصفوفة المتعدية$ \ dot (A) $ ، بالإضافة إلى مصفوفة التقارب للإغلاق الانتقالي للرسم البياني المعطى بواسطة المصفوفة $ \ dot (A) $. من الواضح تمامًا أن مصفوفة الإغلاق الانتقالي للرسم البياني المتصل هي المصفوفة المجاورة الرسم البياني الكامل، بمعنى آخر. مصفوفة مربعةتتكون من وحدة واحدة. تعطينا هذه الملاحظة أيضًا طريقة لتحديد اتصال الرسم البياني: يرتبط الرسم البياني فقط إذا وفقط إذا كانت مصفوفة الإغلاق الانتقالي للمصفوفة المجاورة ستتألف من مصفوفة واحدة فقط (ستكون مصفوفة الرسم البياني الكامل).

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

دعونا نوضح الآن كيف يسمح لنا إجراء الإغلاق المتعدي ببناء ما يسمى "مصفوفة المسافة". للقيام بذلك ، نحدد المسافة بين الرؤوس $ i $ و $ j $. إذا تم توصيل الرؤوس $ i $ و $ j $ ، فحينئذٍ مسافه: بعدفيما بينها ، سنقوم بتسمية طول الحد الأدنى (وفقًا لعدد اجتياز الحواف) مسار بسيط يربط بين هذه الرؤوس ؛ إذا كانت الرؤوس $ i $ و $ j $ مفصولة ، فإننا نحدد المسافة مساوية للصفر (صفر على أنه نفي مسار ما يربط بين هذه الرؤوس). مع هذا التعريف للمسافة ، فإن المسافة بين الرأس ونفسها تساوي 2 (طول المسار على طول الحافة والظهر). إذا كانت هناك حلقة في الرأس ، فإن المسافة بين الرأس ونفسها تساوي 1.

لإنشاء مصفوفة مسافة لرسم بياني $ n $ -vertex مع مصفوفة مجاورة $ A $ ، والتي من شأنها أن تشير إلى المسافة بين أي رأسين ، نقدم المصفوفات $ A ^ (\ (k \)) = A ^ ([[ ك]) - A ^ () $ ، حيث $ k = 2،3، ...، n - 1 $ و $ A ^ (\ (1 \)) = A ^ () = A $. يشير غياب النقاط فوق رمز المصفوفة إلى أننا نعتبر المصفوفات $ A ^ ([k]) $ ($ k = 1،2، ...، n - 1) $ كمصفوفات عددية (0،1) ، تم الحصول عليها بشكل طبيعي من المصفوفات $ \ dot (A) ^ ([k]) $ (نعتبر الآن العناصر المنطقية 0 و 1 كالرقمين 0 و 1). يتبع من طريقة تكوين المصفوفات $ A ^ ([k]) $ أن $ A ^ ([k]) \ ge A ^ () $ ($ k = 2،3، ...، n - 1 $ ) وبالتالي فإن $ A ^ (\ (k \)) $ ($ k = 1،2، ...، n - 1 $) هي (0،1) - المصفوفات. علاوة على ذلك ، فإن المصفوفة $ A ^ (\ (2 \)) $ تحتوي على 1 فقط في تلك الأماكن التي تكون فيها الرؤوس التي يحددها هذا المكان (رقم الصف ورقم العمود) متصلة ببعض المسارات بطول اثنين وغير متصلة بمسار أصغر. طريق. وبالمثل ، يحتوي $ A ^ (\ (3 \)) $ على 1 فقط في تلك الأماكن حيث تكون الرؤوس المحددة بواسطة هذا المكان متصلة بمسار طوله ثلاثة وغير متصل بأي مسار أقل طولًا ، وهكذا. وبالتالي ، فإن المصفوفة $ D = \ sum \ limits_ (k = 1) ^ (n - 1) (k \ cdot A ^ (\ (k \))) $ ستكون مصفوفة المسافة المرغوبة. سيكون العنصر $ d_ (ij) $ لهذه المصفوفة يساوي المسافةبين الرؤوس $ i $ و $ j $. المسافة بين الرؤوس $ u $ و $ v $ سيشار إليها أيضًا على أنها $ d (u، v) $.

تعليق.منتج جمع محدد $ a_ (il_1) a_ (l_1 l_2) ... a_ (l_ (k - 2) l_ (k - 1)) a_ (l_ (k - 1) j) = 1 $ عنصر $ a_ (ij) ^ ((k)) $ $ k $ -th من المصفوفة المجاورة $ A ^ k $ تحدد $ (i، j) $ - path $ i \ (i، l_1 \) l_1 \ (l_1، l_2 \ ) l_2 ... l_ (k - 2) \ (l_ (k - 2)، l_ (k - 1) \) l_ (k - 1) \ (l_ (k - 1)، j \) j $ من $ i $ -th الرأس إلى $ j $ -th. تسلسل الرؤوس والحواف المتجاورة تربط بينهما $ i \ (i، l_1 \) l_1 \ (l_1، l_2 \) l_2 ... l_ (k - 2) \ (l_ (k - 2)، l_ (k - 1) \) l_ (k - 1) \ (l_ (k - 1)، j \) j $ يسمى أيضًا $ (i، j) $ - الطريق. يختلف المسار عن سلسلة تتكون فقط من حواف متجاورة مميزة في تلك الحواف المتساوية المسموح بها في المسار. يتكون المسار البسيط من رؤوس وحواف متجاورة مختلفة ، أي متطابقة تقريبًا مع سلسلة بسيطة.

من الواضح تمامًا أن العنصر $ d_ (ij) $ لمصفوفة المسافة يحدد طول السلسلة الدنيا التي تربط الرأس $ i $ بالرقم $ j $.

ضع في اعتبارك أمثلة على الرسوم البيانية الواردة في الشكلين 1 و 2 ، ومصفوفات تقاربها ومصفوفات مسافاتها.

الشكل 1 (رسم بياني $ \ Gamma _1 $ ، مصفوفة مجاورة $ A_1 $ ، مصفوفة المسافة $ D_1 $).
$ A_1 = \ left (((\ begin (array) (* c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \ end (مجموعة))) \ يمين) ، $
$ D_1 = \ يسار (((\ start (array) (* c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \ end (مجموعة))) \ يمين) $

أرز. 2 (رسم بياني $ \ Gamma _2 $ ، مصفوفة مجاورة $ A_2 $ ، مصفوفة المسافة $ D_2 $).
$ A_2 = \ left (((\ begin (array) (* c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \ end (array))) \ right) $ ،
$ D_2 = \ يسار (((\ start (array) (* c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \ end (array))) \ right). $

من السهل تحديد المصفوفتين $ D_1 $ و $ D_2 $ أقطار$ d_1 $ للرسم البياني $ \ Gamma _1 $ و $ d_2 $ للرسم البياني $ \ Gamma _2 $ كحد أقصى لقيم عناصر هذه المصفوفات. إذن ، $ d_1 = 3 دولارات و $ d_2 = 6 دولارات.

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

في نهاية القسم ، سنقوم بتدوين طرق تحديد الحد الأدنى والحد الأقصى للسلاسل باستخدام مصفوفة المسافات التي تربط بين الرؤوس $ i $ -th و $ j $ -th في الرسم البياني.

والآن نقدم بعض التعريفات الإضافية لنظرية الرسم البياني المتعلقة بالمسافات بين الرؤوس والتي يمكن تحديدها بسهولة من مصفوفات المسافات.

غرابة$ e (v) $ من قمة $ v $ في رسم بياني متصل $ \ Gamma $ يعرف بأنه max $ d (u، v) $ على كل الرؤوس $ u $ في $ \ Gamma $. نصف القطر$ r (\ Gamma) $ هو أصغر انحرافات في قمة الرأس. لاحظ أن أكبر الانحرافات يساوي قطر الرسم البياني. يُطلق على الرأس $ v $ الرأس المركزي للرسم البياني $ \ Gamma $ إذا كان $ e (v) = r (\ Gamma) $؛ المركزيمثل الرسم البياني $ \ Gamma $ مجموعة كل الرؤوس المركزية.

لذلك بالنسبة للرسم البياني $ \ Gamma _1 $ من الشكل 1 ، فإن الانحراف المركزي للرأس 13 سيكون مساويًا لـ 2 ($ e (13) = 2 $). سيكون للرؤوس 3 و 5 و 10 نفس الانحرافات ($ e (3) = e (5) = e (10) = 2 $). سيكون الانحراف المركزي الذي يساوي 2 هو الأصغر للرسم البياني $ \ Gamma _1 $ ، أي $ r (\ Gamma _1) = 2 دولار. سيتكون مركز الرسم البياني $ \ Gamma _1 $ من الرؤوس 3 و 5 و 10 و 13. أكبر انحراف مركزي يساوي 3 وسيكون مساويًا ، كما ذكرنا سابقًا ، لقطر الرسم البياني $ \ Gamma _1 $ .

للرسم البياني $ \ Gamma _2 $ من الشكل. في الشكل 2 ، سيكون للقمة الوحيدة 4 أصغر انحراف مركزي ($ e (4) = r (\ Gamma _2) = 3 $). لذلك ، فإن مركز الرسم البياني $ \ Gamma _2 $ يتكون من رأس واحد 4. قطر الرسم البياني $ \ Gamma _2 $ ، كما هو مذكور أعلاه ، هو 6.

الرسم البياني $ \ Gamma _2 $ عبارة عن شجرة ، ويتم وصف هيكل مركز أي شجرة بالنظرية التالية.

نظرية جوردان سيلفستر.كل شجرة لها مركز يتكون من رأس واحد أو رأسين متجاورين.

دليل - إثبات.قم بالإشارة بواسطة $ K_1 $ إلى الرسم البياني الذي يتكون من رأس واحد معزول ، و $ K_2 $ الرسم البياني لرأسين متصلين بحافة. حسب التعريف ، قمنا بتعيين $ e (K_1) = r (K_1) = 0 $. ثم سيصمد تأكيد النظرية على $ K_1 $ و $ K_2 $. دعنا نوضح أن أي شجرة $ T $ لها نفس الرؤوس المركزية للشجرة $ (T) "$ تم الحصول عليها من $ T $ عن طريق إزالة جميع الرؤوس المعلقة. من الواضح أن المسافة من رأس معين $ u $ إلى أي يمكن أن تصل قمة أخرى $ v $ أعظم قيمةفقط إذا كان $ v $ رأسًا معلقًا.

وبالتالي ، فإن الانحراف اللامركزي لكل رأس من رأس الشجرة $ (T) "$ هو بالضبط أقل من الانحراف المركزي لنفس الرأس في $ T $. الانحراف المركزي في $ (T)" $ ، أي تتطابق مراكز الأشجار $ T $ و $ (T) "$. إذا واصلنا عملية إزالة الرؤوس المعلقة ، فسنحصل على سلسلة من الأشجار بنفس مركز $ T $. نظرًا لأن $ T $ محدود ، سنصل بالضرورة إلى $ K_1 $ أو إلى $ K_2 $ على أي حال ، فإن جميع رؤوس الشجرة التي تم الحصول عليها بهذه الطريقة تشكل مركز الشجرة ، والتي تتكون بالتالي إما من رأس واحد أو رأسين متجاورين.

دعنا الآن نوضح كيف ، باستخدام مصفوفة المسافة ، يمكن للمرء تحديد ، على سبيل المثال ، الحد الأدنى للمسار الذي يربط الرأس 4 بالرأس 8 على الرسم البياني $ \ Gamma _1 $. في المصفوفة $ D_1 $ ، العنصر $ d_ (48) = 3 $. لنأخذ العمود الثامن من المصفوفة $ D_1 $ ونجد في العمود جميع عناصر هذا العمود التي تساوي 1. يمكن العثور على عنصر واحد على الأقل بسبب ارتباط الرسم البياني $ D_1 $. في الواقع ، سيكون هناك ثلاث وحدات من هذا القبيل في العمود الثامن ، وتقع في الصفوف الخامس والسادس والسابع. دعونا الآن نأخذ الصف الرابع ونأخذ في الاعتبار العناصر الموجودة في الأعمدة الخامس والسادس والسابع. ستكون هذه العناصر 2 و 3 و 3 على التوالي. فقط العنصر الموجود في العمود الخامس يساوي 2 ، ومع 1 الموجود في المكان (5،8) ، نحصل على المجموع 3. ومن ثم ، يتم تضمين الرأس 5 في السلسلة $ \ (\ (4، ؟ \)، \ (؟، 5 \)، \ (5،8 \) \) $. دعونا الآن نأخذ العمود الخامس من المصفوفة ونفكر في 1 من هذا العمود. ستكون هذه العناصر الموجودة في الخطوط 3 و 6 و 7 و 8 و 10 و 13. نعود إلى الصف الرابع مرة أخرى ونرى أنه فقط عند تقاطع العمود الثالث والصف الرابع هو 1 ، والذي ، جنبًا إلى جنب مع 1 في المكان (3،5) ، يعطي إجمالي 2. لذلك ، فإن السلسلة المرغوبة سوف يكون $ \ (\ (4،3 \) ، \ (3،5 \) ، \ (5،8 \) \) $. بالنظر الآن إلى الشكل 1 ، نحن مقتنعون بصحة الحل الموجود.

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

يترك جيهو رسم بياني n محدود.

طريقفي جيعبارة عن سلسلة من الحواف يكون لكل حافتين متجاورتين رأس مشترك:

يُطلق على عدد الحواف في المسار اسمها الطول.

طريق م اتصل طريق نظرة عامة سلسلة سلسلة بسيطة - إذا لم تتكرر رؤوسه ،

مسار تكون فيه رؤوس البداية والنهاية متماثلة ، أي. ، يسمى دورية (مغلق ).

طريق دوري م اتصل الطريق العام ، إذا تكررت الرؤوس والحواف ، دورة - إذا لم تتكرر حوافها ، دورة بسيطة - إذا لم تتكرر رؤوسه (باستثناء البداية والنهاية).

رسم بياني،لا تحتوي على دورات تسمى لا دوري.

قمم و اتصل الاتصال إذا كان هناك طريق يبدأ من وتنتهي في .

بيان - تصريح:علاقة اتصال رأس الرسم البياني هي علاقة تكافؤ وتحدد قسم رأس الرسم البياني الذي تم تعيينه في مجموعات فرعية غير متقاطعة .

العد يسمى متصل إذا كان هناك طريق يربط بينهما لأي رأسين مختلفين.

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

مسافه: بعدبين القمم أ و ب هو طول الحد الأدنى من السلسلة البسيطة التي تربط بينهما. يشار إلى المسافة د(أ, ب) .

البديهيات المترية:

1) د(أ, ب) =د(ب,أ);

2) د(أ, ب) ≥ 0, د(أ, ب) = 0 ↔ أ = ب;

3) د(أ, ب) ≤ د(أ, ج) + د(ج, ب)

مصفوفة المسافة عبارة عن مصفوفة مربعة متماثلة الأبعاد ، تتوافق صفوفها وأعمدتها مع رؤوس الرسم البياني ، ويتم تسجيل المسافة بين الرؤوس عند تقاطع الصفوف والأعمدة.

			…
			…
			…
…	…	…	…	…	…
			…

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

. (7.1)

قطر الدائرةعدد جي – أقصى مسافةبين رؤوس الرسم البياني. تم العثور على القطر من خلال الصيغة:

.

باستخدام الانحرافات التي تم العثور عليها للرؤوس ، يمكن إيجاد القطر بالصيغة:

. (7.2)

نصف القطرعدد جي – الحد الأدنى للقيمةشذوذ. تم العثور على نصف القطر بالصيغة:

. (7.3)

مركزعدد جيهو الرأس الذي.

تعليق.قد لا يكون المركز في الرسم البياني هو الوحيد.

سلسلة قطريةعدد جي قطر الدائرةيربط بين القمم البعيدة للرسم البياني.

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

مثال 7.1.

بالنسبة للرسم البياني n الموضح في الشكل 7.1 ، اكتب 1) مسارًا عامًا ، 2) دائرة غير بسيطة ، 3) دائرة بسيطة ، 4) مسار دوري عام ، 5) دورة غير بسيطة ، 6) دائرة بسيطة دورة.

المحلول:

1) المسار العام هو مسار تختلف فيه رؤوس البداية والنهاية وتتكرر بعض الحواف. م 1 = (1, 4 , 5, 1, 4 ، 7 ، 3). هنا تتكرر الحافة (1 ، 4).

2) ليست سلسلة بسيطة - هذا مسار لا تتكرر فيه الحواف ، ولكن تتكرر الرؤوس. م 2 = (4, 3, 1 , 5, 6, 7 , 4, 1 ). يتكرر الذروة 1 هنا.

3) السلسلة البسيطة هي طريق لا تتكرر فيه القمم. م 3 = (4, 3, 7, 5, 6).

4) المسار الدوري العام هو مسار تتطابق فيه رؤوس البداية والنهاية وتتكرر بعض الحواف. م 4 = (1, 5 , 1, 5 , 1 ). هنا تتكرر الحافة (1 ، 5).

الشكل 7.1. طرق البناء

في رسم بياني غير موجه

5) الدورة غير البسيطة هي مسار دوري لا تتكرر فيه الحواف ، بل تتكرر الرؤوس. م 5 = (3, 4 , 5, 7, 4 ، 13). تتكرر الذروة 4 هنا.

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

6) الدورة البسيطة هي مسار دوري لا تتكرر فيه أي رؤوس. م 6 = (5, 4, 3, 2, 1, 5).

مثال 7.2.

بالنسبة للرسم البياني n الموضح في الشكل 7.1 ، قم ببناء مصفوفة المسافة. حدد قطر ونصف قطر الرسم البياني. حدد مراكز الرسم البياني. سجل سلاسل قطرية وشعاعية

المحلول:

لبناء مصفوفة مسافة ، دعنا نقارن الصفوف والأعمدة بالرؤوس. عند تقاطع الصفوف والأعمدة ، نشير إلى المسافة بين الرؤوس المقابلة.

د( أ, ب)	1	2	3	4	5	6	7
1	0	1	1	1	1	2	2	2
2	1	0	1	2	2	3	2	3
3	1	1	0	1	2	2	1	2
4	1	2	1	0	1	2	1	2
5	1	2	2	1	0	1	1	2
6	2	3	2	2	1	0	1	3
7	2	2	1	1	1	1	0	2

الموضع (1 ، 1) هو 0 ، لأن أقصر طريق بين الرأس 1 والرأس 1 هو طريق متدهور (بدون حواف) بطول 0.

الموضع (1 ، 2) هو 1 ، لأن أقصر طريق بين الرأس 1 والرأس 2 هو الحافة الوحيدة التي تربط هذه الرؤوس.

في المكان (1 ، 6) يقف 2 ، لأن أقصر مسار بسيط بين الرأس 1 والرأس 6 هو سلسلة من حافتين (1 ، 5 ، 6). إذن ، المسافة بين هذه الرؤوس هي 2.

يُظهر العمود الأخير من الجدول المسافة من قمة معينة إلى الرأس الأبعد عنها - الانحراف. تم العثور على قيمها بواسطة الصيغة (7.1).

الحد الأقصى لقيمة العمود الأخير هو قطر الرسم البياني. أين د(جي) = 3.

الحد الأدنى لقيمة العمود الأخير هو نصف قطر الرسم البياني. أين ص(جي) = 2.

المراكز هي الرؤوس: 1 ، 3 ، 4 ، 5 ، 7. الانحرافات المركزية بينهما تساوي نصف قطر الرسم البياني.

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

د 1 = (2 ، 1 ، 5 ، 6) و د 2 = (2, 3, 7, 6).

لبناء سلاسل شعاعية ، نستخدم مصفوفة المسافة لمعرفة الرءوس الأبعد عن المراكز.

يقع الرأسان 6 و 7 على مسافة نصف قطر 2 من المركز 1. وهذا يعني أنه يمكن رسم السلاسل الشعاعية:

ص 1 = (1 ، 5 ، 6) و ص 2 = (1, 4, 7).

يقع الرأسان 5 و 6 على مسافة نصف قطر من المركز 3. وهذا يعني أنه يمكن رسم السلاسل الشعاعية:

ص 3 = (3 ، 4 ، 5) و ص 4 = (3, 7, 6).

يعد حساب المسافات وتحديد المسارات في الرسم البياني من أكثر المشكلات وضوحًا وعملية التي تنشأ في نظرية الرسم البياني. دعونا نقدم بعض التعريفات الضرورية.

غرابةرؤوس الرسم البياني - المسافة إلى الرأس الأبعد عنه. للرسم البياني الذي لم يتم تعريفه الوزن حوافها ، يتم تعريف المسافة على أنها عدد الحواف.

نصف القطرالرسم البياني هو الحد الأدنى من الانحراف اللامركزي للرؤوس ، و قطر الدائرة الرسم البياني هو أقصى انحراف مركزي للرؤوس.

مركزشكل الرسم البياني الرؤوس التي غريب الأطوار يساوي نصف القطر. يمكن أن يتكون مركز الرسم البياني من رأس رسم بياني واحد أو عدة رؤوس أو كلها.

هامشيالقمم لها انحراف يساوي القطر.

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

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

نظرية 12.2.(الأردن) لكل شجرة مركز يتكون من رأس أو رأسين متجاورين.

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

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

مثال 12.5.أوجد نصف قطر وقطر ومركز الرسم البياني الموضح في الشكل. 12.1.

المحلول.في هذه المشكلة ، إنه مناسب للاستخدام مصفوفة المسافة S.. عنصر هذه المصفوفة المتماثلة المربعة يساوي المسافة بين الرأس أناوأعلى ي. للرسم البياني الموضح في الشكل. 12.1 ، مصفوفة المسافة لديها العرض التالي:

دعونا نحسب الانحراف المركزي لكل رأس. يمكن تعريف هذه القيمة على أنها الحد الأقصى لعنصر العمود المقابل لمصفوفة المسافة (أو الصف ، منذ المصفوفة سمتماثل). نحن نحصل

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

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

نظرية 12.4. اسمحوا أن تكون المصفوفة المجاورة للرسم البياني G بدون حلقات وأين. ثم يساوي عدد مسارات الطول k من الرأس إلى الرأس.

يسمى حل مشاكل نظرية الرسم البياني باستخدام تحويلات مختلفة لمصفوفة الجوار الطريقة الجبرية .

مثال 12.6.أوجد مصفوفة المسافة للرسم البياني الموضح في الشكل. 12.1 ، بالطريقة الجبرية.

المحلول.مصفوفة الجوار لهذا الرسم البياني هي:

سنملأ مصفوفة المسافة من خلال النظر في درجات مصفوفة الجوار. تُظهر وحدات مصفوفة الجوار أزواج من الرؤوس التي لها مسافة واحدة بينها (أي أنها متصلة بحافة واحدة).

العناصر القطرية لمصفوفة المسافة هي أصفار. اضرب المصفوفة المجاورة في نفسها:

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

تبقى المسافة بين الرأسين 1 و 3. غير معروفة سنضرب المصفوفة المجاورة على نفسها حتى المصفوفة لن يظهر عنصر غير فارغ . ثم العنصر المقابل لمصفوفة المسافة يساوي الدرجةالمصفوفات المتجاورة: . في الخطوة التالية ، وصلنا

بالتالي، و اخيرا

المصفوفة الناتجة تتوافق مع مصفوفة المسافة س(12.2) تم العثور عليها من خلال الحسابات المباشرة من الشكل.

1. تعيين ص=1 (ص هو عدد المكونات المتصلة) ،.

2. قم بتضمين مجموعة الرؤوس الخامس ص المكونات المتصلة بقوة د صالرؤوس المقابلة لوحدات الصف الأول من المصفوفة س ص . كمصفوفة أ(د ص) خذ مصفوفة فرعية من المصفوفة أ(د أالخامس ص .

3. شطب من س صالصفوف والأعمدة المقابلة للرؤوس من الخامس ص. إذا لم يكن هناك صف (وعمود) على اليسار ، فحينئذٍ صهو عدد المكونات المتصلة بقوة. خلاف ذلك ، فإننا نشير إلى المصفوفة المتبقية بعد حذف المصطلح والأعمدة كـ س ص +1 ، تعيين ص= ص+1 وانتقل إلى الخطوة 2.

مثال

دعونا نفرد المكونات المتصلة للرسم البياني الموجه الموضح في الشكل. 1. في هذه المسألة ، عدد الرؤوس ن= 5.

لذلك ، بالنسبة للرسم البياني الموجه ، سيكون لمصفوفة التقارب أبعاد 5 × 5 وستبدو هكذا

.

لنجد مصفوفة قابلية الوصول لهذا الرسم البياني الموجه باستخدام الصيغة 1) من العبارة 3:

,
,

,

بالتالي،

.

وبالتالي ، فإن المصفوفة شديدة الارتباط التي تم الحصول عليها بواسطة الصيغة 2) من البيان 3 ستكون على النحو التالي:

.

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

تحذف من المصفوفة س 1 (د) الصف والعمود المقابل للأعلى الخامس 1 للحصول على المصفوفة س 2 (د):

.

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

.

تحذف من المصفوفة س 2 (د) الصفوف والأعمدة المقابلة للرؤوس من الخامس 2 للحصول على المصفوفة س 3 (د) ، والتي تتكون من عنصر واحد:

والتنازل ص= 3. وهكذا ، فإن المكون الثالث المتصل بقوة في الرسم البياني الأصلي ، مثل المكون الأول ، يتكون من رأس واحد
.

وبالتالي ، يتم تحديد 3 مكونات مرتبطة بقوة في الرسم البياني الموجه د:

المهمة 2. المسافات في رسم بياني موجه

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

يترك
رسم بياني موجه مع رؤوس n³2 و الخامس,ث (الخامس¹ ث) – رؤوس معينةمن الخامس.

خوارزمية لإيجاد المسار الأدنى من B في رسم بياني موجه

(خوارزمية جبهة الموجة).

خلاف ذلك ، نواصل:

خلاف ذلك ، وجدنا المسار الأدنى من في
وطوله ك. تسلسل الرأس

هناك هذا الحد الأدنى من المسار. يتم الانتهاء من العمل.

ملاحظات

لإيجاد مسافات في رسم بياني موجه ، تحتاج إلى عمل مصفوفة من أدنى مسافات ص(د) بين رؤوسه. هذه مصفوفة مربعة الأبعاد
، التي تساوي عناصرها القطرية الرئيسية الصفر (
,أنا=1,..,ن).

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

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

ملحوظة: في الاختبار ، ابحث عن أطول مسار باستخدام خوارزمية مقدمة الموجة.

مثال

ابحث عن المسافات في رسم بياني موجه دهو مبين في الشكل. 2. في هذه المسألة ، عدد الرؤوس ن= 7 ، ومن هنا تأتي مصفوفات الجوار والمسافات الدنيا بين رؤوس الرسم البياني الموجه د سيكون له البعد 7 × 7.

مصفوفة الجوار:

.

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

وبالتالي ، سيكون قطر الرسم البياني الموجه المدروس
.

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

ص(الخامس 1)=3, ص(الخامس 2)=3, ص(الخامس 3)=5, ص(الخامس 4)=4, ص(الخامس 5)=2, ص(الخامس 6)=2, ص(الخامس 7)=3.

لذا فإن نصف القطر عدد جيسوف يكون

تبعا لذلك ، مراكز الرسم البياني جي ستكون هناك قمم الخامس 5 و الخامس 6 ، نظرًا لأن قيم الانحرافات الخاصة بهم تتطابق مع قيمة نصف القطر
.

دعونا الآن نصف إيجاد المسار الأدنى من الرأس الخامس 3 في الأعلى الخامس 6 وفقًا لخوارزمية جبهة الموجة. دلالة على قمة الرأس الخامس 3 مثل الخامس 0 ، والأعلى الخامس 6 - كيف دبليو(انظر الشكل 3). مجموعة القمم التي تنتمي إلى الصورة الخامس 0 ، يتكون من عنصر واحد - هذا هو الجزء العلوي الخامس 4 ، وفقًا للخوارزمية ، يُشار إليها بـ الخامس 1: مهاجم 1 (الخامس 3)={الخامسأربعة). لأن القمة المرغوبة لا تنتمي إلى مقدمة الموجة للمستوى الأول
، نواصل الخوارزمية. نبني مقدمة الموجة للمستوى الثاني - هذه هي مجموعة الرؤوس التي تنتمي إلى صورة الرأس الخامس 1: مهاجم 2 (الخامس 3)={الخامس 7) ، دلالة الخامس 7 ≡الخامس 2. في صورة القمة الخامس 2 يتضمن رأسين - الخامس 5 و الخامس 4 ، ولكن منذ ذلك الحين الخامستم بالفعل وضع علامة على 4 كـ الخامس 0 ، ثم تتكون مقدمة الموجة للمستوى الثالث من عنصر واحد: مهاجم 3 (الخامس 3)={الخامس 5 }, الخامس 5 ≡الخامس 3. من الرؤوس غير المسماة إلى صورة الرأس الخامس 3 متضمن الخامس 1 و الخامس 2 ، على التوالي ، مهاجم 4 (الخامس 3)={الخامس 1 , الخامس 2 }, الخامس 1 ≡الخامس 4 , الخامس 2 ≡الخامسأربعة. الآن يتم تصنيف جميع الرؤوس باستثناء الخامس 6 ، والتي تم تضمينها في صورة الرأس
، هذا هو مهاجم 5 (الخامس 3)={الخامس 6 ≡دبليو) ، تم الانتهاء من الخوارزمية. الحد الأدنى للمسار (5 خطوات) من الأعلى الخامس 3 في الأعلى الخامس 6 يشبه هذا: الخامس 3 الخامس 4 الخامس 7 الخامس 5 الخامس 1 الخامس 6 .