المسار (نظرية الرسم البياني)
في نظرية المخططات ، المسار في المخطط هو سلسلة منتهية أو غير منتهية من الحواف التي تربط سلسلة من الرؤوس ، والتي تكون جميعها، وفقًا لمعظم التعريفات، متميزة (وبما أن الرؤوس متميزة، فإن الحواف كذلك). أما المسار الموجه (ويُسمى أحيانًا المسار الثنائي [ 1 ] ) في المخطط الموجه فهو سلسلة منتهية أو غير منتهية من الحواف التي تربط سلسلة من الرؤوس المتميزة، مع شرط إضافي هو أن تكون جميع الحواف موجهة في نفس الاتجاه.
تُعدّ المسارات مفاهيم أساسية في نظرية الرسوم البيانية، وقد وُصفت في الأقسام التمهيدية لمعظم كتب نظرية الرسوم البيانية. انظر على سبيل المثال: بوندي ومورتي (1976) ، وجيبونز (1985) ، وديستل (2005) . ويتناول كورت وآخرون (1990) مواضيع خوارزمية أكثر تقدماً تتعلق بالمسارات في الرسوم البيانية.
التعريفات
المشي، والمسار، والممر
- ليكن G = ( V , E , Φ ) مخططًا بيانيًا. المسار المحدود هو سلسلة من الحواف ( e1 , e2 , ... , en - 1 ) التي يوجد لها سلسلة من الرؤوس ( v1 , v2 , ..., vn ) بحيث يكون Φ ( ei ) = { vi , vi +1 } ، حيث i = 1 , 2, ..., n-1. (v1, v2, ..., vn ) هي سلسلة رؤوس المسار . يكون المسار مغلقًا إذا كان v1 = vn ، ومفتوحًا فيما عدا ذلك . المسار غير المحدود هو سلسلة من الحواف من نفس النوع الموصوف هنا ، ولكن بدون رأس أول أو أخير، أما المسار شبه المحدود (أو الشعاع ) فله رأس أول ولكن ليس له رأس أخير.
- المسار هو طريق تكون فيه جميع الحواف واضحة. [ 2 ]
- المسار هو درب تكون فيه جميع الرؤوس (وبالتالي جميع الحواف) متميزة. [ 2 ]
إذا كانت w = ( e1 , e2 , ... , en - 1 ) مسارًا محدودًا بتسلسل رؤوس (v1 , v2 , ... , vn ) ، فإن w يُقال إنه مسار من v1 إلى vn . وينطبق الأمر نفسه على المسار أو الطريق . فإذا وُجد مسار محدود بين رأسين مختلفين ، فإنه يوجد أيضًا مسار محدود بينهما.
لا يشترط بعض المؤلفين أن تكون جميع رؤوس المسار متميزة، ويستخدمون بدلاً من ذلك مصطلح المسار البسيط للإشارة إلى مثل هذا المسار حيث تكون جميع الرؤوس متميزة.
يربط الرسم البياني الموزون قيمة ( وزن ) بكل حافة فيه. وزن المسار (أو الطريق) في الرسم البياني الموزون هو مجموع أوزان الحواف التي تم اجتيازها. أحيانًا تُستخدم كلمتا " التكلفة " أو "الطول" بدلًا من "الوزن".
المشي الموجه، والمسار الموجه، والطريق الموجه
- المسار الموجه هو سلسلة محدودة أو غير محدودة من الحواف الموجهة في نفس الاتجاه والتي تربط سلسلة من الرؤوس . [ 2 ]
- ليكن G = ( V , E , Φ ) مخططًا موجهًا. المسار الموجه المحدود هو سلسلة من الحواف ( e1 , e2 , ..., en - 1 ) التي يوجد لها سلسلة من الرؤوس ( v1 , v2 , ..., vn ) بحيث يكون Φ ( ei ) = ( vi , vi +1 ) لـ i = 1 , 2, ..., n-1. (v1, v2, ..., vn ) هي سلسلة رؤوس المسار الموجه . يكون المسار الموجه مغلقًا إذا كان v1 = vn ، ومفتوحًا فيما عدا ذلك . المسار الموجه غير المحدود هو سلسلة من الحواف من نفس النوع الموصوف هنا ، ولكن بدون رأس أول أو أخير، والمسار الموجه شبه المحدود (أو الشعاع ) له رأس أول ولكن ليس له رأس أخير.
- المسار الموجه هو مسار موجه تكون فيه جميع الحواف متميزة. [ 2 ]
- المسار الموجه هو مسار موجه تكون فيه جميع الرؤوس متميزة. [ 2 ]
إذا كانت w = ( e1 , e2 , ..., en - 1 ) مسارًا موجهًا محدودًا بتسلسل رؤوس ( v1 , v2 , ..., vn ) ، فإن w يُقال إنه مسار من v1 إلى vn . وينطبق الأمر نفسه على المسار الموجه. فإذا وُجد مسار موجه محدود بين رأسين مختلفين ، فإنه يوجد أيضًا مسار موجه محدود بينهما.
المسار الموجه البسيط هو مسار تكون فيه جميع الرؤوس متميزة.
يربط الرسم البياني الموجه الموزون قيمة ( وزن ) بكل حافة فيه. وزن المسار الموجه (أو الطريق) في الرسم البياني الموجه الموزون هو مجموع أوزان الحواف التي تم اجتيازها. أحيانًا تُستخدم كلمتا "التكلفة " أو "الطول" بدلًا من "الوزن".
أمثلة
- تكون الرسمة متصلة إذا كانت هناك مسارات تحتوي على كل زوج من الرؤوس.
- يكون الرسم البياني الموجه متصلاً بقوة إذا كانت هناك مسارات موجهة ذات اتجاهات متعاكسة تحتوي على كل زوج من الرؤوس.
- يُطلق على المسار الذي لا تربط فيه حواف الرسم البياني رأسين غير متتاليين من رؤوس المسار اسم المسار المستحث .
- المسار الذي يشمل كل رأس من رؤوس الرسم البياني دون تكرار يُعرف باسم مسار هاميلتوني .
- يكون المساران مستقلين عن الرؤوس ( أو منفصلين داخليًا ) إذا لم يشتركا في أي رأس أو ضلع داخلي. وبالمثل، يكون المساران مستقلين عن الأضلاع (أو منفصلين عن الأضلاع ) إذا لم يشتركا في أي ضلع. المساران المنفصلان داخليًا هما منفصلان عن الأضلاع، ولكن العكس ليس صحيحًا بالضرورة.
- المسافة بين رأسين في الرسم البياني هي طول أقصر مسار بينهما، إن وجد، وإلا فإن المسافة تكون لا نهائية .
- قطر الرسم البياني المتصل هو أكبر مسافة (محددة أعلاه) بين أزواج رؤوس الرسم البياني.
إيجاد المسارات
توجد العديد من الخوارزميات لإيجاد أقصر وأطول المسارات في الرسوم البيانية، مع التمييز المهم بأن المشكلة الأولى أسهل حسابيًا بكثير من المشكلة الثانية.
تُنتج خوارزمية ديكسترا قائمة بأقصر المسارات من رأس المصدر إلى كل رأس آخر في الرسوم البيانية الموجهة وغير الموجهة ذات أوزان الحواف غير السالبة (أو بدون أوزان حواف)، بينما يمكن تطبيق خوارزمية بيلمان-فورد على الرسوم البيانية الموجهة ذات أوزان الحواف السالبة. ويمكن استخدام خوارزمية فلويد-وارشال لإيجاد أقصر المسارات بين جميع أزواج الرؤوس في الرسوم البيانية الموجهة الموزونة.
مشكلة تقسيم المسار
مشكلة تقسيم المسار k هي مشكلة تقسيم الرسم البياني المعطى إلى أصغر مجموعة من المسارات المنفصلة عن الرؤوس بطول لا يتجاوز k . [ 3 ]
انظر أيضاً
ملحوظات
- ↑ McCuaig 1992 ، ص 205.
- 1 2 3 4 5 6 Bender & Williamson 2010 ، ص. 162.
- ↑ تشين، يونغ؛ غوبل، راندي؛ لين، غوهوي؛ سو، بينغ؛ شو، ياو؛ تشانغ، آن (2019-07-01). "خوارزمية تقريب محسّنة لمسألة تقسيم المسار الثلاثي الأدنى" . مجلة التحسين التوافقي . 38 (1): 150-164 . doi : 10.1007/s10878-018-00372-z . ISSN 1382-6905 .
مراجع
- بيندر، إدوارد أ.؛ ويليامسون، إس. جيل (2010). القوائم والقرارات والرسوم البيانية. مع مقدمة في الاحتمالات .
- بوندي، جيه إيه؛ مورتي، يو إس آر (1976). نظرية الرسوم البيانية مع تطبيقاتها . نورث هولاند. ص 12-21 . ISBN 0-444-19451-7.
- ديستل، راينهارد (2005). نظرية الرسم البياني . سبرينغر-فيرلاغ. ص 6 – 9. ISBN 3-540-26182-6.
- جيبونز، أ. (1985). نظرية الرسم البياني الخوارزمية . مطبعة جامعة كامبريدج. ص 5-6 . ISBN 0-521-28881-9.
- الأماكن القريبة : الأماكن القريبة : بروميل، هانز يورغن؛ شريفر، ألكسندر (1990). المسارات والتدفقات وتخطيط VLSI . سبرينغر-فيرلاغ. رقم ISBN 0-387-52685-4.
- مكويغ، ويليام (1992). "الرسوم البيانية الموجهة بين الدورات" . في: روبرتسون، نيل ؛ سيمور، بول (محرران). نظرية بنية الرسوم البيانية . المؤتمر الصيفي المشترك للبحوث حول الرسوم البيانية الصغرى، الجمعية الأمريكية للرياضيات - معهد الرياضيات التطبيقية - جمعية الرياضيات الصناعية والتطبيقية، سياتل، 22 يونيو - 5 يوليو 1991. الجمعية الأمريكية للرياضيات. ص 205.
- كائنات نظرية الرسم البياني
- اتصال الرسم البياني