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

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

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

تعریف: یک گراف (همبند)

\[ G = (V, E) \]

با مجموعه رئوس

\[ V \]

و مجموعه یال های

\[ E \]

را در نظر بگیرید. روی مجموعه رئوس می توان یک متریک به نام متریک گرافی یا متریک کوتاه ترین مسیر (shortest path metric) تعریف کرد:

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

معمولا هر یال طول ۱ دارد، مگر اینکه وزن دار باشد. این متریک،

\[ V \]

را به یک فضای متریک تبدیل می کند.

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

ویژگی های اصلی:

متریک گرافی یک فضای متریک گسسته (با مقادیر صحیح) ایجاد می کند.

این فضا کاملا ناهمبند است (چون مقادیر فاصله گسسته اند).

اگر گراف وزن دار باشد، مقادیر فاصله می توانند حقیقی باشند.

ژئودزیک ها در این فضا متناظر با کوتاه ترین مسیرها هستند.

قطر گراف برابر با

\[ \max_{u,v} d_G(u, v) \]

است.

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

متریک مقاومتی (Resistance metric): بر اساس قانون اهم و مقاومت الکتریکی بین دو گره.

متریک انتشار (Diffusion metric): بر اساس فرایند انتشار روی گراف.

متریک موثریت (Effective metric): برای گراف های جهت دار.

متریک هذلولوی گروماف: برخی گراف ها (مانند درخت ها) هذلولوی هستند.

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

درخت ها: درخت ها گراف های بدون دور هستند. متریک روی درخت خواص خاصی دارد (مثلا بین هر دو رأس یک مسیر یکتا وجود دارد).

📌 مثال ساده:

یک خط با ۵ رأس:

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

.

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

،

\[ d(v_1, v_5) = 4 \]

.

یک مربع با رئوس

\[ a, b, c, d \]

و یال های

\[ ab, bc, cd, da \]

.

\[ d(a, c) = 2 \]

(از طریق

\[ b \]

یا

\[ d \]

).