إثبات الصحة:خوارزمية قطر الشجرة في نظرية الرسم البياني

Question

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

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

أى أفكار كانت لتقدر أكثر...

Answer 1

دعونا نسمي نقطة النهاية الموجودة بنقطة BFS الأولى. تثبت الخطوة الحاسمة أن X الموجود في هذه الخطوة الأولى دائما "يعمل" - وهذا هو دائما في نهاية واحدة من أطول مسار. (لاحظ أنه بشكل عام، يمكن أن يكون هناك أكثر من مجرد مسار أطول على قدم المساواة.) إذا استطعنا تأسيس هذا، فمن الواضح أن نرى أن BFS الجذور في X ستجد بعض العقدة قدر الإمكان من X، والتي يجب أن تكون بشكل عام أطول مسار.

تلميح: لنفترض (على العكس من ذلك) أن هناك مسار أطول بين رأيتين يو و v، لا أي منها س.

لاحظ ذلك، على المسار الفريد بينك وبين V، يجب أن يكون هناك بعض أعلى (الأقرب إلى الجذر) قمة الرأس. هناك احتمالان: إما H موجود على الطريق من جذر BFS إلى X، أو أنه ليس كذلك. إظهار تناقض من خلال إظهار أنه في كلتا الحالتين، يمكن إجراء مسار U-V على الأقل طالما استبدال بعض مقاطع المسار في طريقه إلى مسار إلى x.

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

<تحرير 2] في بعض قمة الرأس، ليس بالضرورة في أعلى نقطة في أعلى نقطة H)؛ و (2) لا يفعل ذلك. ما زلنا بحاجة إلى H لإثبات كل حالة.

Answer 2

انا ذاهب الى العمل بها تلميح j_random_hacker.يترك s, t يكون زوجًا بعيدًا إلى أقصى حد.يترك u تكون قمة التعسفي.لدينا مثل التخطيطي

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

أين x هو تقاطع s, t, u (أي.الرأس الفريد الذي يقع على كل من المسارات الثلاثة الواقعة بين هذه القمم).

لنفترض أن v هي قمة بعيدة إلى أقصى حد u.إذا كان التخطيطي يبدو الآن

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

ثم

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

حيث يحمل عدم المساواة لأن d(u, t) = d(u, x) + d(x, t) و d(u, v) = d(u, x) + d(x, v).هناك حالة متماثلة حيث v يعلق بين s و x بدلا من بين x و t.

الحالة الأخرى تبدو كذلك

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

الآن،

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

لذا max(d(v, s), d(v, t)) >= d(s, t) بواسطة حجة متوسطة، و v ينتمي إلى زوج بعيد إلى أقصى حد.

Answer 3

إليك طريقة بديلة للنظر إليها:

يفترض ز = ( الخامس, ه ) هي شجرة غير فارغة ومحدودة مع مجموعة قمة الخامس ومجموعة الحافة ه.

خذ بعين الاعتبار الخوارزمية التالية:

1. يترك عدد = 0.دع جميع الحواف تدخل ه في البداية تكون غير ملونة.يترك ج في البداية تكون مساوية ل الخامس.
2. النظر في المجموعة الفرعية الخامس' ل الخامس تحتوي على جميع القمم مع حافة واحدة غير ملونة بالضبط:
   • لو الخامس' فارغة ثم السماح د = عدد *2، وتوقف.
   • لو الخامسيحتوي على عنصرين بالضبط ثم قم بتلوين حافتهما المتبادلة (غير الملونة) باللون الأخضر، دع د = عدد *2+1، وتوقف.
   • خلاف ذلك، الخامس' يحتوي على ثلاثة رؤوس على الأقل؛استكمل كما يلي:
3. زيادة راتب عدد بواحد.
4. إزالة كافة القمم من ج التي ليس لها حواف غير ملونة.
5. لكل قمة في الخامس مع حافتين أو أكثر غير ملونة، قم بإعادة تلوين كل من حوافها الخضراء باللون الأحمر (قد لا تحتوي بعض القمم على مثل هذه الحواف).
6. لكل قمة في الخامس"، قم بتلوين حوافها غير الملونة باللون الأخضر.
7. العودة إلى الخطوة (2).

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

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

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

---

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

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

Answer 4

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)