سرفصل‌های این مبحث

گراف

تعریف گراف ساده

آخرین ویرایش: 09 اسفند 1402

دسته‌بندی: گراف

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

تعریف

گراف ساده $G$ را با زوج مرتب $G = (V, E)$ نمایش می‌دهند و عبارت است از:

$V = \{v_{1}, v_{2}, ..., v_{p}\}$

مجموعه فوق مجموعه‌ای ناتهی و متناهی است که عناصر آن را گره یا رأس می‌نامیم و مجموعه راس‌های گراف $G$ را با $V (G)$ نمایش می‌دهند.

$E = \{e_{1}, e_{2}, ..., e_{q}\}$

مجموعه فوق زیرمجموعه‌های دوعضوی $V$ است که آنها را یال‌های $G$ می‌نامیم و مجموعه یال‌های گراف $G$ را با $E (G)$ نمایش می‌دهند.

در این‌صورت برای هر راس $v_{i}$ و $v_{j}$ که $(i \neq j)$ توسط یال $e_{k}$ به‌هم متصل شده باشند، داریم:

$e_{k} = \{v_{i} v_{j}\} = v_{i} v_{j}; (i \neq j)$

نکته

از تعریف گراف ساده درمی‌یابیم:

1- مجموعه یال‌ها یعنی $E (G)$ می‌تواند تهی باشد یعنی هیچ یالی به راس‌ها وجود نداشته باشد.

2- مجموعه راس یعنی $V (G)$ نمی‌تواند تهی باشد.

3- دو مجموعه $V$ و $E$ از هم جدا هستند.

4- مجموعه یال‌ها یعنی $E (G)$ شامل زیرمجموعه‌های دو عضوی از عناصر متمایز مجموعه راس $V (G)$ می‌باشد.

5- در یک گراف ساده هر دو راس حداکثر با یک یال به یک‌دیگر متصل می‌گردند. اتصال یا پیوند، یالی است که دو انتهایش از هم مجزا است.

6- راس منفرد راسی است که با هیچ راسی مجاور نباشد.

دو راس مجاور یا دو راس همسایه

دو راس $v_{i}$ و $v_{j}$ از یک گراف که به‌وسیله یک یال $v_{i} v_{j}$ به‌هم متصل شده باشد را دو راس مجاور (یا همسایه) می‌گویند.

به‌عنوان نمونه، گراف زیر در نظر بگیرید:

گراف ساده - پیمان گردلو

راس $v_{1}$ با رئوس $v_{2}$ و $v_{5}$ همسایه است.

راس $v_{2}$ با رئوس $v_{1}$ و $v_{3}$ و $v_{4}$ همسایه است.

همسایگی باز راس $v$

به مجموعه راس‌هایی از گراف $G$ که به راس $v$ متصل هستند، همسایگی باز راس $v$ می‌گوییم و با $N_{G} (v)$ نمایش می‌دهیم.

همسایگی بسته راس $v$

اضافه کردنِ خودِ راسِ $v$ به $N_{G} (v)$ را همسایگی بسته راس $v$ می‌گوییم و با $N_{G} [v]$ نمایش می‌دهیم.

تمرین

شکل زیر را در نظر بگیرید:

گراف ساده - پیمان گردلو

همسایگی باز راس‌های $a, c, f$ را نمایش دهید.

$\begin{array}{l} N_{G} (a) = \{b\} \\ N_{G} (c) = \{b, d, g\} \\ N_{G} (f) = \emptyset \end{array}$

همسایگی بسته راس‌های $a, c, f$ را نمایش دهید.

$\begin{array}{l} N_{G} [a] = \{a, b\} \\ N_{G} [c] = \{c, b, d, g\} \\ N_{G} [f] = \{f\} \end{array}$

دو یال مجاور

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

به‌عنوان نمونه، گراف زیر در نظر بگیرید:

گراف ساده - پیمان گردلو

یال‌های $b c$ و $c d$ مجاورند.

نمودار گراف ساده

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

این نمایش تصویری بسیاری از خواص و ویژگی‌های گراف‌ها را به‌طور مشهودی به ما معرفی می‌کند.

برای نمایش نمودار یک گراف ساده، عضوهای مجموعه راس $V (G)$ (راس‌های گراف) را با نقاطی متمایز در صفحه مشخص می‌کنیم .

سپس از آن به‌ازای هر یال موجود در مجموعه یالی دو سر یال را با قطعه خط یا منحنی به‌هم وصل می‌نماییم.

ضمنا چگونگی رسم یال‌ها فعلا چندان اهمیتی ندارد چرا که هیچ راه منحصر به‌فردی برای رسم نمودار یک گراف موجود نمی‌باشد.

به‌عبارت دیگر برای رسم نمودار یک گراف، روش یکتایی مد نظر نیست و آن‌چه مهم است این است که باید مشخص باشد که گراف مورد نظر چند راس و چند یال دارد و کدام یال به‌کدام رئوس متصل است.

شکل‌های زیر هر دو یک گراف را نمایش می‌دهند:

گراف ساده - پیمان گردلو

تذکر

1- در نظر گرفتن بیش از یک یال بین دو راس مجاز نیست، یعنی یال‌های چندگانه نداریم.

2- در یک گراف ساده، طوقه $(L o o p)$ وجود ندارد.

طوقه یالی است که ابتدا و انتهای آن یک راس است مانند راس $a$ در گراف زیر:

3- در زمان رسم نمودار یک گراف توجه کنید که هیچ یالی خودش را قطع نکند و هیچ یالی نباید از روی راسی که مربوط به دو سر آن یال نیست، عبور نماید.

تمرین

گراف های زیر را در نظر بگیرید:

كدام‌يک از شكل های فوق مشخص كننده يک گراف ساده است؟

گرافی مشخص كننده يک گراف ساده است كه:

اولا) طوقه نداشته باشد.

ثانيا) بين هر دو راس آن حداكثر يک يال داشته باشيم.

شکل $(2)$ گراف ساده است.

تمرین

گراف های زیر را در نظر بگیرید:

كدام شکل می‌تواند معرف گراف با مشخصات زير باشد.

$\begin{array}{l} G = (V, E) \\ V = \{a, b, c, d\} \\ E = \{a c, a d, b d\} \end{array}$

شکل $(2)$ گراف ساده است.

تمرین

اگر داشته باشیم:

$\begin{array}{l} V = \{a, b, c, d\} \\ E = \{a b, a c, b d, b c\} \end{array}$

آن‌گاه نمودار گراف $G = (V, E)$ را رسم كنيد.

تمرین

شش تيم فوتبال f,e,d,c,b,a با يک‌ديگر مسابقه می‌دهند، بازی های زير انجام شده است:

a با c,d,f بازی كرده است.

d با a,e,f بازی كرده است.

b با c,e,f بازی كرده است.

e با b,d,f بازی كرده است.

c با a,b بازی كرده است.

f با a,b,d,e بازی كرده است.

گراف مربوط به اين مسابقه را رسم كنيد.

$\begin{array}{l} G = (V, E) \end{array}$

$\begin{array}{l} V = \{a, b, c, d, e, f\} \end{array}$

$E = \{a c, a d, a f, b c, b e, b f, d e, d f, e f\}$

تمرین

فرض كنيد:

$\begin{array}{l} V = \{a, b, c, d, e\} \\ E = \{a b, a d, a e, b c, b d, c e, d e\} \end{array}$

اگر داشته باشیم:

نمودار گراف $G = (V, E)$ كدام یک از شکل های فوق است؟

تمرین

يک مثال در (زندگی واقعی) از يک گراف G ارائه دهيد كه هم به راس و هم به يال های آن داده هايی نسبت داده شده باشد.

راس های گراف G را نمايش شهرها با جمعيت‌شان و يال های G را نمايش فاصله بين شهر‌ها در نظر بگيريد.

تمرین

گراف G با اطلاعات زیر را در نظر بگیرید:

$\begin{array}{l} V = \{v_{1}, v_{2}, v_{3}, v_{4}\} \\ E = \{v_{1} v_{2}, v_{1} v_{3}, v_{2} v_{3}, v_{3} v_{4}\} \end{array}$

در اين گراف راس های مجاور با راس $v_{2}$ را بيابيد.

چون $v_{1} v_{2}$ يک يال دراين گراف است، پس $v_{1}$ با $v_{2}$ مجاور است.

از طرفی $v_{2} v_{3}$ نيز یک يال دراين گراف می‌باشد، پس $v_{3}$ با $v_{2}$ مجاور است، بنابراين فقط راس های $v_{1}$ و $v_{3}$ با راس $v_{2}$ مجاورند.

تمرین

اگر داشته باشیم:

$\begin{array}{l} V = \{v_{1}, v_{2}, v_{3}, v_{4}\} \\ E = \{v_{1} v_{2}, v_{1} v_{3}, v_{3} v_{4}, v_{2} v_{4}, v_{1} v_{4}\} \end{array}$

گراف ساده $G = (V, E)$ را رسم کنید.

تمرین

نمودار گراف G در زیر رسم شده است.

مجموعه های V و E را مشخص كنيد.

$\begin{array}{l} V = \{v_{1}, v_{2}, v_{3}, v_{4}, v_{5}\} \end{array}$

$E = \{v_{1} v_{2}, v_{1} v_{3}, v_{1} v_{4}, v_{2} v_{4}, v_{2} v_{5}, v_{3} v_{4}, v_{4} v_{5}\}$

تمرین

كدام‌يک از وضعيت‌های زير بیان‌گر گراف ساده نیست؟

وضعيت ژنتيک افراد يک خانواده

گراف مربوط به این حالت يک گراف ساده است.

زيرا هيچ فردی از خودش به وجود نمی‌آيد (عدم وجود طوقه)

هيچ فردی دو بار زائيده نمی‌شود.

نقشه جاده‌های كشور

این حالت می‌تواند دارای يک گراف ساده يا چندگانه باشد.

زيرا بين دو شهر در يک كشور ممكن است بيش از يک جاده وجود داشته باشد، لذا اين امر يال چندگانه را امكان پذير می‌سازد.

دوستی ما بين يک گروه از انسان‌ها

گراف مربوط به این حالت يک گراف ساده است.

در این حالت دوست بودن یک فرد با خودش معنی ندارد. (عدم وجود طوقه)

در يک گراف، وقتی دو نفر با يک‌ديگر دوست می‌باشند را فقط با يک يال به‌هم متصل می‌كنند.

مسابقات ورزشی يک حذفی

گراف مربوط به این حالت يک گراف ساده است.

در این حالت می‌توان گفت د‌ر مسابقات ورزشی يک حذفی، هر تيم با تيم ديگر بيش از يک بار مسابقه نمی‌دهد. (يال چندگانه ندارد)

ضمنا هيچ تيمی با خودش مسابقه نمی‌دهد. ( عدم وجود طوقه)

تمرین

گراف های زیر را در نظر بگیرید:

در كدام‌يک از گراف های فوق، خاصيت زیر برقرار است؟

$a c \notin E \Rightarrow b c \notin E, a b \notin E$

تمرین

گراف های زیر را در نظر بگیرید:

در كدام يک از گراف های فوق، مجموعه راسی را می‌توان به دو مجموعه X و Y افراز كرد به‌طوری كه هر يال گراف مورد نظر، دارای يک انتها در X و يک انتها در Y باشد؟

اگر قرار دهيم:

$\begin{array}{l} X = \{b, e\} \\ Y = \{a, b, c\} \end{array}$

در اين صورت هر يال در اين گراف دارای يک انتها در X و يک انتها در Y است.

پس گراف زیر، گراف مورد نظر است:

دریافت مثال

دریافت فایل PDF

خرید پاسخ‌ها

تعریف گراف ساده

4,000تومان

برای ارسال نظر وارد سایت شوید

گراف

تعریف گراف ساده

تعریف

دو راس مجاور یا دو راس همسایه

همسایگی باز راس $v$

همسایگی بسته راس $v$

دو یال مجاور

نمودار گراف ساده

nenomatica

مجموعه قوانین

دسترسی سریع

آیا می‌خواهید فیلم معرفی را مشاهده نمایید؟

گراف

تعریف گراف ساده

تعریف

دو راس مجاور یا دو راس همسایه

همسایگی باز راسv

همسایگی بسته راسv

دو یال مجاور

نمودار گراف ساده

همسایگی باز راس $v$

همسایگی بسته راس $v$