About: Three utilities problem

An Entity of Type: building, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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.

thumbnail
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
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 58862 (xsd:integer)
dbo:wikiPageLength
  • 25206 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1104252447 (xsd:integer)
dbo:wikiPageWikiLink
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
dbp:year
  • 1917 (xsd:integer)
dcterms:subject
gold:hypernym
rdf:type
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
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is dbp:knownFor of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License