مقدمة
في مجال نظرية الرسوم البيانية في الرياضيات، مسار الرسم البياني (أو الرسم البياني الخطي) هو رسم بياني يمكن سرد رؤوسه بترتيب يمكن فيه ربط رأسين متجاورين في القائمة بحافة، ولا يتم توصيل الرؤوس غير المتجاورة. بعبارة أخرى، هو رسم بياني يمكن رسمه كرسم بياني حيث تقع جميع الرؤوس والحواف على طول خط مستقيم.
تعتبر الرسوم البيانية المسارية من أبسط أنواع الرسوم البيانية، وتظهر بشكل متكرر في مجموعة متنوعة من التطبيقات، بدءًا من علوم الكمبيوتر وهندسة الشبكات وصولًا إلى الكيمياء وعلم الأحياء. فهم خصائصها وسلوكها أمر ضروري لفهم أعمق للرسوم البيانية الأكثر تعقيدًا.
التعريف الرسمي
بشكل رسمي، المسار graph مع *n* من الرؤوس، غالبًا ما يُرمز إليه بـ *Pn*، هو graph يتكون من سلسلة من *n* من الرؤوس المتمايزة والحواف *n-1*. يمكن تمثيل مجموعة الرؤوس على أنها {*v1, v2, …, vn*}، ومجموعة الحواف على أنها {(*v1, v2*), (*v2, v3*), …, (*vn-1, vn*)}.
بمعنى أبسط، يمكن تخيل المسار graph كسلسلة من النقاط المرتبطة بخطوط. الرأسين الموجودين في نهايتي المسار يطلق عليهما نقاط النهاية أو الرؤوس الطرفية، بينما تسمى جميع الرؤوس الأخرى الرؤوس الداخلية.
خصائص مسار الرسم البياني
تمتلك مسارات الرسوم البيانية عددًا من الخصائص المميزة التي تجعلها سهلة التحليل والفهم:
- الترابط: مسار الرسم البياني متصل دائمًا، مما يعني أنه توجد مسار بين أي رأسين فيه.
- عدم وجود دورات: لا يحتوي مسار الرسم البياني على أي دورات. بعبارة أخرى، لا توجد طريقة للبدء من رأس ما والعودة إليه باتباع سلسلة من الحواف دون تكرار أي رؤوس أو حواف.
- الدرجة: كل رأس داخلي في مسار الرسم البياني له درجة 2 (متصل بحافتين)، بينما كل رأس طرفي له درجة 1 (متصل بحافة واحدة).
- الرسم: يمكن دائمًا رسم مسار الرسم البياني على مستوى دون عبور أي حواف. وهذا يعني أنه رسم بياني مستو.
- التلوين: يمكن تلوين مسار الرسم البياني بلونين فقط. وهذا يعني أنه رسم بياني ثنائي الأطراف.
أمثلة
لتوضيح المفهوم بشكل أفضل، إليك بعض الأمثلة:
- *P1*: رأس واحد وحيد بدون حواف.
- *P2*: رأسان متصلان بحافة واحدة.
- *P3*: ثلاثة رؤوس متصلة بحافتين على شكل خط.
- *P4*: أربعة رؤوس متصلة بثلاث حواف على شكل خط.
تخيل مجموعة من الأطفال يقفون في صف واحد ويمسكون بأيدي بعضهم البعض. هذا يشكل مسار graph. كل طفل يمثل رأسًا، وكل يد ممسكة تمثل حافة.
تمثيلات مسار الرسم البياني
هناك عدة طرق لتمثيل مسار graph، بما في ذلك:
- قائمة الحواف: ببساطة سرد جميع الحواف في الرسم البياني. على سبيل المثال، يمكن تمثيل *P4* بقائمة الحواف: {(1, 2), (2, 3), (3, 4)}.
- مصفوفة التجاور: مصفوفة مربعة حيث يمثل العنصر (i, j) ما إذا كان هناك حافة بين الرأس *i* والرأس *j*. بالنسبة لمسار الرسم البياني، ستكون مصفوفة التجاور مصفوفة ثلاثية الأقطار.
- قائمة التجاور: قائمة تربط كل رأس بقائمة جيرانه. بالنسبة لمسار الرسم البياني، سيكون لكل رأس داخلي جارين، وسيكون لكل رأس طرفي جار واحد.
تطبيقات مسار الرسم البياني
تظهر مسارات الرسوم البيانية في العديد من التطبيقات المختلفة، بما في ذلك:
- علوم الكمبيوتر: تمثيل قوائم الانتظار، وقوائم الانتظار المزدوجة، وهياكل البيانات الخطية الأخرى.
- هندسة الشبكات: تمثيل مسارات البيانات في الشبكة.
- الكيمياء: تمثيل سلاسل الكربون في الجزيئات العضوية.
- علم الأحياء: تمثيل تسلسل الحمض النووي.
- تحليل المسار الحرج: تحديد أطول مسار من الأنشطة التي يجب إكمالها في الوقت المحدد حتى يكتمل المشروع؛ يمكن نمذجة المشاريع التي تتكون من سلسلة من المهام المتسلسلة باستخدام مسار graph.
- معالجة الصور: في بعض خوارزميات معالجة الصور، يمكن استخدام مسارات الرسوم البيانية لتمثيل ميزات الصورة أو هياكلها، على سبيل المثال، في تتبع الخطوط أو تحليل الهيكل العظمي للكائنات.
مسارات الرسم البياني والدورات
على عكس الدورات (cycles)، التي هي أيضًا أنواع أساسية من الرسوم البيانية، تفتقر مسارات الرسوم البيانية إلى أي مسارات مغلقة. هذا يجعلها أبسط بكثير من حيث التحليل والخوارزميات. غالبًا ما تُستخدم مسارات الرسوم البيانية كلبنات بناء لفهم خصائص الرسوم البيانية الأكثر تعقيدًا التي قد تحتوي على دورات.
مسارات الرسم البياني الموزونة
في بعض التطبيقات، قد يكون لكل حافة في مسار الرسم البياني وزن مرتبط بها. يمثل هذا الوزن عادةً تكلفة أو مسافة أو أي مقياس آخر مرتبط بالمرور عبر تلك الحافة. يمكن استخدام مسارات الرسوم البيانية الموزونة لنمذجة مشاكل مثل إيجاد أقصر طريق بين نقطتين على طريق، أو تحديد التسلسل الأمثل للعمليات في خط تجميع.
التعرف على مسار الرسم البياني
تحديد ما إذا كان رسم بياني معين هو مسار الرسم البياني هو مشكلة بسيطة. يمكن حلها في الوقت الخطي عن طريق التحقق من الخصائص التالية:
- يجب أن يكون الرسم البياني متصلاً.
- يجب أن يحتوي الرسم البياني على رأسين على الأكثر بدرجة 1.
- يجب أن يكون لجميع الرؤوس الأخرى درجة 2.
إذا كانت هذه الشروط صحيحة، فإن الرسم البياني هو مسار الرسم البياني.
الرسوم البيانية ذات الصلة
هناك العديد من الرسوم البيانية الأخرى المرتبطة ارتباطًا وثيقًا بمسارات الرسوم البيانية، بما في ذلك:
- الدورة (Cycle Graph): يشبه مسار الرسم البياني ولكنه يحتوي على حافة إضافية تربط الرأس الأول بالرأس الأخير، مما يخلق دورة مغلقة.
- الرسم البياني الكامل (Complete Graph): حيث يرتبط كل رأس بجميع الرؤوس الأخرى.
- الرسم البياني الشجري (Tree Graph): رسم بياني متصل بدون دورات، ولكن قد يكون له بنية متفرعة أكثر تعقيدًا من مسار الرسم البياني.
خاتمة
مسار الرسم البياني هو مفهوم أساسي في نظرية الرسوم البيانية، ويتميز ببنيته البسيطة وخصائصه سهلة الفهم. يلعب دورًا مهمًا في مجموعة متنوعة من التطبيقات في علوم الكمبيوتر والهندسة والعلوم الأخرى. فهم مسارات الرسوم البيانية هو خطوة أولى حاسمة نحو فهم الرسوم البيانية الأكثر تعقيدًا والخوارزميات التي تعمل عليها.