تسمية مجموعات من القمم في الرسم البياني بطريقة فعالة دون BFS / DFS

Question

لدي رسم بياني مع مجموعة من القمم $ \ mathcal {v} $ ومجموعة من الحواف $ \ mathcal {e} $ . يوجد مسار بين كل 2 رأس في الرسم البياني. إلى كل حافة هناك وزن مرتبط $ w (e)، e \ in \ mathcal {e} $ . أحدد عتبة (عالمية) $ T $ بحيث إذا $ W ((U، V)) / span> أفضل القمم $ u، v \ in \ mathcal {v} $ هي في نفس المجموعة: $ g \ في \ mathcal {v} \ rawrow \ mathbb {z}، g (v_1)= g (v_2) $ . هذا السلوك متعدية. الهدف هو تسمية المجموعات المميزة بدءا من الصفر (ترتيب المجموعات غير ذي صلة). أعلم أن هذا يمكن تحقيقه بشكل تافه مع BFS أو DFS، لكنني أريد تجنب استخدام تلك.

الفكرة التي توصلت إليها هي التكرار فوق القمم، وتذهب فوق حي الحلقة الخاتم، وإنشاء مجموعة جديدة في كل مرة تقوم فيها $ w ((u، v) ) لأي من الحواف وليس $ u $ ولا $ v $ تم تعيين مجموعة (على سبيل المثال $ g (u)= g (v)= -1 $ ). بالإضافة إلى ذلك، يتم تعيين كل مجموعة تسمية، والتي تساوي في البداية لمؤشر المجموعة: $ h: \ mathbb {n} \ charearrow \ mathbb {n}، h (g ( U))= g (u) $ . إذا كان ذلك في بعض النقاط $ w ((x، y)) و $ w ((y، z)) ، ولكن $ g (x) \ ne g (z) $ ثم تعيين $ h ( G (x)) \ LaStarrow \ Min (h (g (x (x))، h (g (x)) $ و $ h (g (z)) \ Leftarrow h (g (x)) $ . بعد هذا الإجراء يجب أن يحمل: $ h (g (u))= h (g (v))، u، V \ in \ in \ mathcal {v} $ إذا كان هناك طريق من $ u $ إلى $ v $ : $ \ pi= e_1، ...، e_n $ بحيث $ w (e_i) . هل الخوارزمية التي جئت معها الصحيح أو هل افتقد شيئا ما؟ كما هو الحال حاليا يتطلب $ | \ mathcal {v} | $ الذاكرة لكل صفيف $ g، h $ . هل هناك طريقة لتحسين هذا أكثر؟

Answer 1

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

Answer 2

أعتقد خوارزمي صحيحة. يتم تقديم رسم من الدليل أدناه:

هناك 2 حالات: إما $ u \ ne v \ in \ mathcal {v} $ تحتاج إلى أن تكون من نفس المجموعة، أو يجب أن تكون من مجموعات مختلفة (اعتمادا على ما إذا كان هناك مسار بينهما بينهما مثل $ W (E) ). يجب أن يظهر أن الخوارزمية تنتج المجموعات الناتجة (سيتم إجراء الدليل لكل حالة من خلال التناقض).

1. case 1: دع $ u، v \ in \ mathcal {v} $ وهناك طريق من $ u $ to $ v $ : $ \ pi= e_1، ...، e_n $ مثل $ w (e_i) . ثم $ h (g (u)) $ يجب أن يساوي $ h (g (v)) $ for الخوارزمية أن تكون صحيحة.

2. افتراض الخوارزمية غير صحيح: افترض أن هذا ليس هو الحال، وأن $ u $ ، $ V $ تنتمي إلى مجموعات مختلفة بناء على نتيجة الخوارزمية. بالنسبة للبساطة، تفترض أن $ \ pi=pi_1، x، y، z، \ pi_2؛ \، x، y، z \ in \ mathcal {v} $ مثل هذا أن جميع القمم من $ \ pi_1، x $ تنتمي إلى $ h (g (u)) $ و جميع القمم على $ y، z، \ pi_2 $ تنتمي إلى $ h (g (v)) $ بناء على الخوارزمية. سيتم إثبات القضية التالية الافتراض أعلاه، ولكن يجب أن يكون واضحا أن نفس الشيء سيحتفظ به الحث حتى لو تم تقسيم $ \ PI $ إلى المزيد من المجموعات بناء على المزيد من الفئات خوارزمية.

دليل على التناقض: من (1)، يتبع $ w (x، y) ، ومن (2) يتبع: $ h (g (x)) \nh (g (z)) $ . من تعريف الخوارزمية، يتبع ذلك أنه لا ينفصل أبدا مجموعات، ويتم دمج مجموعتين إذا $ w (x، y) ولكن $ h (g (x)) \ NE H (g (z)) $ . نظرا لأن الخوارزمية تذهب فوق جميع الحواف، فينبغي أن دمج $ h (g (x)) $ و $ h (g ( z)) $ .

3. case 2: $ u، v \ in \ mathcal {v} $ وليس هناك مسار $ \ Pi $ من $ u $ to $ v $ مثل $ w (e) ، ثم $ h (g (u))= h (g (5)) $ .

4. افتراض الخوارزمية غير صحيحة: افترض $ h (g (u))= h (g (v)) $ .

دليل على التناقض: كلاهما في إنشاء المجموعة ودمج المجموعة (الطريقتين الوحيدتين للحصول على رؤوس في نفس المجموعة) تحتاج إلى وجود مسار بين $ u $ و $ v $ مثل $ w (e) . (3) تنص على أنه لا يوجد هذا المسار، ثم $ h (g (u)) \ Ne h (g (v)) $ .

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