اكتشف دورات الوزن الإجمالي الفردي في رسم بياني بحواف مرجحة {0,1}.

Question

نظرا لdigraph الحافة المرجحة $G = (V, E \subseteq V^2, w \in E o \{0, 1\})$, هل هناك خوارزمية ترجع TRUE إذا كانت هناك دورة في هذا الرسم البياني يكون وزنها الإجمالي فرديًا و FALSE خلاف ذلك، والذي يعمل بشكل أسرع من $O((|V| + |E|)(c + 1))$ (أين $ج$ هو عدد الدورات البسيطة في الرسم البياني، وهو بالطبع $\أوميغا(2^{|V|})$)?

كما يوحي السؤال، لقد توصلت بالفعل إلى خوارزمية تعمل $O((|V| + |E|)(c + 1))$ وقت.تتضمن هذه الخوارزمية التشغيل الأول خوارزمية تعداد الدورة البسيطة لجونسون, ، والذي يعطينا جميع الدورات البسيطة في الرسم البياني.منذ even + even = even, ، ويتم إنشاء جميع الدورات عن طريق جمع دورات بسيطة معًا، ويحتوي الرسم البياني على دورة ذات طول فردي إذا كانت تحتوي على دورة بسيطة ذات طول فردي.وهكذا، نحن فقط نحسب التكافؤ في الدورات البسيطة والعودة TRUE إذا كان أي منهم غريبا، و FALSE خلاف ذلك.

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

Answer 1

يمكنك حل هذا في $O(|V| \cdot |E|)$ وقت.

بناء ديغراف مع رؤوس النموذج $\langle v,b angle$ أين $v \في V$, $ب \في \{0,1\}$, ، على النحو التالي:لكل حافة $v \stackrel{t}{ o} w$ في الرسم البياني الخاص بك، أضف الحواف $\langle v,b angle o \langle w,b + t \bmod 2 angle$ لكل $ب \في \{0,1\}$ إلى الرسم البياني الجديد.

ثم لكل $v \في V$, ، تحقق مما إذا كان هناك مسار من $\langle v,0 angle$ ل $\langle v,1 angle$ او من $\langle v, 1 angle$ ل $\langle v,0 angle$ في هذا الرسم البياني الجديد.يمكن القيام بذلك من خلال عمليتي بحث DFS لكل قمة $v \في V$;يستغرق كل بحث DFS $O(|E|)$ الوقت، وبالتالي فإن إجمالي وقت التشغيل هو $O(|V| \cdot |E|)$ وقت.يمكن تسريع البحث عن طريق تحليل الرسم البياني الجديد إلى مكونات مرتبطة بقوة مرة واحدة ثم البحث في يوم المكونات (الميتاغراف).

Answer 2

بناء مصفوفة حدوث قمة الرأس:تتوافق الصفوف مع الحواف، والأعمدة مع القمم، وهناك $1$ إذا كانت الحافة حادثة للقمة.إضافة أعمدة أخرى مليئة $1$'س.تريد معرفة ما إذا كانت هناك مجموعة فرعية من الصفوف التي تلخص المتجه $0،\lالنقاط،0،1$ (النموذج 2).يمكنك معرفة ذلك باستخدام الحذف الغوسي، في زمن كثير الحدود.

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

وذلك بإضافة إضافية $1$ العمود إلى المصفوفة، فإننا نتتبع تكافؤ الدورة.دورات فردية تلخص المتجه $0،\lالنقاط،0،1$.على العكس من ذلك، إذا كانت مجموعة من الصفوف مجموع $0،\lالنقاط،0،1$, ، فهو يتوافق مع مجموعة من الدورات التي طولها الإجمالي فردي، فإحدى الدورات فردية.

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