المسافة في نظرية المخططات

في المجال الرياضي لنظرية المخططات (Graph Theory)، تُعرف المسافة بين رأسين في مخطط بأنها عدد الحواف في أقصر مسار يربط بينهما. يُطلق على هذا المفهوم أيضاً اسم المسافة الجيوديسية أو مسافة أقصر مسار. من المهم ملاحظة أنه قد يكون هناك أكثر من مسار قصير واحد بين رأسين معينين.

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

المسافة في المخططات الموجهة

في حالة المخطط الموجه (Directed Graph)، تُعرف المسافة $d(u,v)$ بين الرأسين $u$ و $v$ بأنها طول أقصر مسار موجه من $u$ إلى $v$ يتكون من أقواس، بشرط وجود مسار واحد على الأقل. وبخلاف المخططات غير الموجهة، فإن المسافة من $u$ إلى $v$ لا تتطابق بالضرورة مع المسافة من $v$ إلى $u$، مما يجعلها شبه مقياس (Quasi-metric) بدلاً من مقياس حقيقي.

رسمياً، بالنسبة للرؤوس $u$ و $v$ في مخطط موجه $G$، لا يوجد ضمان بأن $d(u,v) = d(v,u)$، وقد تكون المسافة $d(u,v)$ غير معرفة إذا لم يوجد مسار موجه من $u$ إلى $v$.

التمثيل الحسابي للمسافات

يمكن تمثيل المسافات بين العقد حسابياً باستخدام مصفوفة المسافات (Distance Matrix)، والتي تُعرف أيضاً بمصفوفة أقصر مسار لجميع الأزواج. هذه مصفوفة مربعة $D = (d_{ij})$ حيث يشير كل إدخال $d_{ij}$ إلى طول أقصر مسار بين الرأسين $v_i$ و $v_j$.

تُستخدم مصفوفات المسافات في تطبيقات متعددة، منها الاتصالات والكيمياء. في نظرية المخططات الكيميائية، تم اشتقاق العديد من المؤشرات الطوبولوجية التي تصف البنية الجزيئية من مصفوفة المسافات.

تضمينات المقياس (Metric Embeddings)

بعيداً عن التمثيلات المصفوفية الدقيقة، يمكن تمثيل مسافات المخطط باستخدام تضمينات المقياس. يقوم هذا النهج برسم رؤوس المخطط كنقاط في فضاء هندسي (مثل الفضاء الإقليدي) بطريقة تحافظ على مسافات المخطط قدر الإمكان.

مفاهيم ذات صلة

يُسمى الفضاء المتري المعرف على مجموعة من النقاط بدلالة المسافات في مخطط معرف على تلك المجموعة مقياس المخطط (Graph Metric). تشكل مجموعة الرؤوس (في مخطط غير موجه) ودالة المسافة فضاءً مترياً إذا وفقط إذا كان المخطط متصلاً.

اللامركزية (Eccentricity)

تُعرف اللامركزية $\epsilon(v)$ للرأس $v$ بأنها أكبر مسافة بين $v$ وأي رأس آخر في المخطط. يمكن التفكير فيها على أنها مدى بُعد العقدة عن أبعد عقدة عنها في المخطط.

نصف القطر والقطر

نصف قطر المخطط (Radius) هو الحد الأدنى للامركزية لأي رأس في المخطط، بينما قطر المخطط (Diameter) هو الحد الأقصى للامركزية لأي رأس.