Проблем со три бунари
Проблем со три бунари, познат и како проблем со три куќи — класична математичка загатка којашто гласи:
Нека се дадени три куќи на рамнина и секоја од нив треба да се поврзе со три бунари како извори на три вида енергија: вода, гас и струја. Дали постои начин да се воспостават сите девет врски без притоа било која од нив да пресекува некоја друга и без да се користи простор со повисока димензија?
Проблемот претставува апстрактна математичка загатка којашто поставува ограничувања кои не постојат во практична инженерска смисла. Тој е дел од математичката област тополошка теорија на графови, која го проучува вметнувањето на графови на површини. Со поформален речник од областа на теоријата на графови, проблемот прашува дали целосниот дводелен граф K3,3 е рамнински.[1] Во однос на проблемот, графот се среќава како „граф на корисност“,[2] а нарекуван е и „Томсенов граф“.[3]
Решение
[уреди | уреди извор]При вообичаената поставеност на проблемот на дводимензионална рамнина, решението на загатката е „не“, односно не постои начин да се воспостават сите девет врски без притоа барем две од нив да не се пресекуваат. Со други зборови, графот K3,3 не е планарен. Во 1930 година, Казимир Куратовски истакнал дека графот K3,3 не е планарен,[4] од каде што следува дека проблемот нема решение. Сепак, Дејвид Кулман изјавил дека „интересно е тоа што Куратовски не објавил детален доказ дека K3,3 е непланарен“.[5]
Поврзано
[уреди | уреди извор]Наводи
[уреди | уреди извор]- ↑ Bóna, Miklós (2011), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, стр. 275–277, ISBN 9789814335232.
- ↑ Utility Graph. mathworld.wolfram.com
- ↑ Coxeter, H. S. M. (1950), „Self-dual configurations and regular graphs“, Bulletin of the American Mathematical Society, 56: 413–455, doi:10.1090/S0002-9904-1950-09407-5, MR 0038078.
- ↑ Kuratowski, Kazimierz (1930), „Sur le problème des courbes gauches en topologie“ (PDF), Fund. Math. (француски), 15: 271–283.
- ↑ Kullman, David (1979), „The Utilities Problem“, Mathematics Magazine, 52 (5): 299–302, JSTOR 2689782.
Надворешни врски
[уреди | уреди извор]- 3 Utilities Puzzle на Cut-the-knot (англиски)
- The Utilities Puzzle — објаснување со решение на Archimedes-lab.org (англиски)
- Loy, Jim, Proof That the Impossible Puzzle is Impossible, Архивирано од изворникот на 20 јануари 2007
- „Utility graph“ од Ерик В. Вајсштајн — MathWorld (англиски)