مسئلهٔ سه روستا یا مسئلهٔ برق، آب، گاز ( خدمات شهری ) ( به انگلیسی: Water, gas, and electricity ) از رده معماهای ریاضی است.
فرض کنید که سه روستا در یک سطح ( صفحه ) یا یک کره قرار دارند و هر کدام مجبورند که به شرکت های آب، برق و گاز وصل شوند. استفاده از سه بعد یا رفتن به درون روستاها یا شرکت ها خلاف مقررات مسئله است. آیا راه حلی برای حل این مسئله بدون قطع کردن خطوط وجود دارد؟
مبدأ مسئلهٔ ذیل به عنوان مثالی از: «گراف دو قسمتی « k 3 , 3 » نامعلوم است اما می دانیم اولین بار در سال ۱۲۹۲ ( ۱۹۱۳ میلادی ) توسط «هنری ارنست دودنی» ( Henry Ernest Dudeney ) بدین شکل مطرح شد: «مسئلهٔ گیج کننده عبارت است از: استقرار تجهیزات آب، گاز و برق بدون آن که هیچ لوله یا خطی با دیگری تقاطع داشته باشد».
این مسئله بخشی از topological graph theory است که به مطالعه مباحث تعبیه گراف روی صفحات می پردازد. اگر بخواهیم کمی اصولی تر حرف بزنیم، این مسئله دربارهٔ اینکه آیا یگ گراف دو بخشی با ۶ راس ( k 3 , 3 ) مسطح است یا خیر. این گراف معادل با گراف دایره ای ( C i 6 ( 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 باید حضور داشته باشند. حالا برای هر یال تصمیم می گیریم که ان را داخل یا خارج گراف دایره ای بکشیم. اما حتماً باید برای دو تا از یال ها انتخاب یکسانی داشته باشیم. چون دو خط نمی توانند در یک طرف بدون تقاطع کشیده شوند، گراف مسطح نیست.
هیچ فردی نمی تواند یک گراف که از دسته صفر نیست را در صفحه بدون تقاطع یال ها بکشد. در طراحی مدارات الکتریکی وقتی که تمام مدارات به یک طرف برد محدود می شوند طراحی تمام مداراتی که شبیه به یک گراف غیر مسطح هستند غیرممکن می شود. تنها در مواردی که می توان در سه بعد کار کرد یا از طرف دیگر برد استفاده کرد طراحی این مدارات امکان پذیر می باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلففرض کنید که سه روستا در یک سطح ( صفحه ) یا یک کره قرار دارند و هر کدام مجبورند که به شرکت های آب، برق و گاز وصل شوند. استفاده از سه بعد یا رفتن به درون روستاها یا شرکت ها خلاف مقررات مسئله است. آیا راه حلی برای حل این مسئله بدون قطع کردن خطوط وجود دارد؟
مبدأ مسئلهٔ ذیل به عنوان مثالی از: «گراف دو قسمتی « k 3 , 3 » نامعلوم است اما می دانیم اولین بار در سال ۱۲۹۲ ( ۱۹۱۳ میلادی ) توسط «هنری ارنست دودنی» ( Henry Ernest Dudeney ) بدین شکل مطرح شد: «مسئلهٔ گیج کننده عبارت است از: استقرار تجهیزات آب، گاز و برق بدون آن که هیچ لوله یا خطی با دیگری تقاطع داشته باشد».
این مسئله بخشی از topological graph theory است که به مطالعه مباحث تعبیه گراف روی صفحات می پردازد. اگر بخواهیم کمی اصولی تر حرف بزنیم، این مسئله دربارهٔ اینکه آیا یگ گراف دو بخشی با ۶ راس ( k 3 , 3 ) مسطح است یا خیر. این گراف معادل با گراف دایره ای ( C i 6 ( 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 باید حضور داشته باشند. حالا برای هر یال تصمیم می گیریم که ان را داخل یا خارج گراف دایره ای بکشیم. اما حتماً باید برای دو تا از یال ها انتخاب یکسانی داشته باشیم. چون دو خط نمی توانند در یک طرف بدون تقاطع کشیده شوند، گراف مسطح نیست.
هیچ فردی نمی تواند یک گراف که از دسته صفر نیست را در صفحه بدون تقاطع یال ها بکشد. در طراحی مدارات الکتریکی وقتی که تمام مدارات به یک طرف برد محدود می شوند طراحی تمام مداراتی که شبیه به یک گراف غیر مسطح هستند غیرممکن می شود. تنها در مواردی که می توان در سه بعد کار کرد یا از طرف دیگر برد استفاده کرد طراحی این مدارات امکان پذیر می باشد.
wiki: مسئله سه روستا