آشنایی با چند مورد از گراف‌های مشهور دنیای برنامه‌نویسی

گراف آزاد-مثلث

یک گراف آزاد-مثلث گرافی بدون جهت است که هیچ سه راس آن تشکیل مثلث ندهند. معادل گراف‌های آزاد-مثلث می‌تواند گراف‌هایی که عدد خوشه‌ای آن‌ها حداکثر ۲ است، گراف‌هایی که کوچکترین دور در آن‌ها حداقل ۴ است، گراف‌های بدون دور ۳تایی یا گراف‌های با استقلال محلی باشد. طبق نظریه توران یک گراف n راسی آزاد-مثلث با بیشترین تعداد یال یک گراف کامل دوبخشی است که در آن تعداد راس‌ها در هر بخش تا جای ممکن برابرند. مسئله پیدا کردن مثلث مانند این مسئله است که گراف، آزاد-مثلث هست یا نه. وقتی گراف مثلث داشته باشد الگوریتمها معمولاً نیازمند این هستند که ۳ راس پیدا کنند که با هم تشکیل مثلث می‌دهند.

گراف تهی

گراف تهی ممکن است اشاره به گرافی از مرتبه صفر داشته باشد یا معادل گرافی بی یال باشد. (دومی که گاهی اوقات به "گراف خالی" نام برده می‌شود).در نظریه دسته‌ها، گراف تهی، بنابر برخی از تعاریف «دسته گراف‌ها» عضوی اولیه در دسته است. گراف تهK{0}  گرافی منحصر بفرد است که هیچ رأسی ندارد (بنابراین مرتبه صفر است). در نتیجه این گراف هیچ یالی هم ندارد.

گراف چگال

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

گراف خط

گراف غیر تهی G را در نظر بگیرید. اگر به جای هر یال G راأسی در نظر بگیریم و دو رأس را به هم متصل می‌کنیم. در صورتی که یال‌های متناظر آن دو رأس در G در یک رأس از G با هم مشترک باشند.

گراف خودمکمل

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

گراف دوهمبند

یک شبکه ارتباطی در برابر نقص دارای قدرت تحمل است اگر دارای مسیرهای دیگری میان راس‌ها باشد. هر چه مسیرهای مجزا بیشتر باشد٫ بهتر است. این مثال دقیقا مفهوم گراف چند همبند (k-vertex-connected graph) است. گراف دوهمبند (biconnected) حالت خاصی از گراف چند همبند است. گراف دوهمبند٫ یک گراف همبند است با این خصوصیت که غیر جداشدنی باشد٫ یعنی با حذف یک راس همبند باقی بماند. این خاصیت برای مدیریت یک گراف با افزونگی دوگانه سودمند است به این منظور که از ناهمبند شدن گراف با حذف یک یال آن جلوگیری شود. به جهت خاصیت افزونگی، استفاده از گراف دوهمبند در زمینه شبکه اهمیت زیادی دارد.

گراف شکافته

گراف شکافته (Split Graph) گرافی است که رئوس آن را می‌توان به یک کلیک و یک مجموعه مستقل افراز نمود. گراف‌های شکافته را اولین بار فولدس و همر مطالعه نموده، و همچنین به‌طور مستقل توسط تیشکویچ و چرنیاک معرفی شدند. ممکن است گراف شکافته شده بیش از یک افراز به کلیک و مجموعه مستقل داشته باشد؛ به عنوان مثال، مسیر a-b-c گراف شکافته شده‌ای است که رئوس آن را می‌توان به سه روش مختلف افراز نمود:

کلیک a,b و مجموعه مستقل c

کلیک b,c و مجموعه مستقل a

کلیک b و مجموعه مستقل a,c

گراف‌های شکافته شده را می‌توان برحسب زیرگراف های القاء شده ممنوعه شان مشخصه سازی نمود: یک گراف دلخواه شکافته شده‌است اگر و تنها اگر هیچ زیرگراف القاء شده آن که چهار یا پنج رأس داشته یا دارای یک جفت یال مجزا باشد (متمم یک ۴-دور)، دوری نباشد.[۴]

گراف فاکتور بحرانی

گراف فاکتور بحرانی یا گراف هایپومچبل (Factor-critical graph) یک گراف با n راس می‌باشد به طوری که هر زیر گراف n-1 عضوی دارای خاصیت تطابق کامل می‌باشد.(تطابق کامل در یک گراف به این معنی است که یک زیر مجموعه از یال‌های این گراف هستند که در این زیر مجموعه هر یک از راس‌ها دقیقاً نقطه پایانی یکی از یال‌ها هستند. نوع دیگری از اتصال که در آن تمامی راس‌ها به جز یکی از آن‌ها پوشش داده می‌شوند تطابق کامل نزدیک (near-perfect matching) نامیده می‌شود. پس به‌طور مشابه یک گراف فاکتور_بحرانی گرافی است که در آن تطابق‌های کامل نزدیک وجود داشته باشد طوری که در هر کدام از یکی از راس‌ها صرف نظر شده باشد.

هر دور به طول فرد یک گراف فاکتور_بحرانی می‌باشد، همانطور که هر گراف کامل با تعداد فرد راس یک گراف فاکتور_بحرانی می‌باشد. به‌طور عمومی هر گراف همیلتونی با تعداد فرد راس یک گراف فاکتور_بحرانی می‌باشد. گراف‌های دوستی یا friendship graphs (گراف‌هایی که از اتصال مجموعه‌ای از مثلث‌ها به وجود آمده و در یک راس مشترک هستند) مثال دیگری از گراف فاکتور_بحرانی‌ها هستند با این تفاوت که این گراف‌ها غیر همیلتونی هستند. هر گراف همبند پنجه آزاد (claw-free) با تعداد فرد راس، یک گراف فاکتور_بحرانی می‌باشد. برای مثال گراف ۱۱ راسی که از حذف یک راس از بیست وجهی منتظم به وجود می‌آید و همبند نیز می‌باشد، یک گراف فاکتور_بحرانی می‌باشد. این نتیجه به‌طور مستقیم از یک قضیه بنیادی تر با این مضمون که هر گراف پنجه آزادِ همبند که دارای تعدادی زوج راس باشد حتماً دارای یک تطابق کامل می‌باشد، حاصل می‌شود.

گراف کیلی

در ریاضیات یک گراف کیلی، گرافی است که ساختار جبری یک گروه جبری را در خود دارد. نام گراف کیلی پس از قضیهٔ کیلی پیشنهاد شد که در تعریف آن یک گروه به همراه مجموعه‌ای از عناصر آن (معمولاً مولد آن گروه) در نظر گرفته می‌شود.

گراف مسطح

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

گراف‌های پنجه‌آزاد

در نظریه گراف، که بخشی از ریاضیات است، گراف پنجه‌آزاد گرافی است که زیرگراف پنجه نداشته باشد. پنجه نام دیگر گراف دوبخشی کامل K1,3 است (یک گراف ستاره با سه برگ و یک راس مرکزی). یک گراف پنجه‌آزاد گرافی است که هیچ‌یک از زیر گراف‌های آن پنجه نباشد؛ یعنی هر زیرگراف چهار راسی آن یالی بیش از سه یالی که آن‌ها را بدین شکل به هم متصل می‌کنند داشته باشد. به بیانی دیگر گراف پنجه‌آزاد گرافی است که در آن مکمل گراف القایی همسایه‌های هر راس آن گراف، مثلث آزاد باشد. گراف‌های پنجه‌آزاد، در ابتدا به عنوان تعمیم گراف یالی شناخته می‌شدند، اما با کشف این سه خاصیت مهم، اهمیت بیشتری پیدا کردند:

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

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

توصیف خصوصیات گراف ایده‌آل پنجه آزاد.

نمایش گراف‌ها

ساختار داده‌های مختلفی برای نمایش گراف‌ها در عمل استفاده می‌شود:

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

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

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