گراف

گراف: [اصطلاح شبکه ریلی] نمودار حرکت مکانی قطار وسایر ( وسائط نقلیه ریلی ) در بعد زمان را گراف می گویند که در آن زمان و مکان حرکت ، توقف ، تلاقی ، سبقت ، مشخصات وسایط نقلیه ریلی و تمام عملیات سیر و حرکتی محور حرکت با درج کد مربوطه ثبت و ترسیم می گردد.

گراف ساده: یک گراف از مجموعه ای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با {\displaystyle V}V نشان می دهیم، و مجموعه ای شامل یال ها، که رأس ها را به هم وصل می کنند و با {\displaystyle E}E نمایش می دهیم. یک چنین گرافی را با {\displaystyle G= ( V, E ) }G= ( V, E ) نشان می دهیم. اگر یال {\displaystyle y}y دو رأس {\displaystyle v_{1}}v_{1} و {\displaystyle v_{2}}v_{2} را به هم وصل کند می نویسیم {\displaystyle y=\lbrace v_{1}, v_{2}\rbrace }y=\lbrace v_{1}, v_{2}\rbrace . [۳]

گراف جهت دار: منظور از گراف جهت دار گرافی است که یال ها در آن دارای جهت هستند. گراف جهت دار G زوج مرتب ( V, E ) است که V مجموعه ای ناتهی و اعضای E زوجهای مرتب از اعضای V هستند. همانند گرافهای ساده، به اعضایV، راسهای G و به اعضای E، یال های G می گوییم. همچنین به هر گراف جهت دار نموداری در صفحه نسبت می دهیم. به این صورت که به ازای هر راس G نقطه ای در صفحه در نظر می گیریم و به ازای هر یال مانند ( u, v ) کمانی بین u و v رسم می کنیم و روی این کمان فلشی از u به v می گذاریم.

گراف مخلوط: گرافی است که در آن ممکن است برخی یال ها جهت داشته باشند و برخی بدون جهت باشند. گراف مخلوط G، سه تایی مرتب G = ( V, E, A ) است که در آن V مجموعه ی رئوس، E یال های بدون جهت و A یال های جهت دارمی باشند. گراف ساده و گراف جهت دار حالت خاصی از گراف جهت دار می باشند.

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

قرارداد ها:

مرتبه و اندازۀ یک گراف: تعداد رأس های گراف G یعنی |V ( G ) | را مرتبهٔ آن گراف می گوییم و باp ( G ) نمایش می دهیم و تعداد یال های گراف یعنی |E ( G ) | را اندازهٔ گراف G می گوییم و با q ( G ) نمایش می دهیم. معمولاً برای راحتی کار به جای p ( G ) از p و به جای q ( G ) از q استفاده می کنیم.

درجۀ یک رأس: درجهٔ رأس v در گراف G برابر است با تعداد یال هایی از گراف G که به رأس v متصل اند و آن را با degG ( v ) یا به طور ساده تر با deg ( v ) یا d ( v ) نمایش می دهیم. اگر درجهٔ یک رأس فرد باشد آن را رأس فرد و اگر زوج باشد آن را رأس زوج می نامیم.

گراف K ـ منتظم: گرافی را که درجهٔ تمام رئوس آن با هم مساوی و برابر با عدد k باشند ، گراف k - منتظم می نامیم.

رأس تنها: به رأسی که درجهٔ آن صفر باشد؛ یعنی هیچ یالی به آن متصل نباشد، رأس تنها ( یا ایزوله ) می گوییم. [۴]

گراف تهی: گرافی را که تمام رئوس آن رأس تنها باشند، یعنی هیچ یالی نداشته باشد ، گراف تهی می نامیم. بنابراین منظور از گراف تهیِ n رأسی، گرافی شامل n رأسِ تنها و بدون یال است.

دو رأس مجاور ( همسایه ) : دو رأس u و v را دو رأسِ همسایه یا مجاور گوییم هرگاه توسط یالی به هم وصل شده باشند، یعنیuv ∈ E ( G ) .

مجموعهٔ همسایه های یک رأس: فرض کنیم v ∈ V ( G ) ، به مجموعهٔ رأس هایی از گراف G که به رأس v متصل هستند، "همسایگی باز رأسv " می گوییم و با NG ( v ) نمایش می دهیم. اضافه کردنِ خودِ رأسِ v به NG ( v ) "همسایگی بستهٔ رأسv " را به دست می دهد که آن را با NG[v] نمایش می دهیم. می توان این دو مجموعه را به صورت زیر نمایش داد: NG ( v ) = {u ∈ V ( G ) ∶ uv ∈ E ( G ) } NG[v] =NG ( v ) ∪{v}

دو یال مجاور: دو یال را مجاور گوییم هرگاه رأسی وجود داشته باشد که هر دوی آنها به آن متصل باشند.

بزرگ ترین و کوچک ترین درجۀ یک گراف: بزرگ ترین عدد در بین درجات رئوس گراف G را با∆ ( G ) و کوچک ترینِ آنها را با δ ( G ) نمایش می دهیم و به ترتیب آنها را ماکزیمم و مینیمم درجهٔ گراف می نامیم.

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

مکمل یک گراف: مکمل گرافی مانند G که آن را با G^c یا G ̅ نمایش می دهیم گرافی است که مجموعهٔ رئوس آن همان مجموعهٔ رئوس گراف G است و بین دو رأس از G^cیک یال است اگر و تنها اگر بین همان دو رأس درG یالی وجود نداشته باشد.

گراف کامل: گرافی را که هر رأس آن با تمام رئوسِ دیگرِ، مجاور باشد گراف کامل می نامیم. گراف کاملِ n رأسی را با Kn نمایش می دهیم. می توان گفت Kn یک گراف n رأسی وn - 1 ــ منتظم است.

مسیر: اگر u و v دو رأس از گراف G باشند، یک مسیر از u به v ( یک v ــ u مسیر ) در G دنباله ای از رئوس دوبه دو متمایز در G است که از u شروع و به v ختم می شود به طوری که هر دو رأس متوالی این دنباله در G مجاور هم باشند. طول یک مسیر برابر است با تعداد یال های موجود در آن مسیر ( یکی کمتر از تعداد رئوس موجود در آن مسیر ) . قرارداد می کنیم که دنبالهٔ متشکل از تنها یک رأسِv، یک مسیر است با طول صفر از رأس v به خودش. ( گرافی را که تنها از یک مسیرِ n رأسی تشکیل شده باشد با Pn نمایش می دهیم ) .

دور: دنبالهٔ ( n ≥ 3 ) v1 v2 v3 . . . vn v1 از رئوس دو به دو متمایز که در آن هر رأس با رأس بعدی مجاور است را یک دور به طول n می نامیم. ( گرافی را که تنها از یک دورِ n رأسی تشکیل شده باشد را با Cn نمایش می دهیم )

همبندی و ناهمبندی یک گراف: گراف G را همبند می نامیم هرگاه بین هر دو رأسِ آن حداقل یک مسیر وجود داشته باشد، در غیر این صورت آن را ناهمبند می نامیم. [۵]

نمودار