گراف همیلتونی

در تئوری گراف ها یک مسیر همیلتونی در یک گراف بدون جهت یک مسیر است که از هر راس فقط یک بار گذشته باشد.و یک دور همیلتونی در یک گراف ساده بدون جهت یک دور است که از هر راس فقط یک بار عبور می‌کند و به راس اول باز می‌گردد و محاسبه این که یک گراف دارای مسیر یا دور همیلتونی است از مسائل NP-complete است.مسیر و دور همیلتونی بعد از William Rowan Hamilton کسی که بازی Icosiam را اختراع کرد نامگذاری شد و البته امروزه با نام پازل همیلتون هم شناخته می‌شود و شامل پیدا کردن یک دور همیلتونی در یک دوازده وجهی بود که همیلتون این مسئله را حل کرد ولی متاسفانه روش او برای تمام گراف ها تعمیم نمی‌یابد.

ادامه نوشته

بازی مکعب ها

بازی مكعب هاي رنگي با چهار مکعب انجام می گیرد.ابتدا وجه های مکعب هارا رنگ می کنیم.دررنگ آمیزی وجه های هر مکعب، تمام رنگ های قرمز(R)،سفید(w)،آبی(B)،زرد(Y)،به کار رفته اند.مامی توانیم این چهارمکعب را به صورت های مختلفی رنگ آمیزی کنیم،که در این جا برای نمونه، شکل 1 را آورده ايم .

ادامه نوشته

اقای پترسن (مبدع نوعی گراف)

اسکار پترسن درگذشت

اسکار پترسون (Oscar Peterson) درگذشت. مرگ این نوازنده‌ی نامدار پیانو دوستداران سبک موسیقی جــَــز در سرتاسر جهان را غمگین ساخت. پترسون، اهل کانادا، در هنگام مرگ ۸۲ ساله بود. شهرت او در دهه ۱۹۵۰ آغاز شد. او که به تکنیک نوازندگی تسلطی استثنايی داشت، می‌توانست با پیانو دیالوگ‌های جانداری را پیش برد.

گراف پترسن

در نظریه گراف ، گراف پترسن گرافی غیر جهت دار ، با ۱۰ راس و ۱۵ یال است. این گراف ، گرافی کوچک می‌باشد که به عنوان مثالی مفید و همچنین مثال نقض در بسیاری از مسائل نظریه گراف به کار می‌رود.
جولیوس پترسن(۱۸۳۹-۱۹۱۰) دانشمندی دانمارکی بود که در سال ۱۸۹۸ گرافی را ، که به نام خودش ثبت شد، به عنوان کوچکترین گراف مکعبی (گرافی که هر راس آن از درجه ۳ باشد.) بدون پل ساخت. در واقع این گراف مثال نقضی برای این ادعا بود که یک گراف مکعبی بدون پل متصل ، داری یک رنگ آمیزی یالی با ۳ رنگ است. در حالی که این گراف دارای این رنگ آمیزی با ۴ رنگ می‌باشد. با این که این گراف به طور عمومی به جولیوس پترسن نسبت داده می‌شود ، ولی درحقیقت برای اولین بار ۱۲ سال زودتر از ساختن آن توسط وی ، در سال ۱۸۸۶ به وجود آمده بود.
دونالد نوث اذعان می‌کند که گراف پترسن ، شکل و پیکری قابل توجه‌است که به عنوان مثالی نقض برای بسیاری از اسناد و اثبات‌های خوش بینانه درباره این که چه چیزهایی ممکن است به طور عمومی برای گراف‌ها درست باشد ، به کار می‌رود.

ادامه نوشته