البطولة الرسم البياني

Question

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

هيكل البيانات مصفوفة الجوار.

ما ق خوارزمية لإيجاد إذا كان الرسم البياني هو البطولة البيانية ؟

Answer 1

وهناك ن ^ 2 الإدخالات في مصفوفة الجوار، وكنت في حاجة إلى المعلومات التي هي في كل من الإدخالات إلى حل المشكلة. (أنت في حاجة 1 للتحقق من أن حواف المناسبة موجودة، و0 للتحقق من أن حواف الظهر لا وجود لها.) وهكذا لأن لديك لقراءة على الأقل 2 N ^ الإدخالات من المصفوفة، يجب أن تأخذ المشكلة العامة O ما لا يقل عن (N ^ 2) وقت.

وفيما يتعلق محاولات البحث BFS: إذا اجتياز الخاص بك يأخذ O (ن ^ 2) - الذي سيكون، نظرا للحاجة للبحث عن حواف في مصفوفة الجوار - ثم لا يهم إذا كان الاختيار يعود الحافة هو ثابت الوقت، الخوارزمية العامة لا تزال O (ن ^ 2).

وطريقة أخرى للنظر في هذه المشكلة: منذ عدد من حواف يساوي عدد أزواج ممكنة من القمم، سيكون هناك ن * (ن 1) / 2 الحواف، وهو O (ن ^ 2) . اجتياز الخاص بك هو O (V + E)، والتي بالتالي هي O (ن + ن ^ 2)، وبالتالي هي O (ن ^ 2).

ومنذ ذلك الوقت أفضل حالة لهذا الخوارزمية O (ن ^ 2)، بالاضافة الى انك قد مجرد حلقة من خلال النصف الأيسر العلوي من المصفوفة (فوق القطري) والتحقق من أن لكل من هذه القيود، إما ) هو 1، أو ب) ما يعادل تبديل لها هو 1.

Answer 2

وتحرير: غاب عن الجزء حيث كان الرسم البياني الكامل

.

إذا M هو مصفوفة الجوار بك، Mt هو مصفوفة نقلها، ~M هو مصفوفة مع كل "بت" مقلوب، وA^B هو بت XOR فشيئا بين اثنين المصفوفة.

وثم المصفوفة هو المنتدى البطولة:

و~(M^Mt) = I

Answer 3

إضافة إلى tonfa تعليق:

مختصر:الخوارزمية "لكل i ≠ j, تحقق لمعرفة ما الذي بالضبط واحدة من (i,j) و (ي ، ط) في الرسم البياني الخاص بك" هو مقارب الأمثل.

مزيد من التفاصيل: مجرد قراءة في مصفوفة الجوار هو ذاهب الى اتخاذ لكم Ω(n²) مرة.لذلك ليس هناك طريقة لحل هذه المشكلة في o(n²) مرة.ولكن دعونا نتجاهل الإدخال.

لنفترض أن المصفوفة هي بالفعل في الذاكرة.لضمان أن صليات نسخة من الرسم البياني الخاص بك هو الكامل, عليك أن تحدد بطريقة أو بأخرى أن لكل i ≠ j, واحد على الأقل من حواف (i,j) (j,i) هو في الرسم البياني الخاص بك.لديك فقط الجوار الرسم البياني ، وهذا يعني سيكون لديك أن في بعض نقطة في زيارة واحدة على الأقل من (i,j) أو (j,i) لكل i ≠ j.لا توجد وسيلة أخرى لضمان اكتمالها.التحقق من هذا سوف يستغرق n(n+1)/2 = O(n² خطوات).