ریاضی , علوم پایه 2634 بازدید

در ادامه مجموعه آموزش‌های ریاضیات مجله فرادرس، به مبحث گراف خواهیم پرداخت. در این آموزش، ابتدا، تاریخچه‌ای از پیدایش مفهوم گراف، سپس کاربردهای آن و در ادامه، تعاریف مربوط به گراف را بیان خواهیم کرد. معرفی انواع گراف‌ها نیز آخرین بحثی است که به آن خواهیم پرداخت. در پایان نیز، معادل انگلیسی برخی واژه‌ها را آورده‌ایم.

تاریخچه

شاید بتوان نقطه آغاز پیدایش نظریه گراف را در قرن هجدهم میلادی و مسئله پل‌های کونیگسبرگ یافت. مسئله «پل‌های کونیگسبرگ»، به هفت پل شهر کونیگسبرگ برمی‌گردد که امروزه از نظر جغرافیایی در کالینینگراد روسیه واقع شده است.

هفت پل کونیگسبرگ

این هفت پل، برای ارتباط بین خشکی‌های دو طرف رودخانه‌ای به‌نام پرگِل احداث شده بود. اما مسئله‌ای که به این پل‌ها ارتباط داشت این بود: «آیا می‌توان از نقطه‌ای شروع به قدم زدن کرد و همه پل‌ها را پیمود؟» در سال ۱۷۳۶، اویلر نشان داد که این کار غیرممکن است. اویلر، ابتدا نقاطی را متناظر با هر یک از قسمت‌های خشکی، مشخص، سپس آن‌ها را با خطوطی که نماینده پل‌ها بود، به یک‌دیگر متصل کرد.

مسئله پل‌ها

اگر به چینش پل‌ها در شکل بالا نگاه کنیم، می‌بینیم که باید ۴ نقطه و ۷ خط داشته باشیم. در حقیقت، اویلر چیزی شبیه شکل زیر را به‌دست آورد که به‌عنوان یک گراف شناخته می‌شود.

گراف پل‌ها

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

در ادامه، چند مورد از کاربردهای گوناگون گراف را به‌طور خلاصه بیان می‌کنیم.

کاربردهای نظریه گراف

نظریه گراف کاربردهای زیادی در علوم مختلف و رشته‌های مهندسی دارد که برخی از آن‌ها به‌شرح زیر است:

  • مهندسی برق: گراف در مهندسی برق برای نمایش اتصال مدارها به کار می‌رود. برخی از این اتصالات به عنوان ستاره، مثلث، سری و موازی شناخته می‌شوند.
  • علوم کامپیوتر: یکی از کاربردهای گراف در علوم کامپیوتر، مطالعه الگوریتم‌ها است. همچنین، برای بیان رابطه بین کامپیوترها در شبکه، از گراف‌ها استفاده می‌شود.
  • علوم: ساختار مولکولی و شیمیایی ماده، ساختار DNA و… از مواردی هستند که برای نمایش آن‌ها از گراف‌ها استفاده می‌شود.
  • زبان‌شناسی: گراف‌ها، برای نمایش نمودار درختی تجزیه و دستور زبان نیز به‌کار می‌روند.
  • عمومی:‌ نمایش مسیرهای بین شهرها نیز یکی از کاربردهای عمومی نظریه گراف است.

گراف چیست؟

یک گراف، نمایشی تصویری از مجموعه اشیائی است که با هم ارتباط دارند. هر یک از این اشیا را «رأس» یا گره می‌نامند. رأس‌ها نیز از طریق «یال‌»ها یا لبه‌ها با هم مرتبط هستند. تا این‌جا، چیزی که به ذهنمان می‌آید، تعدادی نقطه است که با خطوطی به یک‌دیگر متصل شده‌اند.

اگر بخواهیم کمی رسمی‌تر بنویسیم، یک گراف را با (V,E) تعریف می‌کنیم که در آن، V مجموعه رأس‌ها و E مجموعه یال‌ها است. شکل زیر، یک گراف را نشان می‌دهد. احتمالاً این شکل، تا حدودی شبیه همان چیزی است که تصور کرده‌اید.

مثالی از یک گراف

در شکل بالا، V و E به‌صورت زیر هستند:

{V = {a, b, c, d, e

{E = {ab, ac, bd, cd, de

تعاریف و اصطلاحات

همان‌طور که گفتیم، یک گراف، نموداری از نقاط، و خطوطی است که آن‌ها را به یک‌دیگر متصل کرده است. مفهوم گراف‌‌‌ها در نظریه گراف، براساس اصطلاحاتی مانند نقطه، خط، رأس، یال، مرتبه رئوس، ویژگی‌های گراف و… بنا شده است. در ادامه، برخی از این اصطلاحات را توضیح می‌دهیم.

نقطه

نقطه، یک موقعیت خاص در فضای یک‌بعدی، دوبعدی یا سه‌بعدی است. برای درک بهتر، یک نقطه را می‌توان با یک نقطه (همان چیزی که در مکالمات روزمره به کار می‌بریم) توپر نمایش داد و یکی از حروف الفبا را با آن متناظر کرد. برای مثال، نقطه زیر با نام «a» مشخص شده است.

نقطه

خط

یک خط، ارتباط بین دو نقطه است. خط را با یک خط ممتد نشان می‌دهند. در شکل زیر، «a» و «b» نقطه‌ها هستند. ارتباط بین این دو نقطه یک خط نامیده می‌شود.

خط

رأس

یک رأس، نقطه‌ای است که در آن، چند خط به هم می‌رسند. رأس، گره نیز نامیده می‌شود. مشابه نقاط، رأس را نیز می‌توان با یکی از حروف الفبا نام‌گذاری کرد.

رأس

یال

یال، اصطلاحی ریاضی است که برای خطی به‌کار می‌رود که دو رأس را به یک‌دیگر وصل می‌کند. از یک رأس ممکن است تعداد زیادی یال شکل بگیرد. بدون وجود رأس، یالی هم وجود نخواهد داشت. برای هر یال، یک رأس ابتدا و یک رأس انتها وجود دارد. در شکل زیر، دو رأس «a» و «b»، و ارتباط بین آن‌ها، یعنی یال نشان داده شده است.

یال

گراف

گراف G را به‌صورت (G=(V,E تعریف می‌کنیم که در آن، V مجموعه‌‌ای از همه رئوس و E مجموعه همه یال‌های آن است.

مثال ۱

در شکل زیر، cd ،ac ،ab و bd یال‌های گراف هستند. به‌طور مشابه، c ،b ،a و d رئوس گراف را نشان می‌دهند.

گراف

مثال ۲

در گراف شکل زیر نیز، c ،b ،a و d رئوس و ad ،ac ،ab و cd یال‌ها را نشان می‌دهند.

گراف

حلقه

اگر در یک گراف، یک یال از رأسی شروع و به همان ختم شود، آن را حلقه می‌نامیم.

مثال ۱

در گراف شکل زیر، V یک یال برای رئوس یا رأس (V,V) است که یک حلقه را تشکیل می‌دهد.

حلقه

مثال ۲

گراف زیر، دو حلقه دارد که در دو رأس a و b تشکیل شده‌اند.

حلقه

مرتبه یا درجه رأس

تعداد رأس‌های مجاور رأس V را مرتبه یا درجه رأس V می‌نامند و آن را با (deg(V نشان می‌دهند. در یک گراف ساده با n رأس، مرتبه هر کدام از رأس‌ها در رابطه زیر صدق می‌کند:

deg(v) ≤ n – 1

هر رأس می‌تواند با رئوس مجاور یال تشکیل دهد، اما با خودش نمی‌تواند. بنابراین، مرتبه هر رأس، حداکثر برابر با تعداد یال‌های گراف منهای یک است. این عدد ۱، برای نشان دادن این است که رأس مورد نظر نمی‌تواند حلقه تشکیل دهد. اگر یک حلقه در هر یک از رئوس وجود داشته باشد، آن‌گاه گراف ساده نیست. گراف ساده را در ادامه توضیح خواهیم داد.

مرتبه رأس را می‌توان در دو نوع گراف بررسی کرد:

  • گراف جهت‌دار
  • گراف بدون جهت

مرتبه رأس در گراف بدون جهت

گراف بدون جهت، گرافی است که یال‌های آن جهت ندارند.

مثال ۱

گراف زیر، یک گراف بدون جهت است.

گراف بدون جهت

در گراف بالا، مرتبه رئوس به‌شرح زیر است:

  • deg(a) = 2، زیرا رأس «a» دو یال دارد.
  • deg(b) = ۳، زیرا رأس «b» سه یال دارد.
  • deg(c) = 1، زیرا رأس «c» یک یال دارد. بنابراین، «c» یک رأس آویزان است.
  • deg(d) = 2، زیرا رأس «d»، دو یال دارد.
  • deg(e) = 0، زیرا رأس «e»، هیچ یالی ندارد. بنابراین، «e» یک رأس جدا است.
مثال ۲

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

گراف بدون جهت

در گراف بالا، داریم:

deg(a) = 2, deg(b) = 2, deg(c) = 2, deg(d) = 2, deg(e) = 0

رأس «e»، یک رأس جدا است. این گراف هیچ رأس آویزانی ندارد.

مرتبه رأس در گراف جهت‌دار

در یک گراف جهت‌دار، هر رأس، یک مرتبه ورودی و یک مرتبه خروجی دارد.

مرتبه ورودی گراف جهت‌دار

مرتبه ورودی رأس V، تعداد یال‌هایی است که به رأس V وارد می‌شوند و آن را با (deg(V نشان می‌دهند.

مرتبه خروجی گراف جهت‌دار

مرتبه خروجی رأس V، تعداد یال‌هایی است که از رأس V خارج شده که با (deg+(V نشان داده می‌شود.

مثال ۱

گراف جهت‌دار شکل زیر را در نظر بگیرید. دو یال «ad» و «ab» از رأس «a» خارج می‌شوند. بنابراین، مرتبه خروجی آن، برابر با ۲ است. همچنین یال «ga» به این رأس وارد می‌شود. در نتیجه مرتبه ورودی رأس «a»، برابر با ۱ است.

گراف جهت‌دار

مرتبه ورودی و خروجی سایر رئوس گراف، در جدول زیر آورده شده‌اند.

رأس مرتبه ورودی مرتبه خروجی
a 1 2
b 2 0
c 2 1
d 1 1
e 1 1
f 1 1
g 0 2
مثال ۲

گراف جهت‌دار شکل زیر را در نظر بگیرید. در این گراف، یال «ae»‌ از رأس «a» خارج می‌شود. بنابراین، مرتبه خروجی آن برابر ۱ است. به‌طور مشابه،‌ یال «ba» به رأس «a» وارد می‌شود، در نتیجه مرتبه خروجی این رأس برابر با ۱ خواهد بود.

گراف جهت‌دار

مرتبه ورودی و خروجی سایر رئوس گراف، در جدول زیر آورده شده‌ است.

رأس مرتبه ورودی مرتبه خروجی
a 1 1
b 0 2
c 2 0
d 1 1
e 1 1

رأس آویزان

رأسی با یک یال را یک رأس آویزان می‌نامیم. در حقیقت، رأسی آویزان است که مرتبه آن، یک باشد.

مثال

در شکل زیر، رئوس «a» و «b»، از طریق یال «ab» با یک‌دیگر ارتباط دارند. بدیهی است که رأس «a» فقط با رأس «b» ارتباط دارد و بالعکس، بنابراین، رئوس «a» و «b» آویزان هستند.

رأس آویزان

رأس جدا

رأسی را جدا می‌نامیم که مرتبه آن صفر باشد.

مثال

در شکل زیر، هیچ ارتباطی بین دو رأس «a» و «b» وجود ندارد. بنابراین، مرتبه هردو رأس، صفر است. این رئوس، جدا نامیده می‌شوند.

رأس جدا

مجاورت

مجاورت برای رأس و یال به‌صورت زیر تعریف می‌شود:

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

مثال ۱

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

  • رئوس «a» و «b» مجاور هستند، زیرا یال مشترک «ab» بین آن‌ها وجود دارد.
  • رئوس «a» و «d» مجاور هستند، زیرا یال مشترک «ad» بین آن‌ها وجود دارد.
  • یال‌های «ab» و «be» مجاور هستند، زیرا رأس مشترک «b» بین آن‌ها وجود دارد.
  • یال‌های «be» و «de» مجاور هستند، زیرا رأس مشترک «e» بین آن‌ها وجود دارد.

مجاورت

مثال ۲

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

  • رئوس «a» و «d» مجاور هستند، زیرا یال مشترک «ad» بین آن‌ها وجود دارد.
  • رئوس «c» و «b» مجاور هستند، زیرا یال مشترک «cb» بین آن‌ها وجود دارد.
  • یال‌های «ad» و «cd» مجاور هستند، زیرا رأس مشترک «d» بین آن‌ها وجود دارد.
  • یال‌های «ac» و «cd» مجاور هستند، زیرا رأس مشترک «c» بین آن‌ها وجود دارد.

مجاورت

یال‌های موازی

اگر دو رأس یک گراف، با بیش از یک یال به یک‌دیگر وصل شده باشند، آن یال‌ها را یال‌های موازی می‌نامیم.

یال‌های موازی

در گراف بالا، «a» و «b»، دو رأس هستند که از طریق دو یال «ab» و «ab» به یک‌دیگر متصل شده‌اند. بنابراین، دو یال موازی هستند.

گراف چندگانه

گرافی که یال موازی داشته باشد، گراف چندگانه یا شبه‌گراف نامیده می‌شود.

مثال ۱

در گراف شکل زیر، پنج یال «cd» ،«cd» ،«ac» ،«ab» و «bd» وجود دارد. از آن‌جایی که بین دو رأس «c» و «d»، دو یال موازی وجود دارد، گراف چندگانه است.

گراف چندگانه

مثال ۲

در گراف شکل زیر، بین دو رأس «b» و «c» دو یال وجود دارد. رئوس «e» و «d» نیز دو یال دارند. بنابراین، گراف زیر، یک گراف چندگانه است.

گراف چندگانه

دنباله مرتبه گراف

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

مثال ۱

در گراف شکل زیر، برای رئوس {d, a, b, c, e}، دنباله مرتبه، به‌صورت {1 ,2 ,2 ,2 ,3} است.

دنباله درجه گراف

رأس a b c d e
متصل به b,c a,d a,d c,b,e d
درجه 2 2 2 ۳ ۱

مثال ۲

در گراف شکل زیر، برای رئوس {a, b, c, d, e, f}، دنباله مرتبه، به‌صورت {0 ,2 ,2 ,2 ,2 ,2} است.

دنباله درجه گراف

رأس a b c d e f
متصل به b,e a,c b,d c,e a,d
درجه 2 2 2 2 2 0

مسیر

مسیر، دنباله ای از رأس‌ها است، به‌طوری که از هر أس به رأس دیگرِ این دنباله، یالی وجود داشته باشد.

دور

به مسیری که رأس ابتدایی و انتهایی آن بر هم منطبق باشد، دور می‌گوییم.

ویژگی‌های اساسی گراف‌ها

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

فاصله بین دو رأس

فاصله بین دو رأس U و V، تعداد یال‌های کوتاه‌ترین مسیر بین آن‌ها است. این بدین معنی است که اگر چند مسیر بین دو رأس وجود داشته باشد، آن‌گاه کوتاه‌ترین مسیر را برای فاصله بین دو رأس در نظر می‌گیریم. فاصله بین دو رأس U و V‌ را با (d(U,V نشان می‌دهند.

مثال

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

فاصله بین دو گراف

در این گراف، فاصله رأس «d» از رأس «e» برابر با ۱ است، زیرا یک یال بین آن‌ها وجود دارد. مسیرهای بین دو رأس «d» و «e» عبارتند از:

  • ab ،da و be
  • fg ،df و ge
  • de (فاصله بین دو رأس)
  • ab ،ca ،fc ،df و be
  • fg ،cf ،ac ،da و ge

خروج از مرکز یک رأس

حداکثر فاصله بین یک رأس از رأس‌های دیگر، خروج از مرکز آن رأس نامیده می‌شود. خروج از مرکز رأس V را با (e(V نشان می‌دهند.

مثال

در گراف شکل زیر، خروج از مرکز رأس «a» برابر با ۳ است.

گریز از مرکز

  • فاصله «a» تا «b» برابر با ۱ است («ab»).
  • فاصله «a» تا «c» برابر با ۱ است («ac»).
  • فاصله «a» از «d» برابر با ۱ است («ad»).
  • فاصله «a» از «e» برابر با ۲ است («be» ،«ab» یا «de» ،«ad»).
  • فاصله «a» از «f» برابر با ۱ است («cf» ،«ac» یا «df» ،«ad»).
  • فاصله «a» از «g» برابر با ۳ است («fg» ،«cf» ،«ac» یا «fg» ،«df» ،«ad»).

بنابراین، خروج از مرکز برابر با ۳، یعنی حداکثر فاصله رأس «a» از رأس «g» است.

به عبارت دیگر:

e(g) = 3, e(f) = 3, e(e) = 3, e(d) = 2, e(c) = 3, e(b) = 3

شعاع گراف

کوچک‌ترین خروج از مرکز رئوس گراف G را شعاع گراف می‌نامند و آن را با (r(G نشان می‌دهند.

مثال

در گراف شکل زیر، r(G) = 2 است.

شعاع گراف

قطر گراف

بزرگ‌ترین خروج از مرکز رئوس گراف G را قطر گراف می‌نامند و آن را با (d(G نشان می‌دهند.

مثال

در گراف شکل زیر، d(G) = 3 است.

قطر گراف

نقطه مرکزی

اگر خروج از مرکز یک رأس با شعاع آن برابر باشد، آن رأس را نقطه مرکزی می‌نامیم. به عبارت دیگر، اگر (e(V) = r(V باشد، V را نقطه مرکزی گراف G می‌نامیم.

مثال

در گراف شکل زیر، d نقطه مرکزی است، زیرا e(d) = r(d) = 2 است.

قطر گراف

مرکز

مجموعه همه نقاط مرکزی یک گراف، مرکز آن نامیده می‌شود.

مثال

در گراف زیر، {d} مرکز گراف است.

مرکز گراف

محیط گراف

تعداد یال‌های طولانی‌ترین دور گراف G را محیط G می‌نامند.

مثال

در گراف شکل زیر، محیط برابر با ۶ است که از طولانی‌ترین دور a-c-f-g-e-b-a یا a-c-f-d-e-b-a به‌دست آمده است.

محیط گراف

 

کمر گراف

تعداد یال‌های کوتاه‌ترین دور گراف را کمر گراف می‌نامیم و آن را با (g(G نمایش می‌دهیم.

در گراف شکل زیر، کمر برابر با ۴ است که از کوتاه‌ترین دور a-c-f-d-a یا d-f-g-e-d یا a-b-e-d-a به‌دست آمده است.

محیط گراف

قضیه مجموع مرتبه‌های رئوس

اگر (G = (V, E یک گراف بدون جهت با رئوس {V = {V1, V2,…Vn باشد، آن‌گاه، داریم (|E| تعداد اعضای مجموعه E است):

$$\sum_\limits{i=1}^n \mathrm{deg}(\mathrm{V_i})=2|\mathrm{E}|$$

نتیجه ۱

اگر (G = (V, E یک گراف جهت‌دار با رئوس {V = {V1, V2,…Vn باشد، آن‌گاه، داریم:

$$\sum_\limits{i=1}^n \mathrm{deg}^+(\mathrm{V_i})=|\mathrm{E}|=\sum_\limits{i=1}^n \mathrm{deg}^-(\mathrm{V_i})$$

نتیجه ۲

در هر گراف بدون جهت، تعداد رئوس با مرتبه فرد، زوج است.

نتیجه ۳

در هر گراف بدون جهت، اگر مرتبه هر رأس را k در نظر بگیریم، آن‌گاه

|k|V| = 2|E

نتیجه 4

در هر گراف بدون جهت، اگر مرتبه هر رأس، حداقل برابر با k باشد، آن‌گاه داریم:

|k|V| ≤ 2|E

نتیجه ۵

در هر گراف بدون جهت، اگر مرتبه هر رأس، حداکثر برابر با k باشد، آن‌گاه داریم:

|k|V| ≥ 2|E

انواع گراف‌ها

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

گراف تهی

گرافی را که یال نداشته باشد، تهی یا پوچ می‌گوییم.

مثال

شکل زیر، گرافی را نشان می‌دهد که سه رأس به‌نام‌های «b» ،«a» و «c» دارد، اما یالی ندارد. به همین دلیل، این گراف را تهی می‌نامیم.

گراف تهی

گراف بدیهی

گرافی که فقط یک رأس دارد، بدیهی نامیده می‌شود.

مثال

گراف شکل زیر که فقط یک رأس «a» دارد، گرافی بدیهی است.

گراف بدیهی

گراف بدون جهت

گراف بدون جهت، گرافی است که یال دارد، اما یال‌های آن جهت ندارند.

مثال

در گراف شکل زیر «f» ،«e» ،«d» ،«c» ،«b» ،«a» و «g» رئوس و «gf» ،«ag» ،«da» ،«cd» ،«bc» ،«ab» و «ef» یال‌های گراف هستند. از آن‌جایی که گراف بدون جهت است، یال‌های «ab» و «ba»، یکسان هستند. این گفته برای سایر یال‌های گراف نیز صادق است.

گراف بدون جهت

گراف جهت‌دار

در یک گراف جهت‌دار، هر یال دارای جهت است.

مثال

در گراف شکل زیر «f» ،«e» ،«d» ،«c» ،«b» ،«a» و «g» رئوس و «fe» ،«ec» ،«ad» ،«dc» ،«cb» ،«ab» و «gf» و «ga» یال‌های گراف هستند. از آن‌جایی که گراف جهت‌دار است،‌ جهت یال‌ها با فلش مشخص شده است. دقت کنید که در یک گراف جهت‌دار، «ab» با «ba» تفاوت دارد.

گراف جهت‌دار

گراف ساده

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

  • حداکثر تعداد یال‌های ممکن در یک گراف ساده با n رأس، برابر با $$n_{C_2}=n(n-1)/2$$.
  • تعداد گراف‌های ساده‌ای را که می‌توان با n رأس ساخت، برابر است با: $$2^{n_{C_2}}=2^{n(n-1)/2}$$.

مثال

در گراف شکل زیر، سه رأس و سه یال وجود دارد که حداکثر تعداد ممکن است (البته به‌جز حلقه و یال موازی). حداکثر تعداد گراف‌های ساده‌ای که با سه رأس می‌توان ساخت، برابر با ۸ است. اثبات این گفته‌ها به سادگی با استفاده از فرمول‌های بالا امکان‌پذیر است.

گراف ساده

گراف‌های زیر، ۸ حالت ممکن را نشان می‌دهند.

هشت گراف ممکن

گراف همبند

گراف G را همبند گوییم، اگر یک مسیر بین هر دو رأس آن وجود داشته باشد. در حقیقت، باید حداقل یک یال برای هر رأس وجود داشته باشد.

مثال

در گراف شکل زیر، برای هر رأس می‌توان مسیری پیدا کرد که به رأس دیگر برسد. بنابراین، گراف همبند است.

گراف همبند

گراف ناهمبند

گراف G را ناهمبند گوییم، اگر حداقل دو رأس جدا داشته باشد.

مثال ۱

شکل زیر، یک گراف ناهمبند را نشان می‌دهد که دو بخش دارد؛ یکی شامل رئوس «c» ،«b» ،«a» و «d» و دیگری شامل رئوس «g» ،«f» ،«e» و «h».

گراف ناهمبند

مثال ۲

شکل زیر، یک گراف ناهمبند را نشان می‌دهد که دو بخش a-b-f-e و c-d دارد.

گراف ناهمبند

گراف منتظم

گرافی را منتظم می‌نامیم که همه رئوس آن، مرتبه یکسانی داشته باشند. اگر در یک گراف، درجه هر رأس، برابر با «k» باشد، آن گراف را گراف k-منتظم می‌گوییم.

مثال

در گراف‌های زیر، همه رئوس مرتبه یکسانی دارند. بنابراین، منتظم هستند.

گراف منتظم

در هر دو گراف بالا، مرتبه رئوس برابر با ۲ است، بنابراین، این دو گراف، ۲-منتظم هستند.

گراف کامل

گراف ساده‌ای را کامل می‌گوییم که هریک از رأس‌های آن، با رئوس دیگر یک یال مشترک داشته باشد و آن را با $$\mathrm{K_n}$$ نشان می‌دهیم.

مثال

در گراف‌های زیر، هر رأس جز خودش با سایر رئوس ارتباط دارد.

گراف کامل

در گراف I داریم:

a b c
a متصل نیست متصل است متصل است
b متصل است متصل نیست متصل است
c متصل است متصل است متصل نیست

برای گراف II نیز می‌توان جدول زیر را ارائه کرد:

p q r s
p متصل نیست متصل است متصل است متصل است
q متصل است متصل نیست متصل است متصل است
r متصل است متصل است متصل نیست متصل است
s متصل است متصل است متصل است متصل نیست

گراف دوری

یک گراف ساده با n رأس و n یال (n >= 3)، یک گراف دوری نامیده می‌شود، اگر همه یال‌های آن، دوری به‌طول n را تشکیل دهند. به عبارت دیگر، اگر مرتبه هر رأس گراف، ۲ باشد، آن‌گاه گراف دوری است. گراف دوری را با $$\mathrm{C_n}$$ نشان می‌دهند.

مثال

گراف‌های شکل زیر را در نظر بگیرید.

گراف دوری

  • گراف I سه رأس و سه یال دارد که دور ab-bc-ca را تشکیل می‌دهند.
  • گراف II چهار رأس و چهار یال دارد که دور pq-qs-sr-rp را تشکیل می‌دهند.
  • گراف III پنج رأس و پنج یال دارد که دور ik-km-ml-lj-ji را تشکیل می‌دهند.

بنابراین، همه گراف‌های بالا، گراف دوری هستند.

گراف چرخ

گراف چرخ، با افزدون یک رأس جدید به گراف دوری $$\mathrm{C_{n-1}}$$ به‌دست می‌آید. گراف چرخ را با $$\mathrm{W_n}$$ نشان می‌دهند. رأس جدید، هاب نامیده می‌شود.

مثال

سه گراف زیر، گراف چرخ هستند.

گراف چرخ

گراف مدوّر یا دوردار

گرافی را مدوّر یا دوردار گوییم که حداقل یک دور داشته باشد.

مثال

در گراف شکل زیر، دو دور a-b-c-d-a و c-f-g-e-c وجود دارد. بنابراین، گراف زیر یک گراف مدوّر یا دوردار است.

گراف مدور

گراف غیرمدوّر

گرافی را که دوری نداشته باشد، گراف غیرمدور می‌نامیم.

مثال

در گراف شکل زیر، هیچ دوری وجود ندارد، بنابراین، گراف غیرمدور است.

گراف غیرمدور

گراف دوبخشی

گراف ساده (G = (V, E را با دو افراز {V = {V1, V2 یک گراف دوبخشی می‌نامیم، اگر هر یال E به یک رأس از $$\mathrm{V_1}$$ و یک رأس از $$\mathrm{V_۲}$$ وصل باشد. در حالت کلی، یک گراف دوبخشی، دو مجموعه از رئوس ($$\mathrm{V_1}$$ و $$\mathrm{V_2}$$) است که هر یال از آن، رأسی از $$\mathrm{V_1}$$ را به رأسی از $$\mathrm{V_2}$$ وصل می‌کند.

مثال

در گراف شکل زیر، می‌توان دو مجموعه رأس $$\mathrm{V_۱}$$ و $$\mathrm{V_2}$$ را مشاهده کرد. در این‌جا، دو یال «ae» و «bd»‌، رئوس دو مجموعه را به یک‌دیگر وصل کرده‌اند.

گراف دوبخشی

گراف دوبخشی کامل

گراف دوبخشی (G = (V, E را با افراز {V = {V1, V2 یک گراف دوبخشی کامل می‌گوییم، اگر همه رئوس $$\mathrm{V_۱}$$ به همه رئوس $$\mathrm{V_۲}$$ متصل باشند.

مثال

گراف شکل زیر، یک گراف دوبخشی کامل است، زیرا یال‌ها همه رئوس دو مجموعه $$\mathrm{V_۱}$$ و $$\mathrm{V_۲}$$ را به هم وصل می‌کنند.

گراف دوبخشی کامل

اگر V1| = m| و V2| = n| باشد، آن‌گاه گراف دوبخشی کامل با Km, n نشان داده می‌شود.

  • Km, n، تعداد (m+n) رأس و (mn) یال دارد.
  • اگر m=n باشد، Km, n یک گراف منتظم است.

توجه کنید که در حالت کلی،‌ گراف دوبخشی کامل، یک گراف کامل نیست. Km,n یک گراف کامل است، اگر m=n=1 باشد.

حداکثر تعداد یال‌های یک گراف دوبخشی با n رأس، از رابطه $$\left [ \frac{n^2}{4} \right ] $$ به‌دست می‌آید.

گراف ستاره

یک گراف دوبخشی کامل، به‌فرم K1, n-1 یک گراف ستاره با n رأس است. به عبارت دیگر، یک گراف دوبخشی کامل را گراف ستاره می‌گوییم، اگر یک رأس به یک مجموعه متعلق باشد و همه رئوس باقی‌مانده به سایر مجموعه‌ها تعلق داشته باشند.

مثال

هر یک از گراف‌های شکل زیر، n رأس دارند، که 1-n تا از رئوس آن‌ها به یک رأس متصل است.

گراف ستاره

مکمل گراف

گراف ساده $$\mathrm{\bar{G}}$$ را مکمل گراف ساده $$\mathrm{G}$$ می‌نامیم، اگر رئوس آن‌ها یکسان بوده و هر دورأسی که در $$\mathrm{G}$$ مجاور نبوده‌اند، در $$\mathrm{\bar{G}}$$ مجاور باشند.

ترکیب دو گراف مکمل، یک گراف کامل را تشکیل می‌دهد.

مثال

در شکل زیر، گراف I دو یال «cd» و «bd» دارد. گراف II مکمل این گراف است که ۴ یال دارد. همان‌طور که می‌بینیم، یال‌های گراف I در گراف II وجود ندارند و بالعکس. مکمل گراف

در شکل بالا، ترکیب دو گراف، یک گراف کامل را تشکیل داده است.

واژه‌نامه

واژه  معادل انگلیسی واژه معادل انگلیسی
گراف Graph قطر گراف Diameter of a Graph
نقطه Point نقطه مرکزی Central Point
خط Line محیط گراف Circumference
رأس Vertex کمر گراف Girth
یال Edge گراف تهی Null Graph
حلقه Loop گراف بدیهی Trivial Graph
مرتبه رأس Degree of Vertex گراف بدون جهت Non-Directed Graph
رأس آویزان Pendent Vertex گراف جهت‌دار Directed Graph
رأس جدا Isolated Vertex گراف ساده Simple Graph
مجاورت Adjacency گراف همبند Connected Graph
یال‌های موازی Parallel Edges گراف ناهمبند Disconnected Graph
گراف چندگانه Multi Graph گراف منتظم Regular Graph
دنباله مرتبه گراف Degree Sequence of a Graph گراف کامل Complete Graph
فاصله بین دو رأس Distance between Two Vertices گراف دوری Cycle Graph
خروج از مرکز یک رأس Eccentricity of a Vertex گراف چرخ Wheel Graph
شعاع گراف Radius گراف مدوّر Cyclic Graph
مرکز Centre گراف غیرمدوّر Acyclic Graph
گراف دوبخشی Bipartite Graph گراف دوبخشی کامل Complete Bipartite Graph
گراف ستاره Star Graph مکمل گراف Complement of a Graph
دور Circuit مسیر Path

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

^^

به عنوان حامی، استارتاپ، محصول و خدمات خود را در انتهای مطالب مرتبط مجله فرادرس معرفی کنید.

telegram
twitter

سید سراج حمیدی

«سید سراج حمیدی» دانش‌آموخته مهندسی برق است. فعالیت‌های کاری و پژوهشی او در زمینه سیستم‌های فتوولتائیک و کاربردهای کنترل در قدرت بوده و، در حال حاضر، آموزش‌های مهندسی برق و ریاضیات مجله فرادرس را می‌نویسد.

بر اساس رای 1 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *