گراف پترسن چیست؟ آشنایی با یکی از مشهورترین گراف‌های ریاضی

مقدمه

در نظریه گراف، برخی گراف‌ها به دلیل ساختار ساده اما ویژگی‌های عمیق و قابل‌توجه خود، جایگاه ویژه‌ای پیدا کرده‌اند. یکی از معروف‌ترین آن‌ها گراف پترسن یا Petersen Graph است؛ گرافی که با وجود داشتن تنها ۱۰ رأس و ۱۵ یال، در بسیاری از مباحث نظریه گراف به‌عنوان نمونه، مثال نقض و ساختاری برای بررسی قضیه‌های مختلف استفاده می‌شود. گراف پترسن در نگاه اول ممکن است فقط شکلی متقارن و زیبا به نظر برسد، اما در پس این ظاهر ساده، ویژگی‌های ریاضی مهمی وجود دارد. این گراف در مطالعه رنگ‌آمیزی، دورها، همبندی، تطابق، گراف‌های منتظم و بسیاری از مسائل دیگر مورد استفاده قرار می‌گیرد. به همین دلیل دانشجویانی که وارد مباحث نظریه گراف می‌شوند، معمولاً خیلی زود با این گراف روبه‌رو خواهند شد. در این مقاله با ساختار گراف پترسن، ویژگی‌های اصلی آن، نحوه نمایش و دلیل اهمیت آن در نظریه گراف آشنا می‌شویم.

گراف پترسن چیست؟

گراف پترسن یک گراف بدون جهت است که از ۱۰ رأس و ۱۵ یال تشکیل شده است. هر رأس در این گراف دقیقاً با سه رأس دیگر ارتباط دارد. به چنین گرافی، گراف ۳-منتظم یا Cubic Graph گفته می‌شود. اگر درجه هر رأس را برابر با تعداد یال‌هایی بدانیم که به آن رأس متصل هستند، در گراف پترسن درجه تمام رأس‌ها برابر با ۳ است. همین یکنواختی یکی از ویژگی‌هایی است که ساختار آن را منظم و از نظر ریاضی جالب می‌کند. معمول‌ترین تصویر گراف پترسن شامل یک پنج‌ضلعی بیرونی و یک ستاره پنج‌پر در داخل آن است. پنج رأس بیرونی به شکل یک پنج‌ضلعی به یکدیگر متصل می‌شوند و پنج رأس داخلی نیز ساختار یک ستاره را تشکیل می‌دهند. سپس هر رأس خارجی به یک رأس داخلی متصل می‌شود. البته باید توجه داشت که شکل هندسی رسم‌شده، خود گراف نیست. آنچه در نظریه گراف اهمیت دارد، روابط میان رأس‌ها و یال‌هاست، نه محل قرار گرفتن رأس‌ها روی صفحه.

چرا گراف پترسن تا این اندازه مشهور است؟

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

گراف پترسن یک گراف منتظم است

یکی از نخستین ویژگی‌های مهم این گراف، منتظم بودن آن است. در یک گراف منتظم، تمام رأس‌ها دارای درجه برابر هستند. در گراف پترسن هر رأس دقیقاً سه یال دارد؛ بنابراین این گراف یک گراف ۳-منتظم است.

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

۱۰ × ۳ = ۳۰

بر اساس قضیه دست‌دادن در نظریه گراف، مجموع درجات رأس‌ها برابر با دو برابر تعداد یال‌هاست. بنابراین:

۳۰ ÷ ۲ = ۱۵

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

دورها در گراف پترسن

یکی دیگر از موضوعات مهم در بررسی گراف‌ها، مفهوم دور یا Cycle است. دور مسیری است که از یک رأس آغاز می‌شود و پس از عبور از چند رأس و یال دوباره به همان رأس اولیه بازمی‌گردد، بدون آنکه یال‌ها به شکل نامناسب تکرار شوند. گراف پترسن دارای دورهای مختلفی است، اما یکی از ویژگی‌های مهم آن این است که کوتاه‌ترین دور آن طول ۵ دارد. به عبارت دیگر، در گراف پترسن دور سه‌تایی یا چهار‌تایی وجود ندارد. به طول کوتاه‌ترین دور در یک گراف، محیط دوری یا Girth گفته می‌شود. بنابراین محیط دوری گراف پترسن برابر با ۵ است. این ویژگی در مطالعه ساختار گراف و مقایسه آن با سایر گراف‌های منتظم اهمیت زیادی دارد.

آیا گراف پترسن همیلتونی است؟

یکی از مشهورترین ویژگی‌های گراف پترسن به مفهوم دور همیلتونی مربوط می‌شود. یک دور همیلتونی دوری است که دقیقاً یک بار از تمام رأس‌های گراف عبور کند و در نهایت به نقطه شروع بازگردد. شاید با نگاه به شکل متقارن گراف پترسن تصور شود که چنین دوری به‌راحتی در آن پیدا می‌شود؛ اما نکته جالب این است که:

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

به همین دلیل گفته می‌شود گراف پترسن غیرهمیلتونی است. این ویژگی یکی از دلایل اصلی شهرت آن است. زیرا با وجود تقارن بالا و همبندی مناسب، نمی‌توان مسیری بسته ایجاد کرد که دقیقاً یک بار از تمام رأس‌های آن عبور کند. البته گراف پترسن مسیر همیلتونی دارد؛ یعنی می‌توان مسیری پیدا کرد که از تمام رأس‌ها دقیقاً یک بار عبور کند، اما این مسیر نمی‌تواند به شکل یک دور بسته شود.

همبندی در گراف پترسن

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

رنگ‌آمیزی گراف پترسن

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

تقارن در گراف پترسن

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

ارتباط گراف پترسن با جبر

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

آیا گراف پترسن در دنیای واقعی کاربرد دارد؟

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

گراف پترسن؛ نمونه‌ای از زیبایی ریاضیات

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

جمع‌بندی

گراف پترسن یکی از مشهورترین و مهم‌ترین گراف‌های شناخته‌شده در نظریه گراف است. این گراف دارای ۱۰ رأس و ۱۵ یال است و هر رأس آن درجه ۳ دارد؛ بنابراین یک گراف ۳-منتظم محسوب می‌شود. محیط دوری آن برابر با ۵ است، عدد رنگی آن ۳ است و با وجود ساختار متقارن و همبند خود، فاقد دور همیلتونی است. همین ویژگی‌ها باعث شده‌اند که گراف پترسن در بسیاری از کتاب‌ها، پژوهش‌ها و آموزش‌های مرتبط با نظریه گراف مورد استفاده قرار گیرد. مطالعه این گراف فرصتی مناسب برای درک بهتر مفاهیمی مانند رأس، یال، درجه، دور، همبندی، رنگ‌آمیزی، تقارن و همیلتونی بودن فراهم می‌کند. از سوی دیگر، ارتباط میان تقارن‌های این گراف و مفاهیم جبری نشان می‌دهد که نظریه گراف چگونه می‌تواند با سایر شاخه‌های ریاضیات پیوند پیدا کند. گراف پترسن نمونه‌ای روشن از این حقیقت است که در ریاضیات، حتی یک ساختار کوچک می‌تواند مجموعه‌ای گسترده از ایده‌ها و پرسش‌های عمیق را در خود جای دهد.