مسئله سه روستا

مبدأ مسئلهٔ ذیل به‌عنوان مثالی از: «گراف دو قسمتی «${\displaystyle k_{3,3}}$

این مسئله بخشی از topological graph theory است که به مطالعه مباحث تعبیه گراف روی صفحات می‌پردازد. اگر بخواهیم کمی اصولی تر حرف بزنیم، این مسئله دربارهٔ اینکه آیا یگ گراف دو بخشی با ۶ راس (${\displaystyle k_{3,3}}$

Kazimierz Kuratowski در سال ۱۹۳۰ ثابت کرد که ${\displaystyle k_{3,3}}$

${\displaystyle k_{3,3}}$

یک اثبات ساده این مسئله به صورت زیر است:

گرافی که از رئوس X-Y-Z-A-B-C تشکیل شده‌است را در نظر بگیرید.که در آن باید یال هایX-A,Y-B,Z-C باید حضور داشته باشند.حالا برای هر یال تصمیم می‌گیریم که ان را داخل یا خارج گراف دایره‌ای بکشیم. اما حتماً باید برای دو تا از یال‌ها انتخاب یکسانی داشته باشیم. چون دو خط نمی‌توانند در یک طرف بدون تقاطع کشیده شوند، گراف مسطح نیست.

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

• مسئله تسهیلات

• Weisstein, Eric W. «Utility Graph.» From MathWorld—A Wolfram Web Resource.
• ریاضیات گسسته – ترجمه اردوان میرزائی
• ریاضیات گسسته - سیمور لیپ شوتز