گراف پترسن در نظريه گراف ها

[Borna66]

گراف پترسن (http://mathphysicinfo.blogfa.com/post-13.aspx)
ساختار [/URL] [URL="http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Petersen_grap h_blue.svg"] (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Petersen_grap h_blue.svg)
گراف پترسن به شکل پنج ضلعی منتظم
دارای ۵ تقاطع


گراف پترسن، گراف مکمل (http://fa.wikipedia.org/w/index.php?title=%DA%AF%D8%B1%D8%A7%D9%81_%D9%85%DA %A9%D9%85%D9%84&action=edit&redlink=1) برای گراف خط (http://fa.wikipedia.org/w/index.php?title=%DA%AF%D8%B1%D8%A7%D9%81_%D8%AE%D8 %B7&action=edit&redlink=1)، K۵ است. همچنین گراف کنزر (http://fa.wikipedia.org/w/index.php?title=%DA%AF%D8%B1%D8%A7%D9%81_%DA%A9%D9 %86%D8%B2%D8%B1&action=edit&redlink=1) KG۵٬۲ هم می‌باشد. این بدان معنا است که اگر برای هر کدام از زیرمجموعه‌های دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعه‌های نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته می‌شود.
گراف پترسن ، گرافی غیر مسطح (http://fa.wikipedia.org/w/index.php?title=%D8%BA%DB%8C%D8%B1_%D9%85%D8%B3%D8 %B7%D8%AD&action=edit&redlink=1) است. هر گراف غیر مسطح (http://fa.wikipedia.org/w/index.php?title=%D8%BA%DB%8C%D8%B1_%D9%85%D8%B3%D8 %B7%D8%AD&action=edit&redlink=1) با گراف کامل (http://fa.wikipedia.org/wiki/%DA%AF%D8%B1%D8%A7%D9%81_%DA%A9%D8%A7%D9%85%D9%84) K۵ یا گراف دو بخشی (http://fa.wikipedia.org/w/index.php?title=%DA%AF%D8%B1%D8%A7%D9%81_%D8%AF%D9 %88_%D8%A8%D8%AE%D8%B4%DB%8C&action=edit&redlink=1) کامل K۳٬۳ هم ریخت (http://fa.wikipedia.org/w/index.php?title=%D9%87%D9%85_%D8%B1%DB%8C%D8%AE%D8 %AA&action=edit&redlink=1) یا هومئومورف است. حال آن که پترسن با هر دو گراف هم ریخت می‌باشد.


خواص عمومی

http://pnu-club.com/imported/2011/01/258.jpg (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Petersen2.jpg ) شکل (2)
گراف پترسن با عدد تقاطع 2



http://pnu-club.com/imported/2011/01/259.jpg (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Petersen3.jpg ) شکل (3)
گراف پترسن با یال‌هایی برابر با واحد




دقیقا ۱۹ گراف مکعبی متصل با ۱۰ یال وجود دارد. گراف پترسن یکی از همین ۱۹ گراف می‌باشد. این گراف تنها گرافی با ۱۰ یال از این دسته‌است که دارای قطر (http://fa.wikipedia.org/wiki/%D9%82%D8%B7%D8%B1) برابر ۲ و تنها گراف بدون پل با اندیس رنگی (http://fa.wikipedia.org/w/index.php?title=%D8%A7%D9%86%D8%AF%DB%8C%D8%B3_%D8 %B1%D9%86%DA%AF%DB%8C&action=edit&redlink=1) ۴ می‌باشد. و نهایتا تنها گراف بدون پل با ۱۰ یال است که همیلتنی نیست.
متداول ترین و متقارن ترین شکل گراف پترسن که یک پنج ضلعی با یک ستارهٔ پنج رأس درون آن است که هر یک از رأس‌هایش به رأس‌های پنج ضلعی با یک یال وصل می‌شود ، دارای ۵ نقطه تقاطع می‌باشد(شکل(۱)).این روش ترسیم بهترین روش برای کمینه کردن تعداد تقاطع‌ها نیست. روشی دیگر برای کشیدن گراف پترسن با دو نقطهٔ تقاطع وجود دارد.(شکل(۲)) بنابراین عدد تقاطع (http://fa.wikipedia.org/w/index.php?title=%D8%B9%D8%AF%D8%AF_%D8%AA%D9%82%D8 %A7%D8%B7%D8%B9&action=edit&redlink=1) گراف پترسن ۲ است.
همچنین گراف پترسن می‌تواند به گونه‌ای رسم شود که یال‌ها دارای طول برابر واحد باشند. این نوع ، یک گراف به طول واحد است.(شکل(3))

دور و مسیر همیلتونی

http://pnu-club.com/imported/2011/01/260.jpg (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Petersen4.jpg ) شکل (4)
گراف پترسن به عنوان گراف شبه همیلتونی



گراف پترسن دارای مسیر همیلتونی (http://fa.wikipedia.org/wiki/%D9%85%D8%B3%DB%8C%D8%B1_%D9%87%D9%85%DB%8C%D9%84% D8%AA%D9%88%D9%86%DB%8C) است ولی دور همیلتونی ندارد. همچنان که در بالا ذکر شد این گراف کوچکترین گراف مکعبی بدون پل است که دور همیلتونی ندارد. در نتیجه گراف همیلتونی (http://fa.wikipedia.org/wiki/%DA%AF%D8%B1%D8%A7%D9%81_%D9%87%D9%85%DB%8C%D9%84% D8%AA%D9%88%D9%86%DB%8C) نیست. ولی این گراف ، شبه همیلتونی (http://fa.wikipedia.org/w/index.php?title=%D8%B4%D8%A8%D9%87_%D9%87%D9%85%DB %8C%D9%84%D8%AA%D9%88%D9%86%DB%8C&action=edit&redlink=1) است، بدان معنی که با وجود این که دور همیلتونی ندارد ولی با حذف کردن هر یال آن تبدیل به گراف همیلتونی می‌شود و ضمنا کوچترین گراف شبه همیلتونی نیز می‌باشد.(شکل(۴)) گراف پترسن یکی از ۵ گراف متصل راس-ترایا است که دور همیلتونی ندارد.
رنگ آمیزی
http://pnu-club.com/imported/2011/01/261.jpg (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Petersen5.jpg ) شکل (5)
گراف پترسن با شماره رنگی 3



گراف پترسن دارای شماره رنگی (http://fa.wikipedia.org/w/index.php?title=%D8%B4%D9%85%D8%A7%D8%B1%D9%87_%D8 %B1%D9%86%DA%AF%DB%8C&action=edit&redlink=1) ۳ است. این بدان معنا است که راس‌های آن می‌توانند با ۳ رنگ ،اما نه با ۲، رنگ شوند به طوری که هیچ یالی دو راس همرنگ را متصل نکند.(شکل(۵)) همچنین دارای اندیس رنگی (http://fa.wikipedia.org/w/index.php?title=%D8%A7%D9%86%D8%AF%DB%8C%D8%B3_%D8 %B1%D9%86%DA%AF%DB%8C&action=edit&redlink=1) ۴ می‌باشد که یعنی برای رنگ کردن یال‌ها به ۴ رنگ نیاز داریم.

جدول خصوصیات

در جدول زیر بعضی از خواص این گراف به طور خلاصه آمده‌است:
http://pnu-club.com/imported/2011/01/262.jpg (http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:Petersen7.jpg )


منابع ‎


ویکیپدیای انگلیسی ، دانشنامه آزاد (http://en.wikipedia.org/wiki/Petersen_Graph)

Petersen Graph -- from Wolfram MathWorld (http://mathworld.wolfram.com/PetersenGraph.html)
The Petersen Graph - Eindhoven University of Technology (http://www.win.tue.nl/%7Eaeb/graphs/Petersen.html)

[2khtar]

ممنون میشم در مورد راس و یال ترایا یکم توضیح بدید.

[Borna66]

ممنون میشم در مورد راس و یال ترایا یکم توضیح بدید.
اینم یک توضیح در مورد یال ترایا
نردبان موبیوس نمونه‌ای از گراف‌های چنبره ای (http://fa.wikipedia.org/w/index.php?title=%DA%AF%D8%B1%D8%A7%D9%81_%DA%86%D9 %86%D8%A8%D8%B1%D9%87_%D8%A7%DB%8C&action=edit&redlink=1&preload=%D8%A7%D9%84%DA%AF%D9%88:%D8%A7%DB%8C%D8%A C%D8%A7%D8%AF+%D9%85%D9%82%D8%A7%D9%84%D9%87/%D8%A7%D8%B3%D8%AA%D8%AE%D9%88%D8%A7%D9%86%E2%80%8 C%D8%A8%D9%86%D8%AF%DB%8C&editintro=%D8%A7%D9%84%DA%AF%D9%88:%D8%A7%DB%8C%D8 %AC%D8%A7%D8%AF+%D9%85%D9%82%D8%A7%D9%84%D9%87/%D8%A7%D8%AF%DB%8C%D8%AA%E2%80%8C%D9%86%D9%88%D8%A A%DB%8C%D8%B3&summary=%D8%A7%DB%8C%D8%AC%D8%A7%D8%AF+%DB%8C%DA%A 9+%D9%85%D9%82%D8%A7%D9%84%D9%87+%D9%86%D9%88+%D8% A7%D8%B2+%D8%B7%D8%B1%DB%8C%D9%82+%D8%A7%DB%8C%D8% AC%D8%A7%D8%AF%DA%AF%D8%B1&nosummary=&prefix=&minor=&create=%D8%AF%D8%B1%D8%B3%D8%AA+%DA%A9%D8%B1%D8%AF %D9%86+%D9%85%D9%82%D8%A7%D9%84%D9%87+%D8%AC%D8%AF %DB%8C%D8%AF) است.(Li(2005 قابلیت جا سازی آنها را در سطوح دستهٔ بالاتر کشف کرد. نردبانهای موبیوس رأس-ترایا(vertex-transitive)(به استثناء (M6))هستند نه یال-ترایا(edge-transitive):هر رأس از دوری که نردبان از آن تشکیل شده است، مربوط به یک 4-دور است، در حالی که هر پله مربوط به دو تا از این دورها است. وقتی (Mn، n ≡ 2 (mod 4دو قسمتی (http://fa.wikipedia.org/w/index.php?title=%DA%AF%D8%B1%D8%A7%D9%81_%D8%AF%D9 %88_%D9%82%D8%B3%D9%85%D8%AA%DB%8C&action=edit&redlink=1&preload=%D8%A7%D9%84%DA%AF%D9%88:%D8%A7%DB%8C%D8%A C%D8%A7%D8%AF+%D9%85%D9%82%D8%A7%D9%84%D9%87/%D8%A7%D8%B3%D8%AA%D8%AE%D9%88%D8%A7%D9%86%E2%80%8 C%D8%A8%D9%86%D8%AF%DB%8C&editintro=%D8%A7%D9%84%DA%AF%D9%88:%D8%A7%DB%8C%D8 %AC%D8%A7%D8%AF+%D9%85%D9%82%D8%A7%D9%84%D9%87/%D8%A7%D8%AF%DB%8C%D8%AA%E2%80%8C%D9%86%D9%88%D8%A A%DB%8C%D8%B3&summary=%D8%A7%DB%8C%D8%AC%D8%A7%D8%AF+%DB%8C%DA%A 9+%D9%85%D9%82%D8%A7%D9%84%D9%87+%D9%86%D9%88+%D8% A7%D8%B2+%D8%B7%D8%B1%DB%8C%D9%82+%D8%A7%DB%8C%D8% AC%D8%A7%D8%AF%DA%AF%D8%B1&nosummary=&prefix=&minor=&create=%D8%AF%D8%B1%D8%B3%D8%AA+%DA%A9%D8%B1%D8%AF %D9%86+%D9%85%D9%82%D8%A7%D9%84%D9%87+%D8%AC%D8%AF %DB%8C%D8%AF) است

موفق باشید

روزگار خوش