قم ببناء DAG من ترتيبات طوبولوجية متعددة معينة

Question

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

1. يجب أن يكون الحد الأقصى للدرجة الخارجية لكل عقدة 1
2. يجب أن يكون عدد العقد التي تحتوي على درجة 0 هو الحد الأدنى.

يمكن أن يكون هناك حلول متعددة، أي واحد منهم يجب أن يعمل.

ما حاولت.(النهج 1 وهو خطأ لأنه فشل في أحد الأمثلة الواردة في الإجابة.يرجى التمرير إلى الطريقة الثانية، والتي ما زلت غير قادر على العثور على خطأ.)

النهج 1
من جميع الطلبات المقدمة، قم أولاً بإنشاء رسم بياني موجه عن طريق إنشاء حافة موجهة من كل عقدة إلى العقدة التالية.يعني إذا كانت الطلبات هي:
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

سأقوم بإنشاء رسم بياني موجه بحافة موجهة من $1$ ل $3, 3$ ل $2, 2$ ل $5$ وهكذا دواليك.

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

تم إنشاء DAG هذا، ويتبع كلا القيودين، ولدى IMO الحد الأدنى لعدد العقد من الدرجة الداخلية وهو 0، على الرغم من أنه لم يتم إثبات ذلك.

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

النهج 2
أقوم بإنشاء رسم بياني موجه $ج$ عن طريق إنشاء حافة من $أ_ي $ ل $a_j$ للجميع $ ي > أنا $ في جميع الطلبات المقدمة.لذلك بالنسبة للأوامر:
$$ 1, 2, 3, 4, 5$$ $$ 2, 4, 1, 5, 3$$

سأقوم بإنشاء الرسم البياني التالي:
الخطوة الأولى بعد ذلك هي التحقق من صحة كافة الطلبات.ليس من الضروري إزالة الدورات بشكل منفصل حيث سيتم إزالتها بهذه الخطوة نفسها.
لأي طلب$$ a_1، a_2، a_3، a_4، ...أ_ن $$سوف أتحقق مما إذا كان هناك أي حافة من $a_j$ ل $a_i$ أين $ ي > أنا $, ، سأزيل تلك الحافة.
سيؤدي القيام بذلك إلى ظهور الرسم البياني التالي:
الخطوة الأخيرة هي إزالة الحواف الإضافية من جميع العقد بأقصى درجة ممكنة لأي عقدة $1$ الأعلى.سأقوم بإزالة الحواف الصادرة بحيث يكون عدد العقد بالدرجة $0$ هو الحد الأدنى.أولاً أقوم بحساب درجة كل عقدة.ثم بالنسبة لكل عقدة تحتوي على أكثر من حافة واحدة صادرة، سأقوم بإزالة جميع الحواف باستثناء تلك ذات الحد الأدنى من الدرجة.

الرسم البياني النهائي $ج$ سوف تبدو مثل:

هذا الرسم البياني يلبي كلا القيود.لكنني أعلم أن هذا النهج خاطئ!يمكن لأي شخص أن يساعد في العثور على سبب هذا الخطأ؟

Answer 1

النهج 1

على سبيل المثال، النظر في الأمرين:1، 2، 3، 4، 5 و 2، 4، 1، 5، 3.

وفقًا لمنهجك، سنحصل على دورة 1->2->3->4->1.نقوم بعد ذلك بإزالة 3->4 و4->1، ونحصل على رسم بياني:

     ______
    /      \
1->2->4->5->3
 \______/

الآن 5->3 و1->2 على التوالي ينتهك الأمرين الأول والثاني، لذلك نقوم بإزالتهما، ونحصل على

     ______
    /      \
1  2->4->5  3
 \______/

الآن العقدة 2 لها حافتان صادرتان.تؤدي إزالة أي منهما إلى إنشاء رسم بياني نهائي حيث تكون 3 عقد (1، 2، 3 أو 1، 2، 4) في الدرجة 0.

ومع ذلك، هناك رسم بياني

1->3 2->4->5

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

لذا فإن النهج 1 غير صحيح.

النهج 2

النظر في الحل الأمثل.كل حافة في هذا الحل الأمثل يجب أن تكون بالشكل $(a_i,a_j)$ أين $أنا<ي$ في كل أمر.وهذا يعني أن جميع الحواف في الحل الأمثل موجودة في الرسم البياني المتوسط.لذا، إذا قمت بعد ذلك بإزالة الحواف الصادرة بحيث يكون عدد العقد التي تحتوي على الدرجة 0 هو الحد الأدنى، فستحصل على الحل الأمثل الصحيح.

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

على سبيل المثال، النظر في الأوامر الثلاثة:تبدأ {align} 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 5 ، 1 ، 6 ، 3 ، 8 ، 2 ، 4 ، 7 2 ، 7 ، 3 ، 8 ، 1 ، 4 ، 5 ، 6 end {align}

أولاً يمكننا الحصول على الرسم البياني الوسيط التالي:

    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

بتطبيق النهج الخاص بك، سنقوم بإزالة 1->4، 2->4 و3->4 (أو 3->8)، وهناك 5 عقد مع الدرجة 0:1، 2، 3، 4 (أو 8)، 5.ومع ذلك، فإن الحل الأمثل سيكون

     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

حيث تحتوي 4 عقد فقط على الدرجة 0:1، 2، 3، 5.