ما هي عقدة المسيطر والشجرة المسيطرية؟

Question

حاولت قراءة ويكيبيديا حول المهيمن (نظرية الرسم البياني) ، الذي يعطي التعريف التالي للعقدة المسيطرية:

يهيمن

A NODE D NODE N إذا كان كل مسار من عقدة الإدخال إلى N يجب أن تمر عبر د.

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

هذا هو الرسم البياني:

p> href="https://i.stack.imgur.com/cpnks.png" rel="nofollow noreferrer">

يجب أن يكون هذا شجرة مهتنة للرسم البياني أعلاه:

href="https://i.stack.imgur.com/fkvnz.png" rel="nofollow noreferrer">

بناء على التعريف أعلاه، أعتقد

node 2 يهيمن على العقدة 3 لأن كل مسار من 3 يجب أن تمر عبر 2. لماذا؟ للذهاب من 3 إلى نفسه، يجب أن أذهب إلى 2. لهذا السبب يذهب 2 إلى 3 في شجرة المسيطر.

هل أفكر في الحق؟

هل يمكنني معرفة أيضا لماذا هذا مفيد في المجمعين؟

Answer 1

السبب الذي تعطيه ليس صحيحا تماما؛ يعمل تعريف العقدة المسيطرية من عقدة البدء ( $ 1 $ في المثال). الطريقة الوحيدة للوصول إلى $ 3 $ من $ 1 $ هي الذهاب من خلال $ 2 $ كما هو العقدة الخليفة الوحيد من $ 1 $ في الرسم البياني المحدد. وبالتالي $ 2 $ يهيمن على $ 3 $ . لسبب نفس السبب، فإن العقد 4 دولارات $ من خلال 6 دولارات $ تهيمن عليها أيضا $ 2 دولار ، $ 2 $ الفوري المسيطر الفوري لهذه العقد (ك $ 1 $ يهيمن $ 2 $ ) ولا تهيمن هذه العقدات أيضا على أي عقد آخر من $ 1 $ و $ 2 $ :

• li> 3 دولارات، 4 دولارات و يمكن الوصول إليها على الفور 6 $ $ على الفور من $ 1 $ عبر $ 2 $ .
• يمكن الوصول إلى $ 5 $ من $ 2 $ إما عن طريق $ 3 $ أو 4 دولارات $ ، وبالتالي فإن العقد الشائعة الوحيدة في هذه المسارات إلى $ 5 $ هي $ 1 $ و $ 2 $ .

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

giveacodicetagpre.

هنا، تهيمن الكتلة التي تتكون من السطرين الأولين على كتلة IF وكذلك الكتلة الأخرى. وبالتالي نحن نعلم أنه بحلول الوقت الذي نقفز فيه إلى كتلة إذا كنا نحدد B إلى TRUE، يتم تعيينه بالفعل على True من قبل كتلة قبضة، وبالتالي يمكن للمترجم تحسين الرمز عن طريق حذف المهمة في كتلة IF.

يمكنك أيضا اكتشاف الحلقات في التعليمات البرمجية عن طريق تحليله إذا كان لدى CFG حواف من النموذج $ b '\ to b $ أين مرة أخرى $ B $ يهيمن على $ b $ . يشير هذا المسار إلى وجود حلقة حيث $ B $ سيمثل رأس حلقة أثناء $ B '$ هو (آخر) جزء من الجسم حلقة.