در نظریه گراف ، گراف پترسن گرافی غیر جهت دار، با ۱۰ راس و ۱۵ یال است. این گراف، گرافی کوچک می باشد که به عنوان مثالی مفید و همچنین مثال نقض در بسیاری از مسائل نظریه گراف به کار می رود. یولیوس پترسن[ ۱] ( ۱۸۳۹ - ۱۹۱۰ ) دانشمندی دانمارکی بود که در سال ۱۸۹۸ گرافی را، که به نام خودش ثبت شد، به عنوان کوچکترین گراف مکعبی ( گرافی که هر راس آن از درجه ۳ باشد. ) بدون پل ساخت. در واقع این گراف مثال نقضی برای این ادعا بود که یک گراف مکعبی بدون پل متصل، داری یک رنگ آمیزی یالی با ۳ رنگ است. در حالی که این گراف دارای این رنگ آمیزی با ۴ رنگ می باشد. با این که این گراف به طور عمومی به یولیوس پترسن نسبت داده می شود، ولی درحقیقت برای اولین بار ۱۲ سال زودتر از ساختن آن توسط وی، در سال ۱۸۸۶ به وجود آمده بود. دونالد نوث[ ۲] اذعان می کند که گراف پترسن، شکل و پیکری قابل توجه است که به عنوان مثالی نقض برای بسیاری از اسناد و اثبات های خوش بینانه دربارهٔ این که چه چیزهایی ممکن است به طور عمومی برای گراف ها درست باشد، به کار می رود.
گراف پترسن، گراف مکمل برای گراف خط، K۵ است. همچنین گراف کنسر KG۵٬۲ هم می باشد. این بدان معنا است که اگر برای هر کدام از زیرمجموعه های دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعه های نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته می شود. گراف پترسن، گرافی غیر مسطح است. هر گراف غیر مسطح زیر گرافی دارد که با گراف کامل K۵ یا گراف دو بخشی کامل K۳٬۳ هم ریخت یا هومئومورف است. حال آن که پترسن با هر دو گراف هم ریخت می باشد.
دقیقاً ۱۹ گراف مکعبی متصل با ۱۰ یال وجود دارد. گراف پترسن یکی از همین ۱۹ گراف می باشد. این گراف تنها گرافی با ۱۰ یال از این دسته است که دارای قطر برابر ۲ و تنها گراف بدون پل با اندیس رنگی ۴ می باشد. و نهایتاً تنها گراف بدون پل با ۱۰ یال است که همیلتنی نیست. متداول ترین و متقارن ترین شکل گراف پترسن که یک پنج ضلعی با یک ستارهٔ پنج رأس درون آن است که هر یک از رأس هایش به رأس های پنج ضلعی با یک یال وصل می شود، دارای ۵ نقطه تقاطع می باشد ( شکل ( ۱ ) ) . این روش ترسیم بهترین روش برای کمینه کردن تعداد تقاطع ها نیست. روشی دیگر برای کشیدن گراف پترسن با دو نقطهٔ تقاطع وجود دارد. ( شکل ( ۲ ) ) بنابراین عدد تقاطع گراف پترسن ۲ است. همچنین گراف پترسن می تواند به گونه ای رسم شود که یال ها دارای طول برابر واحد باشند. این نوع، یک گراف به طول واحد است. ( شکل ( 3 ) )
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفگراف پترسن، گراف مکمل برای گراف خط، K۵ است. همچنین گراف کنسر KG۵٬۲ هم می باشد. این بدان معنا است که اگر برای هر کدام از زیرمجموعه های دو عضوی یک مجموعهٔ ۵ عضوی یک رأس در نظر بگیریم و بین هر دو رأسی که زیرمجموعه های نظیرشان ناسازگار باشند یک یال وصل کنیم، گراف پترسن ساخته می شود. گراف پترسن، گرافی غیر مسطح است. هر گراف غیر مسطح زیر گرافی دارد که با گراف کامل K۵ یا گراف دو بخشی کامل K۳٬۳ هم ریخت یا هومئومورف است. حال آن که پترسن با هر دو گراف هم ریخت می باشد.
دقیقاً ۱۹ گراف مکعبی متصل با ۱۰ یال وجود دارد. گراف پترسن یکی از همین ۱۹ گراف می باشد. این گراف تنها گرافی با ۱۰ یال از این دسته است که دارای قطر برابر ۲ و تنها گراف بدون پل با اندیس رنگی ۴ می باشد. و نهایتاً تنها گراف بدون پل با ۱۰ یال است که همیلتنی نیست. متداول ترین و متقارن ترین شکل گراف پترسن که یک پنج ضلعی با یک ستارهٔ پنج رأس درون آن است که هر یک از رأس هایش به رأس های پنج ضلعی با یک یال وصل می شود، دارای ۵ نقطه تقاطع می باشد ( شکل ( ۱ ) ) . این روش ترسیم بهترین روش برای کمینه کردن تعداد تقاطع ها نیست. روشی دیگر برای کشیدن گراف پترسن با دو نقطهٔ تقاطع وجود دارد. ( شکل ( ۲ ) ) بنابراین عدد تقاطع گراف پترسن ۲ است. همچنین گراف پترسن می تواند به گونه ای رسم شود که یال ها دارای طول برابر واحد باشند. این نوع، یک گراف به طول واحد است. ( شکل ( 3 ) )
wiki: گراف پترسن