هل هناك مصطلح لهذه الأساس "النزول" من الرسوم البيانية الدراسية الموجهة نحو الدراجات؟

Question

النظر في الرسم البياني الدراسي الموجه $ g $ مع قمة الرأس مجموعة $ v $ .اختر Vertex $ v $ ، ودع $ h $ يكون subgraph يحتوي على $ v $ وجميع القمم الأخرى في $ g $ يمكن الوصول إليها من $ v $ (جنبا إلى جنب مع الحواف الموجهة المرتبطة).

(بمعنى آخر، إذا اخترنا $ v \ in v $ ، ثم نحن مهتمون بالمجموعة الفرعية التي تتكون من $ v $ وجميع أحفادها).

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

Answer 1

نوع من. لكننا سوف نستخدم طريقة علم الكمبيوتر المعتادة لوصف هذا، باستخدام لغة العلاقات الثنائية .

ربما كنت على دراية بالفعل بالعلاقات الثنائية، مثل المساواة $= $= $ ، أقل غير متساو إلى $ \ LE $ ، مجموعة فرعية $ \ subseteq $ ، وهلم جرا. بشكل عام، العلاقة الثنائية $ r $ عبر مجموعة $ x $ هي مجموعة فرعية $ r \ subseteq x \ times x $ . إذا $ (x، y) \ in r $ ، نحن ندلح هذا ك $ xry $ .

إذا كان $ \ forall x \ in x، xrx $ ، ثم $ r $ هو الانعكاس . العلاقات $= $ و $ \ JO $ هي انعكاسية، ولكن $ \ LT $ ليست كذلك.

إذا كان $ \ forall x، y، z \ in x، xry \، wedge \ jrz \ charnarrow xrz $ ، ثم $ r $ هو متعدية . الكثير من العلاقات متعدية، بما في ذلك جميع تلك الواردة أعلاه. إذا $ x \ le y $ and $ y \ le z $ ، ثم $ x \ le z $ .

إعطاء العلاقة $ r $ إغلاق غير مردود من $ r $ < / span> undered $ r ^ * $ ، هل أصغر علاقة $ r ^ * $ مثل ذلك $ r \ subseteq r ^ * $ ، و $ r ^ * $ deflexive and overizive.

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

عند النظر إلى الأدب، ستحتاج إلى معرفة قطعة أخرى من الترميز: إغلاق متعاقد من $ r $ $ r ^ + $ ، هل أصغر علاقة $ r ^ + $ مثل $ r \ subseteq r ^ + $ ، و $ r ^ + $ متعدية. خوارزميات لحساب الإغلاق المتعدود والإغلاق المتعدود المنعكس مرتبطا، لأنها تختلف فقط من قبل إدخالات "قطري": $ r ^ + \ cup \ left \ {(x، x) \، | \، x \ in x \ right \}= r ^ * $ .

هناك العديد من الخوارزميات القياسية لتحسين RTC من العلاقة. إذا كانت العلاقة كثيفة، بمعنى أنه من الممكن تمثيله كصفوفة قليلا، فإن خوارزمية Floyd-Warshall هي واحدة من أسرع الخوارزميات العملية؛ وقت التشغيل الخاص به هو $ \ theta (| v | ^ 3) $ من الناحية النظرية، ولكن الحلقة الداخلية سريعة جدا على الأجهزة الحقيقية معينة أنها حفنة من بت معالجة ناقلات.

for Sparse العلاقات، راجع أطروحة Esko Nuutila ، والذي يحتوي على مسح جيد جدا وكذلك بعض الخوارزميات الأخيرة.