فضای متریک روی گراف (Metric Space over a Graph)، در ریاضیات (Mathematics)

انواع فضاهای متریک (Metric Space) را در آموزش زیر شرح دادیم :

فضای متریک روی گراف (Metric Space over a Graph) :

تعریف: یک فضای متریک روی گراف، مجموعه رئوس یک گراف همراه با متریک طبیعی ناشی از گراف است. در این فضا، فاصله بین دو رأس برابر با طول کوتاه ترین مسیر بین آنها در گراف است.

\[ d_G(u, v) = \text{length of shortest path between } u \text{ and } v \]

اگر مسیری وجود نداشته باشد، معمولا

\[ d_G(u, v) = \infty \]

تعریف می شود.

توضیح مفهومی: گراف ها ساختارهای گسسته ای هستند که روابط بین اشیا را نشان می دهند. با تعریف فاصله بر اساس کوتاه ترین مسیر، می توانیم مفاهیم هندسی و تحلیلی را روی گراف ها پیاده سازی کنیم. این فاصله، که به فاصله گرافی یا فاصله کوتاه ترین مسیر معروف است، یک متریک است اگر گراف همبند باشد (یعنی بین هر دو رأس مسیری وجود داشته باشد).

ویژگی ها: فاصله گرافی همواره نامنفی، متقارن، و در گراف های همبند، نامساوی مثلث را برآورده می کند. اگر گراف وزن دار باشد، فاصله بر اساس مجموع وزن یال ها محاسبه می شود.

متریک گراف های خاص:

درخت: در درخت ها، بین هر دو رأس دقیقا یک مسیر وجود دارد، بنابراین فاصله به سادگی قابل محاسبه است.

گراف کامل: در گراف کامل با وزن واحد، فاصله بین هر دو رأس متمایز برابر ۱ است (متریک گسسته).

گراف دوری: در یک گراف دوری

\[ C_n \]

، فاصله بین دو رأس مینیمم طول دو مسیر ممکن در طول دور است.

کاربردها: فضاهای متریک روی گراف کاربردهای فراوانی دارند:

شبکه های اجتماعی: فاصله بین افراد در شبکه های اجتماعی (تعداد واسطه ها)

شبکه های حمل و نقل: کوتاه ترین مسیر بین دو شهر در شبکه جاده ای

شیمی: فاصله بین اتم ها در یک مولکول (گراف مولکولی)

علوم کامپیوتر: الگوریتم های مسیریابی (مانند الگوریتم دیکسترا)

بیوانفورماتیک: مقایسه توالی ها با استفاده از گراف های هم جواری

توسعه ها: مفاهیم پیشرفته تری مانند متریک گراف های تصادفی، گراف های متریک (گراف هایی که خود از یک فضای متریک مشتق شده اند)، و هم مورفیسم های لیپشیتز بین گراف ها وجود دارند.

📌 مثال ساده:

یک گراف خطی با ۵ رأس به ترتیب

\[ v_1 - v_2 - v_3 - v_4 - v_5 \]

را در نظر بگیرید. فاصله

\[ d(v_1, v_3) = 2 \]

(از طریق

\[ v_2 \]

)،

\[ d(v_2, v_5) = 3 \]

(از طریق

\[ v_3, v_4 \]

)، و

\[ d(v_i, v_i) = 0 \]

.