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

**مسئلهٔ سه روستا** یا **مسئلهٔ برق، آب، گاز (خدمات شهری)**  از رده معماهای ریاضی است.

فرض کنید که سه روستا در یک سطح (صفحه) یا یک کره قرار دارند و هر کدام مجبورند که به شرکت‌های آب، برق و گاز وصل شوند. استفاده از سه بعد یا رفتن به درون روستاها یا شرکت‌ها خلاف مقررات مسئله‌است. آیا راه حلی برای حل این مسئله بدون قطع کردن خطوط وجود دارد؟
پرونده:آب.JPG
## تاریخچه
مبدأ مسئلهٔ ذیل به‌عنوان مثالی از: «گراف دو قسمتی «k_{3,3}» نامعلوم است گفته میشود شیخ بهاالدین محمد (شیخ بهایی) دانشمند و ریاضی دان ایرانی این مسئله را به گونه 3 خانه و 3 چاه مطرح کرد که به نوعی گراف اولیه شناخته میشد اما می‌دانیم به طور رسمی در سال ۱۲۹۲ (۱۹۱۳ میلادی) همین سوال به شکل دیگری توسط *«هنری ارنست دودنی»* (Henry Ernest Dudeney) بدین‌شکل مطرح شد: «مسئلهٔ گیج‌کننده عبارت است از: استقرار تجهیزات آب، گاز و برق بدون آن‌که هیچ لوله یا خطی با دیگری تقاطع داشته باشد».

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

*Kazimierz Kuratowski* در سال ۱۹۳۰ ثابت کرد که k_{3,3} مسطح نیست و بنابراین این مسئله هیچ جوابی ندارد.این جواب می‌تواند شاهدی بر نتیجهٔ قضیه خم جردن Jordan curve theorem باشد. حکم کاملی که دربارهٔ گراف‌های مسطحه در *Kuratowski reduction theorem* آمده شامل این نتیجه می‌شود.

k_{3,3} حلقه شکل است یعنی در اینجا با سوراخ کردن صفحه (یا کره) می‌توان مسئله را حل کرد، این ویژگی‌های توپولوژیک مسئله را تغییر می‌دهد.
## اثبات
بندانگشتی
یک اثبات ساده این مسئله به صورت زیر است:

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

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

## منابع

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

* Chartrand, G. «The Three Houses and Three Utilities Problem: An Introduction to Planar Graphs.» §۹٫۱ in Introductory Graph Theory. New York: Dover, pp. ۱۹۱-۲۰۲، ۱۹۸۵.
* Coxeter, H. S. M. «Self-Dual Configurations and Regular Graphs.» Bull. Amer. Math. Soc. ۵۶، ۴۱۳-۴۵۵، ۱۹۵۰.
* Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. ۹۲-۹۴، ۱۹۸۴.
* Ore, Ø. Graphs and Their Uses. New York: Random House, pp. ۱۴-۱۷، ۱۹۶۳.
* Royle, G. «F۰۰۶A.» http://www.csse.uwa.edu.au/~gordon/foster/F006A.html.
* Pappas, T. «Wood, Water, Grain Problem.» The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. ۱۷۵ and ۲۳۳، ۱۹۸۹.
* Steinhaus, H. Mathematical Snapshots, ۳rd ed. New York: Dover, pp. ۲۶۲-۲۶۳، ۱۹۹۹.

## پیوند به بیرون
* مسئله تسهیلات

رده:مسئله‌های ریاضی
رده:معماها
رده:معماهای ریاضی
رده:معماهای غیرقابل‌حل
رده:نظریه گراف توپولوژیکی
رده:نظریه گراف