گراف – تعاریف و انواع آن به زبان ساده

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

تاریخچه

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

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

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

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

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

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

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

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

• مهندسی برق: گراف در مهندسی برق برای نمایش اتصال مدارها به کار می‌رود. برخی از این اتصالات به عنوان ستاره، مثلث، سری و موازی شناخته می‌شوند.
• علوم کامپیوتر: یکی از کاربردهای گراف در علوم کامپیوتر، مطالعه الگوریتم‌ها است. همچنین، برای بیان رابطه بین کامپیوترها در شبکه، از گراف‌ها استفاده می‌شود.
• علوم: ساختار مولکولی و شیمیایی ماده، ساختار 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, f}، دنباله مرتبه، به‌صورت {0 ,2 ,2 ,2 ,2 ,2} است.

مسیر

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

دور

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

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

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

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

فاصله بین دو رأس 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}$$ نشان می‌دهیم.

مثال

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

در گراف سمت چپ داریم:

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

گراف دوری

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

مثال

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

• گراف مثلثی شکل سه رأس و سه یال دارد که دور db-bc-cd را تشکیل می‌دهند.
• گراف مستطیلی چهار رأس و چهار یال دارد که دور pq-qs-sr-rp را تشکیل می‌دهند.
• گراف پنج‌ضلعی شکل پنج رأس و پنج یال دارد که دور 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 = {V₁, V₂ یک گراف دوبخشی می‌نامیم، اگر هر یال 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 = {V₁, V₂ یک گراف دوبخشی کامل می‌گوییم، اگر همه رئوس $$\mathrm{V_۱}$$ به همه رئوس $$\mathrm{V_۲}$$ متصل باشند.

مثال

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

اگر V₁| = m| و V₂| = n| باشد، آن‌گاه گراف دوبخشی کامل با K_{m, n} نشان داده می‌شود.

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

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

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

گراف ستاره

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

مثال

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

مکمل گراف

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

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

مثال

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

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

واژه‌نامه

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

• گزاره ها و سورهای منطقی — به زبان ساده
• نمایش ماتریسی گراف — به زبان ساده
• اصل لانه کبوتر — به زبان ساده
• برهان خلف — به زبان ساده