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

تاریخچه

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

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

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

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

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

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

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

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

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

فیلم آموزش ریاضیات‌ گسسته در فرادرس

کلیک کنید

گراف چیست؟

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

در شکل بالا، 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 تشکیل شده‌اند.

درجه راس

درجه یک راس معادل است با تعداد یا‌ل‌هایی که به آن راس می‌رسند و با (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»، برابر با ۱ است.

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

مثال ۲

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

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

رأس آویزان

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

مثال

در شکل زیر، رئوس «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 است):