شاه کلید نکات
شاه کلید سوال
![[شاه کلید مای درس] | معرفی گراف](https://dl.my-dars.com/upload/image/01 (11)1728766112.jpg)
گراف از مجموعه ای از نقاط (که به هر کدام راس می گوییم) و مجموعه ای از خطوط (که به هرکدام یال می گوییم) تشکیل شده است. هر یال بین دو راس قرار دارد. در گراف G مجموعه ی راس ها را با (Vertex) V (G) و مجموعه یال ها را با (Edge) E (G) نشان می دهیم.
گراف یک روش مدل سازی برای نشان دادن رابطه بین اعضای یک مجموعه است.
مثال
1 برای گراف زیر یک مجموعه ی احاطه گر بنویسید.
\(\{ a,b,e,d\} \)
2 یک گراف 5 راسی با عدد احاطه گری 2 رسم کنید.
به گرافی که یال های آن جهت داشته باشند، گراف جهت دار می گوییم. در نمایش گراف جهت دار با استفاده از نماد های ریاضی، یال هارا با زوج مرتب نشان می دهیم.
مثال
مجموعه ی راس ها و یال های گراف زیر را بنویسید.
\(\begin{array}{l}V = \{ a,b,c,d,e\} \\E = \{ (a,b),(b,c),(d,c),(d,b),(e,d),(e,a),(a,e)\} \end{array}\)
برای رسم نمودار یک گراف روش یکتایی وجود ندارد و شکل گراف صرفا باید مشخص کند که کدام راس ها به هم متصل اند.
مثلا دو نمودار زیر هر دو یک گراف را نمایش می دهند.
بین هر دو راس گراف ممکن است بیش از یک یال موجود باشد و همچنین یک یال ممکن است یک راس را به خود آن راس وصل کند که در این صورت به آن یال طوقه می گویند.
به گرافی که طوقه نداشته باشد و بین هر دو راس آن حداکثر یک یال وجود داشته باشد، گراف ساده می گوییم. در این فصل با گراف های ساده سر و کار خواهیم داشت و هر کجا از گراف نام ببریم، منظور گراف ساده است.
به تعداد راس های گراف G، مرتبه ی گراف گفته و آن را با P نشان می دهیم. به تعداد یال های گراف G، اندازه ی گراف گفته و آن را با q نشان می دهیم.
به تعداد یال های متصل به گراف G که به راس V متصل اند، درجه ی آن راس گفته و آن را با \({\deg _G}(v)\) یا \(\deg (v)\) نشان می دهیم. اگر درجه یک راس عددی فرد باشد، به آن راس فرد و اگر درجه زوج باشد، به آن راس زوج می گوییم. در صورتی که \(\deg (v) = 0\) باشد (یعنی راس مورد نظر به راس دیگر متصل نباشد) به v راس تنها یا ایزوله می گوییم.
دو راس که توسط یالی به هم متصل شده باشند را مجاور (یا همسایه) می نامیم. مثلا در گراف زیر راس های مجاور و غیر مجاور عبارت اند از:
مجموعه های همسایه های یک راس
فرض کنیم \(v \in V(G)\)، به مجموعه راس هایی از گراف g که به راس v متصل هستند، همسایگی باز راس v می گوییم و با \({N_G}(v)\) نمایش می دهیم. اضافه کردن خود راس v به \({N_G}(v)\) همسایگی بسته ی راس v را به دست می دهد که آن را با \({N_G}[v]\) نمایش می دهیم. می توان این دو مجموعه را به صورت زیر نشان داد:
\(\begin{array}{l}{N_G}(v) = \{ u \in V(G):uv \in E(G)\} \\{N_G}[v] = {N_G}(v) \cup \{ v\} \end{array}\)
مثال
مجموعه های همسایه های یک راس گراف زیر را بنویسید.
\(\begin{array}{l}{N_G}(a) = \{ b\} \\{N_G}(c) = \{ b,d,g\} \\{N_G}(f) = \emptyset \\{N_G}[a] = \{ a,b\} \\{N_G}[c] = \{ b,c,d,g\} \\{N_G}[f] = \{ f\} \end{array}\)
در صورتی که \({N_G}[v] = \emptyset \) باشد، راس v ایزوله است.
دو یال را مجاور می نامیم هر گاه راسی وجود داشته باسد که هر دو یال به آن وصل باشند. مثلا در گراف زیر یال های \({v_1}{v_2}\) و \({v_2}{v_3}\) مجاورند. ولی یال های \({v_1}{v_2}\) و \({v_3}{v_4}\) مجاور نیستند.
بزرگ ترین درجه در بین راس های یک گراف را ماکزیمم درجه نامیده و آن را با نماد \(\Delta (G)\) نمایش می دهیم. به صورت مشابه، کوچک ترین درجه را مینیمم درجه نامیده و با نماد \(\delta (G)\) نمایش می دهیم.
برای مثال در گراف زیر \(\Delta = 3\) و \(\delta = 1\)
حواستان باشد ممکن است چند راس از درجه ماکسیمم یا مینیمم وجود داشته باشد.
همواره داریم \(\Delta \le p - 1\)
در گراف از مرتبه p، راسی که با همه رئوس دیگر مجاور باشد، را راس فول (پر) می نامیم. در واقع راس فول دارای درجه \(p - 1\) است.
اگر گرافی از مرتبه p، دارای k راس فول باشد آنگاه \(\delta \ge K\)
فرض کنید گراف G از مرتبه ی p و اندازه ی q باشد، در این صورت:
\(\sum\limits_{i - 1}^p {\deg ({v_i}) = } \deg ({v_1}) + \deg ({v_2}) + ... + \deg ({v_p}) = 2q\)
در نتیجه تعداد راس های فرد هرگراف عددی زوج است.
تمرین
1 در گراف شکل زیر
الف) مجموعه احاطه گری بنویسید که مینیمال باشد ولی مینیمم نباشد.
\(\{ a,h,c,e,f\} \)
ب) عدد احاطه گری این گراف را تعیین کنید.
\(\left[ {\frac{8}{{4 + 1}}} \right] = 2 \le \gamma (G)\) و چون \(\{ b,d\} \) یک مجموعه ی احاطه گر پس \(\gamma (G) = 2\)
2 شهری دارای 11 میدان است و هر میدان شهر از طریق خیابان ها حداکثر به 4 میدان دیگر متصل است. می خواهیم در بعضی از میدان ها نمازخانه بسازیم به طوری که هر شخصی در هر یک از میدان های شهر که باشد، یا در همانی میدانی که ایستاده به نمازخانه دسترسی داشته باشد یا در میدان مجاور آن. آیا با ساخت 2 نمازخانه می توانیم به این هدف برسیم؟ چرا؟
چون کران پایین عدد احاطه گری 3 است. پس با تعداد کمتر از 3 نمازخانه به هدف نمی رسیم و حداقل به 3 نماز خانه لازم است.
\(\gamma (G) = \left[ {\frac{{11}}{{4 + 1}}} \right] = 3\)
تهیه کننده: جابر عامری و الماسی کیا
