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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مساله‌ی سه روستا یا مساله‌ی برق، آب، گاز (خدمات شهری) (به انگلیسی: Water, gas, and electricity) از رده معماهای ریاضی است.

فرض کنید که سه روستا در یک سطح (صفحه) یا یک کره قرار دارند و هر کدام مجبورند که به شرکتهای آب، برق و گاز وصل شوند. استفاده از سه بعد یا رفتن به درون روستاها و یا شرکت‌ها خلاف مقررات مساله‌است. آیا راه حلی برای حل این مساله بدون قطع کردن خطوط وجود دارد؟ آب.JPG

تاریخچه[ویرایش]

مبدأ مسألهٔ ذیل به‌عنوان مثالی از: «گراف دو قسمتی «k_{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} حلقه شکل است یعنی در اینجا با سوراخ کردن صفحه (یا کره) می‌توان مساله را حل کرد، این ویژگی‌های توپولوژیک مساله را تغییر می‌دهد.

اثبات[ویرایش]

Complete bipartite graph K3,3.svg

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

گرافی که از رئوس 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. ۲۶۲-۲۶۳, ۱۹۹۹.