Three utilities problem (original) (raw)
مسألة غاز، ماء، كهرباء هي أحد الأحاجي الرياضية المعروفة أو مسألة الخدمات الثلاثة أو مسألة الأكواخ الثلاثة تنص على مايلي: لنفترض وجود ثلاث أكواخ في مستوي (أو على سطح كرة) كل منها يحتاج أن يزود بخطوط وأنابيب الغاز، الماء، والكهرباء. من غير الممكن استخدام البعد الثالث أو تقاطع أي خطين. هل هناك أي طريقة للتوصيل بدون أي يتقاطع أي من الخطوط؟.
| Property | Value |
|---|---|
| dbo:abstract | مسألة غاز، ماء، كهرباء هي أحد الأحاجي الرياضية المعروفة أو مسألة الخدمات الثلاثة أو مسألة الأكواخ الثلاثة تنص على مايلي: لنفترض وجود ثلاث أكواخ في مستوي (أو على سطح كرة) كل منها يحتاج أن يزود بخطوط وأنابيب الغاز، الماء، والكهرباء. من غير الممكن استخدام البعد الثالث أو تقاطع أي خطين. هل هناك أي طريقة للتوصيل بدون أي يتقاطع أي من الخطوط؟. (ar) Tři domy a tři studně je hlavolam z oboru rekreační matematiky a zároveň úloha z teorie grafů. (cs) Se conoce como el problema de los tres servicios a un problema matemático clásico que consiste en proporcionar tres servicios: agua, electricidad y gas, a tres casas. Para ello hay que conectar cada uno de los servicios a cada casa con una línea que representa la cañería o los cables. Debemos dar todos los servicios a todas las casas sin que las líneas de conexión se crucen. (es) L'énigme des trois maisons, aussi appelée l'énigme de l'eau, du gaz et de l'électricité, est un jeu mathématique dont l'analyse utilise un théorème de topologie ou de théorie des graphes. Ce problème n'a pas de solution. Georges Perec le cite en 1978 dans son livre Je me souviens : « Je me souviens des heures que j'ai passées, en classe de troisième, je crois, à essayer d'alimenter en eau, gaz et électricité, trois maisons, sans que les tuyaux se croisent (il n'y a pas de solution tant que l'on reste dans un espace à deux dimensions ; c'est l'un des exemples élémentaires de la topologie, comme les ponts de Königsberg, ou le coloriage des cartes) ». Cette énigme est déjà posée par Henry Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu'« il existe une demi-douzaine d'énigmes vieilles comme le monde, qui réapparaissent perpétuellement ». Celle de l'article en est une, qu'il appelle eau, gaz, et électricité. Elle est popularisée par Martin Gardner, qui la présente dans son Sixième livre de jeux mathématiques. Il existe deux approches pour démontrer l'inexistence d'une solution connectant chacune des trois maison directement aux trois fournisseurs. La première approche montrant l'impossibilité utilise le théorème de Jordan, indiquant que si l'on dessine une boucle dans un plan, le complémentaire de la boucle, c'est-à-dire la partie non dessinée du plan, se compose de deux connexes par arcs, l'un borné (l'intérieur de la boucle) et l'autre non (l'extérieur de la boucle). La seconde approche, plus générale, utilise la formule d'Euler pour les graphes planaires. Elle est une étape dans la démonstration du théorème clé des graphes planaires, due à Kazimierz Kuratowski. (fr) The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved. This puzzle can be formalized as a problem in topological graph theory by asking whether the complete bipartite graph , with vertices representing the houses and utilities and edges representing their connections, has a graph embedding in the plane. The impossibility of the puzzle corresponds to the fact that is not a planar graph. Multiple proofs of this impossibility are known, and form part of the proof of Kuratowski's theorem characterizing planar graphs by two forbidden subgraphs, one of which is . The question of minimizing the number of crossings in drawings of complete bipartite graphs is known as Turán's brick factory problem, and for the minimum number of crossings is one. is a graph with six vertices and nine edges, often referred to as the utility graph in reference to the problem. It has also been called the Thomsen graph after 19th-century chemist Julius Thomsen. It is a well-covered graph, the smallest triangle-free cubic graph, and the smallest non-planar minimally rigid graph. (en) In topologia e teoria dei grafi, il problema dei servizi affronta questioni che si richiamano al classico quesito: Apparentemente di immediata soluzione, il problema delle tre case e dei tre pozzi fa sorridere gli ingenui, ma fa pensare i matematici. La soluzione è possibile soltanto se i tre soggetti sono disposti a costruire un cavalcavia in modo che almeno uno di loro vi passi sotto ed un altro vi passi sopra. Il primo matematico a affrontare e risolvere esaustivamente questo problema è stato Fermat, nel 1643, che ne pubblicò la soluzione trovata accidentalmente durante uno studio sulla dei grandi numeri. (it) Задача о трёх домиках и трёх колодцах — классическая математическая головоломка: проложить от каждого из трёх колодцев к каждому из трёх домиков непересекающиеся тропинки. Формулировка задачи приписывается Эйлеру. В современной литературе иногда встречается в следующей форме: возможно ли к каждому из трёх домиков проложить без пересечений на плоскости трубы (рукава) от трёх источников — электроснабжения, газоснабжения и водоснабжения («вода, газ, электричество»). Головоломка не имеет решения: топологическая теория графов, изучающая вложение графов в поверхности, даёт отрицательный ответ на вопрос о возможности изобразить соответствующий граф на плоскости без пересечений рёбер. Полный двудольный граф , представляющий задачу, называют «домики и колодцы», «коммунальный граф» (англ. utility graph), граф Томсена. (ru) Domki i studnie – zagadka matematyczna, której współczesna wersja może mieć następujące brzmienie: Na kartce (płaszczyźnie) są 3 domki i 3 firmy (doprowadzające wodę, prąd i gaz). Bez użycia trzeciego wymiaru i bez przechodzenia przez domki ani przez firmy, doprowadź wodę, prąd i gaz do każdego domku, tak aby linie się nie przecięły. Marta Bilska, Korepetycje z Martą Formalnie łamigłówka odpowiada na pytanie czy pełny graf dwudzielny jest płaski. (pl) O chamado problema das três casas, conhecido também como água, gás e eletricidade ou problema das três utilidades, é um clássico, que pode ser declarado como segue: Suponha que haja três casas em um plano (ou superfície de uma esfera) e cada uma precisa ser ligada às empresas de gás, água e eletricidade. O uso de uma terceira dimensão ou o envio de qualquer uma das conexões através de outra empresa ou casa não é permitido. Existe uma maneira de fazer todos os nove ligações sem qualquer uma das linhas que se cruzam? O problema é um quebra-cabeça matemático abstrato que impõe restrições que não existiriam em uma situação prática de engenharia. (pt) 三間小屋問題（three cottages problem）也稱為水、天然氣及電力問題（water, gas and electricity）或Three utilities problem，是經典的數學謎題，描述如下： 假設在平面上（或是在球面上）有三間小屋，要連接到天然氣公司、水廠以及電力公司。若不考慮使用立體架構，也不透過任何小屋或是其他公共設備來傳送資源，是否可以用九條線連結三間小屋及三間公共設備，而且九條線完全沒有交錯？ 三間小屋問題無解，無法在平面上畫出讓這些連接線不交錯的圖形。 三間小屋問題是抽象數學問題，是數學領域中的問題，拓扑图论是研究曲面上图的嵌入。若用正式的圖論術語，此問題在問完全二分图K3,3是否是平面图，可以讓中間的線沒有交叉。此圖形也常稱為utility graph，也稱為湯瑪森圖（Thomsen graph）。 (zh) «Вода, газ та електрика» («задача про три ресурси» або «задача про три котеджі») — класична математична головоломка, яка може бути сформульована таким чином: Нехай є три котеджі на площині (або сфері) і до кожного потрібно підвести газ, воду і електрику. Використовувати третій вимір не дозволяється (тобто все відбувається тільки в площині), як і не дозволяється використовувати подачу ресурсу з іншого котеджу. Чи можливо здійснити ці дев'ять підключень без схрещування підвідних шляхів? Завдання ставиться як абстрактне і не має відношення до реальних інженерних мереж. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/3_utilities_problem_plane.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.archimedes-lab.org/How_to_Solve/Water_gas.html http://www.cut-the-knot.org/do_you_know/3Utilities.shtml |
| dbo:wikiPageID | 58862 (xsd:integer) |
| dbo:wikiPageLength | 25206 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1104252447 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pál_Turán dbr:Sam_Loyd dbr:Minor_(graph_theory) dbr:Benzene dbr:Archimedes-lab.org dbr:Jordan_curve_theorem dbr:Rigid_transformation dbr:Cubic_graph dbr:Kuratowski's_theorem dbr:List_of_impossible_puzzles dbr:Numberlink dbc:Unsolvable_puzzles dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Crossing_number_(graph_theory) dbr:Maximal_independent_set dbr:Chemical_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_minor dbr:Möbius_strip dbr:File:3_utilities_problem_plane.svg dbr:Cage_(graph_theory) dbr:Embedding dbr:Plane_(geometry) dbr:Surface_(topology) dbr:The_Strand_Magazine dbr:Mathematical_puzzle dbr:Torus dbr:Town_gas dbr:Triangle-free_graph dbr:Well-covered_graph dbr:K-vertex-connected_graph dbr:Laman_graph dbr:Almost_all dbr:Cut-the-knot dbc:Mathematical_puzzles dbr:Graph_embedding dbr:Graph_theory dbr:Structural_rigidity dbr:Hans_Peter_Jørgen_Julius_Thomsen dbr:Henry_Dudeney dbc:Topological_graph_theory dbr:Kazimierz_Kuratowski dbr:Bipartite_graph dbr:Toroidal_graph dbr:Planar_graph dbr:Euler_characteristic dbr:Topological_graph_theory dbr:Wagner's_theorem dbr:Turán's_brick_factory_problem dbr:Electric_lighting dbr:Rigid_system dbr:Bridgeless_graph dbr:Polynomial_equation dbr:Coffee_mug dbr:Spanning_subgraph dbr:File:3_utilities_problem_proof.svg dbr:File:K33_one_crossing.svg |
| dbp:authorlink | Henry Dudeney (en) |
| dbp:caption | Solution on a Möbius strip (en) Solution on a torus (en) |
| dbp:first | Henry (en) |
| dbp:footer | Two views of the utility graph, also known as the Thomsen graph or (en) |
| dbp:id | UtilityGraph (en) |
| dbp:image | 3 (xsd:integer) Complex polygon 2-4-3-bipartite graph.png (en) Graph K3-3.svg (en) |
| dbp:last | Dudeney (en) |
| dbp:mode | cs2 (en) |
| dbp:title | Utility graph (en) |
| dbp:totalWidth | 360 (xsd:integer) 480 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Clear dbt:Good_article dbt:Harvtxt dbt:MathWorld dbt:Multiple_image dbt:Quotation dbt:R dbt:Redirect dbt:Reflist dbt:Short_description dbt:Harvs |
| dbp:year | 1917 (xsd:integer) |
| dct:subject | dbc:Unsolvable_puzzles dbc:Mathematical_puzzles dbc:Topological_graph_theory |
| gold:hypernym | dbr:Cottages |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:WikicatIndividualGraphs dbo:Building yago:VisualCommunication106873252 yago:WikicatRegularGraphs |
| rdfs:comment | مسألة غاز، ماء، كهرباء هي أحد الأحاجي الرياضية المعروفة أو مسألة الخدمات الثلاثة أو مسألة الأكواخ الثلاثة تنص على مايلي: لنفترض وجود ثلاث أكواخ في مستوي (أو على سطح كرة) كل منها يحتاج أن يزود بخطوط وأنابيب الغاز، الماء، والكهرباء. من غير الممكن استخدام البعد الثالث أو تقاطع أي خطين. هل هناك أي طريقة للتوصيل بدون أي يتقاطع أي من الخطوط؟. (ar) Tři domy a tři studně je hlavolam z oboru rekreační matematiky a zároveň úloha z teorie grafů. (cs) Se conoce como el problema de los tres servicios a un problema matemático clásico que consiste en proporcionar tres servicios: agua, electricidad y gas, a tres casas. Para ello hay que conectar cada uno de los servicios a cada casa con una línea que representa la cañería o los cables. Debemos dar todos los servicios a todas las casas sin que las líneas de conexión se crucen. (es) Domki i studnie – zagadka matematyczna, której współczesna wersja może mieć następujące brzmienie: Na kartce (płaszczyźnie) są 3 domki i 3 firmy (doprowadzające wodę, prąd i gaz). Bez użycia trzeciego wymiaru i bez przechodzenia przez domki ani przez firmy, doprowadź wodę, prąd i gaz do każdego domku, tak aby linie się nie przecięły. Marta Bilska, Korepetycje z Martą Formalnie łamigłówka odpowiada na pytanie czy pełny graf dwudzielny jest płaski. (pl) 三間小屋問題（three cottages problem）也稱為水、天然氣及電力問題（water, gas and electricity）或Three utilities problem，是經典的數學謎題，描述如下： 假設在平面上（或是在球面上）有三間小屋，要連接到天然氣公司、水廠以及電力公司。若不考慮使用立體架構，也不透過任何小屋或是其他公共設備來傳送資源，是否可以用九條線連結三間小屋及三間公共設備，而且九條線完全沒有交錯？ 三間小屋問題無解，無法在平面上畫出讓這些連接線不交錯的圖形。 三間小屋問題是抽象數學問題，是數學領域中的問題，拓扑图论是研究曲面上图的嵌入。若用正式的圖論術語，此問題在問完全二分图K3,3是否是平面图，可以讓中間的線沒有交叉。此圖形也常稱為utility graph，也稱為湯瑪森圖（Thomsen graph）。 (zh) «Вода, газ та електрика» («задача про три ресурси» або «задача про три котеджі») — класична математична головоломка, яка може бути сформульована таким чином: Нехай є три котеджі на площині (або сфері) і до кожного потрібно підвести газ, воду і електрику. Використовувати третій вимір не дозволяється (тобто все відбувається тільки в площині), як і не дозволяється використовувати подачу ресурсу з іншого котеджу. Чи можливо здійснити ці дев'ять підключень без схрещування підвідних шляхів? Завдання ставиться як абстрактне і не має відношення до реальних інженерних мереж. (uk) L'énigme des trois maisons, aussi appelée l'énigme de l'eau, du gaz et de l'électricité, est un jeu mathématique dont l'analyse utilise un théorème de topologie ou de théorie des graphes. Ce problème n'a pas de solution. Georges Perec le cite en 1978 dans son livre Je me souviens : « Je me souviens des heures que j'ai passées, en classe de troisième, je crois, à essayer d'alimenter en eau, gaz et électricité, trois maisons, sans que les tuyaux se croisent (il n'y a pas de solution tant que l'on reste dans un espace à deux dimensions ; c'est l'un des exemples élémentaires de la topologie, comme les ponts de Königsberg, ou le coloriage des cartes) ». (fr) The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved. (en) In topologia e teoria dei grafi, il problema dei servizi affronta questioni che si richiamano al classico quesito: Apparentemente di immediata soluzione, il problema delle tre case e dei tre pozzi fa sorridere gli ingenui, ma fa pensare i matematici. La soluzione è possibile soltanto se i tre soggetti sono disposti a costruire un cavalcavia in modo che almeno uno di loro vi passi sotto ed un altro vi passi sopra. (it) O chamado problema das três casas, conhecido também como água, gás e eletricidade ou problema das três utilidades, é um clássico, que pode ser declarado como segue: Suponha que haja três casas em um plano (ou superfície de uma esfera) e cada uma precisa ser ligada às empresas de gás, água e eletricidade. O uso de uma terceira dimensão ou o envio de qualquer uma das conexões através de outra empresa ou casa não é permitido. Existe uma maneira de fazer todos os nove ligações sem qualquer uma das linhas que se cruzam? (pt) Задача о трёх домиках и трёх колодцах — классическая математическая головоломка: проложить от каждого из трёх колодцев к каждому из трёх домиков непересекающиеся тропинки. Формулировка задачи приписывается Эйлеру. В современной литературе иногда встречается в следующей форме: возможно ли к каждому из трёх домиков проложить без пересечений на плоскости трубы (рукава) от трёх источников — электроснабжения, газоснабжения и водоснабжения («вода, газ, электричество»). (ru) |
| rdfs:label | مسألة الخدمات الثلاثة (ar) Tři domy a tři studně (cs) Problema de los tres servicios (es) Énigme des trois maisons (fr) Problema dei servizi (it) Problema das três casas (pt) Domki i studnie (pl) Three utilities problem (en) Домики и колодцы (ru) Вода, газ та електрика (uk) 三間小屋問題 (zh) |
| owl:sameAs | freebase:Three utilities problem yago-res:Three utilities problem wikidata:Three utilities problem dbpedia-ar:Three utilities problem dbpedia-cs:Three utilities problem dbpedia-es:Three utilities problem dbpedia-fa:Three utilities problem dbpedia-fr:Three utilities problem dbpedia-hu:Three utilities problem http://hy.dbpedia.org/resource/Ջուր,_գազ_և_էլեկտրականություն dbpedia-it:Three utilities problem dbpedia-mk:Three utilities problem dbpedia-pl:Three utilities problem dbpedia-pt:Three utilities problem dbpedia-ru:Three utilities problem dbpedia-th:Three utilities problem dbpedia-uk:Three utilities problem dbpedia-zh:Three utilities problem https://global.dbpedia.org/id/32ydg |
| prov:wasDerivedFrom | wikipedia-en:Three_utilities_problem?oldid=1104252447&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/3_utilities_problem_moebius.svg wiki-commons:Special:FilePath/3_utilities_problem_plane.svg wiki-commons:Special:FilePath/3_utilities_problem_proof.svg wiki-commons:Special:FilePath/3_utilities_problem_torus.svg wiki-commons:Special:FilePath/Complex_polygon_2-4-3-bipartite_graph.png wiki-commons:Special:FilePath/Graph_K3-3.svg wiki-commons:Special:FilePath/K33_one_crossing.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Three_utilities_problem |
| is dbo:knownFor of | dbr:Hans_Peter_Jørgen_Julius_Thomsen |
| is dbo:wikiPageRedirects of | dbr:Utility_graph dbr:Thomsen_graph dbr:Electricity,_gas,_and_water dbr:Electricity,_gas,_water dbr:Electricity,_water,_and_gas dbr:Electricity,_water,_gas dbr:Electricity_gas_and_water dbr:Electricity_gas_water dbr:Electricity_water_and_gas dbr:Electricity_water_gas dbr:Water,_gas,_&_electricity dbr:Water,_gas,_and_electricity dbr:Water_gas_and_electricity dbr:Water,_electricity,_and_gas dbr:Water,_electricity,_gas dbr:Water,_gas,_electricity dbr:Water,_gas_and_electricity dbr:Water_electricity_and_gas dbr:Water_electricity_gas dbr:Water_gas_electricity dbr:Gas,_electricity,_and_water dbr:Gas,_electricity,_water dbr:Gas,_water,_and_electricity dbr:Gas,_water,_electricity dbr:Gas_electricity_and_water dbr:Gas_electricity_water dbr:Gas_water_and_electricity dbr:Gas_water_electricity dbr:Impossible_House_puzzle dbr:Supuzzle dbr:3_cottage_problem dbr:3_cottages_problem dbr:3_utilities_problem dbr:3_utility_problem dbr:Three-cottage_problem dbr:Three_cottage_problem dbr:Three_cottages_problem dbr:Three_utility_problem dbr:Utilities_problem dbr:SuPuzzle |
| is dbo:wikiPageWikiLink of | dbr:List_of_impossible_puzzles dbr:K33 dbr:Crossing_number_(graph_theory) dbr:Möbius_strip dbr:Puzzle dbr:Hans_Peter_Jørgen_Julius_Thomsen dbr:Three_Wells_(disambiguation) dbr:Planar_graph dbr:Utility_graph dbr:Thomsen_graph dbr:Outline_of_games dbr:Topological_graph_theory dbr:Turán's_brick_factory_problem dbr:Electricity,_gas,_and_water dbr:Electricity,_gas,_water dbr:Electricity,_water,_and_gas dbr:Electricity,_water,_gas dbr:Electricity_gas_and_water dbr:Electricity_gas_water dbr:Electricity_water_and_gas dbr:Electricity_water_gas dbr:Water,_gas,_&_electricity dbr:Water,_gas,_and_electricity dbr:Water_gas_and_electricity dbr:Water,_electricity,_and_gas dbr:Water,_electricity,_gas dbr:Water,_gas,_electricity dbr:Water,_gas_and_electricity dbr:Water_electricity_and_gas dbr:Water_electricity_gas dbr:Water_gas_electricity dbr:Gas,_electricity,_and_water dbr:Gas,_electricity,_water dbr:Gas,_water,_and_electricity dbr:Gas,_water,_electricity dbr:Gas_electricity_and_water dbr:Gas_electricity_water dbr:Gas_water_and_electricity dbr:Gas_water_electricity dbr:Impossible_House_puzzle dbr:Supuzzle dbr:3_cottage_problem dbr:3_cottages_problem dbr:3_utilities_problem dbr:3_utility_problem dbr:Three-cottage_problem dbr:Three_cottage_problem dbr:Three_cottages_problem dbr:Three_utility_problem dbr:Utilities_problem dbr:SuPuzzle |
| is dbp:knownFor of | dbr:Hans_Peter_Jørgen_Julius_Thomsen |
| is foaf:primaryTopic of | wikipedia-en:Three_utilities_problem |
