This is a good article. Click here for more information.

Three utilities problem

From Wikipedia, the free encyclopedia
(Redirected from Utility graph)

Template:Short description Lua error in package.lua at line 80: module 'Module:Hatnote list' not found.

Diagram of the three utilities problem on a plane. All lines are connected, but two of them are crossing.

Page Template:Multiple image/styles.css has no content.

Two views of the utility graph, also known as the Thomsen graph or K3,3

The three utilities problem, also known as water, gas and electricity, is a mathematical puzzle that asks for non-crossing connections to be drawn between three houses and three utility companies on a 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 any of them 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 K3,3, 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 K3,3 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 K3,3.

The general question of minimizing the number of crossings in drawings of complete bipartite graphs is known as Turán's brick factory problem. For K3,3 the minimum number of crossings is one.

K3,3 is a graph with six vertices and nine edges, often referred to as the utility graph in reference to the problem.[1]Template:R/superscript It has also been called the Thomsen graph after the 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.

History

A review of the history of the three utilities problem is given by Lua error in package.lua at line 80: module 'Module:Footnotes/anchor_id_list' not found.. He states that most published references to the problem characterize it as "very ancient".[2]Template:R/superscript In the earliest publication found by Kullman, Henry Dudeney (1917) names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than electric lighting, or even gas".[3]Template:R/superscript Dudeney also published the same puzzle previously, in The Strand Magazine in 1913.[4]Template:R/superscript A competing claim of priority goes to Sam Loyd, who was quoted by his son in a posthumous biography as having published the problem in 1900.[5]Template:R/superscript

Another early version of the problem involves connecting three houses to three wells.[6]Template:R/superscript It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern numberlink puzzles.[7]Template:R/superscript Loyd's puzzle "The Quarrelsome Neighbors" similarly involves connecting three houses to three gates by three non-crossing paths (rather than nine as in the utilities problem); one house and the three gates are on the wall of a rectangular yard, which contains the other two houses within it.[8]Template:R/superscript

As well as in the three utilities problem, the graph K3,3 appears in late 19th-century and early 20th-century publications both in early studies of structural rigidity[9]Template:R/superscript[10]Template:R/superscript and in chemical graph theory, where Julius Thomsen proposed it in 1886 for the then-uncertain structure of benzene.[11]Template:R/superscript In honor of Thomsen's work, K3,3 is sometimes called the Thomsen graph.[12]Template:R/superscript

Statement

The three utilities problem can be stated as follows:

Page Template:Blockquote/styles.css has no content.

Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house to each company. Is there a way to make all nine connections without any of the lines crossing each other?

The problem is an abstract mathematical puzzle which imposes constraints that would not exist in a practical engineering situation. Its mathematical formalization is part of the field of topological graph theory which studies the embedding of graphs on surfaces. An important part of the puzzle, but one that is often not stated explicitly in informal wordings of the puzzle, is that the houses, companies, and lines must all be placed on a two-dimensional surface with the topology of a plane, and that the lines are not allowed to pass through other buildings; sometimes this is enforced by showing a drawing of the houses and companies, and asking for the connections to be drawn as lines on the same drawing.[13]Template:R/superscript[14]Template:R/superscript

In more formal graph-theoretic terms, the problem asks whether the complete bipartite graph K3,3 is a planar graph. This graph has six vertices in two subsets of three: one vertex for each house, and one for each utility. It has nine edges, one edge for each of the pairings of a house with a utility, or more abstractly one edge for each pair of a vertex in one subset and a vertex in the other subset. Planar graphs are the graphs that can be drawn without crossings in the plane, and if such a drawing could be found, it would solve the three utilities puzzle.[13]Template:R/superscript[14]Template:R/superscript

Puzzle solutions

Unsolvability

Proof without words: One house is temporarily deleted. The lines connecting the remaining houses with the utilities divide the plane into three regions. Whichever region the deleted house is placed into, the similarly shaded utility is outside the region. By the Jordan curve theorem, a line connecting them must intersect one of the existing lines.

As it is usually presented (on a flat two-dimensional plane), the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other. In other words, the graph K3,3 is not planar. Kazimierz Kuratowski stated in 1930 that K3,3 is nonplanar,[15]Template:R/superscript from which it follows that the problem has no solution. Lua error in package.lua at line 80: module 'Module:Footnotes/anchor_id_list' not found., however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ K3,3 ] is non-planar".[2]Template:R/superscript

One proof of the impossibility of finding a planar embedding of K3,3 uses a case analysis involving the Jordan curve theorem.[16]Template:R/superscript In this solution, one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding.[17]Template:R/superscript

Alternatively, it is possible to show that any bridgeless bipartite planar graph with V vertices and E edges has E≤2V−4 by combining the Euler formula V−E+F=2 (where F is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (the vertices around each face must alternate between houses and utilities, so each face has at least four edges, and each edge belongs to exactly two faces). In the utility graph, E=9 and 2V−4=8 so in the utility graph it is untrue that E≤2V−4. Because it does not satisfy this inequality, the utility graph cannot be planar.[18]Template:R/superscript

Changing the rules

Page Template:Multiple image/styles.css has no content.

Solution on a Möbius strip
Solution on a torus
A torus allows up to 4 utilities and 4 houses

K3,3 is a toroidal graph, which means that it can be embedded without crossings on a torus, a surface of genus one.[19]Template:R/superscript These embeddings solve versions of the puzzle in which the houses and companies are drawn on a coffee mug or other such surface instead of a flat plane.[20]Template:R/superscript There is even enough additional freedom on the torus to solve a version of the puzzle with four houses and four utilities.[21]Template:R/superscript[5]Template:R/superscript Similarly, if the three utilities puzzle is presented on a sheet of a transparent material, it may be solved after twisting and gluing the sheet to form a Möbius strip.[22]Template:R/superscript

Another way of changing the rules of the puzzle that would make it solvable, suggested by Henry Dudeney, is to allow utility lines to pass through other houses or utilities than the ones they connect.[3]Template:R/superscript

Properties of the utility graph

Beyond the utility puzzle, the same graph K3,3 comes up in several other mathematical contexts, including rigidity theory, the classification of cages and well-covered graphs, the study of graph crossing numbers, and the theory of graph minors.

Rigidity

The utility graph K3,3 is a Laman graph, meaning that for almost all placements of its vertices in the plane, there is no way to continuously move its vertices while preserving all edge lengths, other than by a rigid motion of the whole plane, and that none of its spanning subgraphs have the same rigidity property. It is the smallest example of a nonplanar Laman graph.[23]Template:R/superscript Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.[9]Template:R/superscript[24]Template:R/superscript For general-position embeddings, a polynomial equation describing all possible placements with the same edge lengths has degree 16, meaning that in general there can be at most 16 placements with the same lengths. It is possible to find systems of edge lengths for which up to eight of the solutions to this equation describe realizable placements.[24]Template:R/superscript

Other graph-theoretic properties

K3,3 is a triangle-free graph, in which every vertex has exactly three neighbors (a cubic graph). Among all such graphs, it is the smallest. Therefore, it is the (3,4)-cage, the smallest graph that has three neighbors per vertex and in which the shortest cycle has length four.[25]Template:R/superscript

Like all other complete bipartite graphs, it is a well-covered graph, meaning that every maximal independent set has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, and are of equal sizes. K3,3 is one of only seven 3-regular 3-connected well-covered graphs.[26]Template:R/superscript

Generalizations

Drawing of K3,3 with one crossing

Two important characterizations of planar graphs, Kuratowski's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor the complete graph K5 as a subdivision, and Wagner's theorem that the planar graphs are exactly the graphs that contain neither K3,3 nor K5 as a minor, make use of and generalize the non-planarity of K3,3.[27]Template:R/superscript

Pál Turán's "brick factory problem" asks more generally for a formula for the minimum number of crossings in a drawing of the complete bipartite graph Ka,b in terms of the numbers of vertices a and b on the two sides of the bipartition. The utility graph K3,3 may be drawn with only one crossing, but not with zero crossings, so its crossing number is one.[5]Template:R/superscript[28]Template:R/superscript

References

  1. ^ Page Module:Citation/CS1/styles.css has no content.Gries, David; Schneider, Fred B. (1993), "Chapter 19: A theory of graphs", A Logical Approach to Discrete Math, New York: Springer, pp. 423–460, doi:10.1007/978-1-4757-3837-7, ISBN 978-1-4419-2835-1, S2CID 206657798. See p. 437: "K3,3 is known as the utility graph".
  2. ^ a b Page Module:Citation/CS1/styles.css has no content.Kullman, David (1979), "The utilities problem", Mathematics Magazine, 52 (5): 299–302, doi:10.1080/0025570X.1979.11976807, JSTOR 2689782
  3. ^ a b Page Module:Citation/CS1/styles.css has no content.Dudeney, Henry (1917), "Problem 251 – Water, Gas, and Electricity", Amusements in mathematics, vol. 100, Thomas Nelson, p. 73, Bibcode:1917Natur.100..302., doi:10.1038/100302a0, S2CID 10245524. The solution given on pp. 200–201 involves passing a line through one of the other houses.
  4. ^ Page Module:Citation/CS1/styles.css has no content.Dudeney, Henry (1913), "Perplexities, with some easy puzzles for beginners", The Strand Magazine, vol. 46, p. 110
  5. ^ a b c Page Module:Citation/CS1/styles.css has no content.Beineke, Lowell; Wilson, Robin (2010), "The early history of the brick factory problem", The Mathematical Intelligencer, 32 (2): 41–48, doi:10.1007/s00283-009-9120-4, MR 2657999, S2CID 122588849
  6. ^ Page Module:Citation/CS1/styles.css has no content."Puzzle", Successful Farming, vol. 13, p. 50, 1914; Page Module:Citation/CS1/styles.css has no content."A well and house puzzle", The Youth's Companion, vol. 90, no. 2, p. 392, 1916.
  7. ^ Page Module:Citation/CS1/styles.css has no content."32. The fountain puzzle", The Magician's Own Book, Or, The Whole Art of Conjuring, New York: Dick & Fitzgerald, 1857, p. 276
  8. ^ Page Module:Citation/CS1/styles.css has no content.Loyd, Sam (1959), "82: The Quarrelsome Neighbors", in Gardner, Martin (ed.), Mathematical Puzzles of Sam Loyd, Dover Books, p. 79, ISBN 9780486204987{{citation}}: CS1 maint: ignored ISBN errors (link)
  9. ^ a b Page Module:Citation/CS1/styles.css has no content.Dixon, A. C. (1899), "On certain deformable frameworks", Messenger of Mathematics, 29: 1–21, JFM 30.0622.02
  10. ^ Page Module:Citation/CS1/styles.css has no content.Henneberg, L. (1908), "Die graphische Statik der starren Körper", Encyklopädie der Mathematischen Wissenschaften, vol. 4, pp. 345–434. See in particular p. 403.
  11. ^ Page Module:Citation/CS1/styles.css has no content.Thomsen, Julius (July 1886), "Die Constitution des Benzols" (PDF), Berichte der Deutschen Chemischen Gesellschaft, 19 (2): 2944–2950, doi:10.1002/cber.188601902285
  12. ^ Page Module:Citation/CS1/styles.css has no content.Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, p. 23, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR 1633290
  13. ^ a b Page Module:Citation/CS1/styles.css has no content.Harary, Frank (1960), "Some historical and intuitive aspects of graph theory", SIAM Review, 2 (2): 123–131, Bibcode:1960SIAMR...2..123H, doi:10.1137/1002023, MR 0111698
  14. ^ a b Page Module:Citation/CS1/styles.css has no content.Bóna, Miklós (2011), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, pp. 275–277, ISBN 9789814335232. Bóna introduces the puzzle (in the form of three houses to be connected to three wells) on p. 275, and writes on p. 277 that it "is equivalent to the problem of drawing K3,3 on a plane surface without crossings".
  15. ^ Page Module:Citation/CS1/styles.css has no content.Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fundamenta Mathematicae (in français), 15: 271–283, doi:10.4064/fm-15-1-271-283
  16. ^ Page Module:Citation/CS1/styles.css has no content.Ayres, W. L. (1938), "Some elementary aspects of topology", The American Mathematical Monthly, 45 (2): 88–92, doi:10.1080/00029890.1938.11990773, JSTOR 2304276, MR 1524194
  17. ^ Page Module:Citation/CS1/styles.css has no content.Trudeau, Richard J. (1993), Introduction to Graph Theory, Dover Books on Mathematics, New York: Dover Publications, pp. 68–70, ISBN 978-0-486-67870-2
  18. ^ Page Module:Citation/CS1/styles.css has no content.Kappraff, Jay (2001), Connections: The Geometric Bridge Between Art and Science, K & E Series on Knots and Everything, vol. 25, World Scientific, p. 128, ISBN 9789810245863
  19. ^ Page Module:Citation/CS1/styles.css has no content.Harary, F. (1964), "Recent results in topological graph theory", Acta Mathematica, 15 (3–4): 405–411, doi:10.1007/BF01897149, hdl:2027.42/41775, MR 0166775, S2CID 123170864; see p. 409.
  20. ^ Page Module:Citation/CS1/styles.css has no content.Parker, Matt (2015), Things to Make and Do in the Fourth Dimension: A Mathematician's Journey Through Narcissistic Numbers, Optimal Dating Algorithms, at Least Two Kinds of Infinity, and More, New York: Farrar, Straus and Giroux, pp. 180–181, 191–192, ISBN 978-0-374-53563-6, MR 3753642
  21. ^ Page Module:Citation/CS1/styles.css has no content.O’Beirne, T. H. (December 21, 1961), "Christmas puzzles and paradoxes, 51: For boys, men and heroes", New Scientist, vol. 12, no. 266, pp. 751–753
  22. ^ Page Module:Citation/CS1/styles.css has no content.Larsen, Mogens Esrom (1994), "Misunderstanding my mazy mazes may make me miserable", in Guy, Richard K.; Woodrow, Robert E. (eds.), Proceedings of the Eugène Strens Memorial Conference on Recreational Mathematics and its History held at the University of Calgary, Calgary, Alberta, August 1986, MAA Spectrum, Washington, DC: Mathematical Association of America, pp. 289–293, ISBN 0-88385-516-X, MR 1303141. See Figure 7, p. 292.
  23. ^ Page Module:Citation/CS1/styles.css has no content.Streinu, Ileana (2005), "Pseudo-triangulations, rigidity and motion planning", Discrete & Computational Geometry, 34 (4): 587–635, doi:10.1007/s00454-005-1184-0, MR 2173930, S2CID 25281202. See p. 600: "Not all generically minimally rigid graphs have embeddings as pseudo-triangulations, because not all are planar graphs. The smallest example is K3,3".
  24. ^ a b Page Module:Citation/CS1/styles.css has no content.Walter, D.; Husty, M. L. (2007), "On a nine-bar linkage, its possible configurations and conditions for paradoxical mobility" (PDF), in Merlet, Jean-Pierre; Dahan, Marc (eds.), 12th World Congress on Mechanism and Machine Science (IFToMM 2007), International Federation for the Promotion of Mechanism and Machine Science
  25. ^ Page Module:Citation/CS1/styles.css has no content.Tutte, W. T. (1947), "A family of cubical graphs", Proceedings of the Cambridge Philosophical Society, 43 (4): 459–474, Bibcode:1947PCPS...43..459T, doi:10.1017/s0305004100023720, MR 0021678, S2CID 123505185
  26. ^ Page Module:Citation/CS1/styles.css has no content.Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F. (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212, MR 1220613
  27. ^ Page Module:Citation/CS1/styles.css has no content.Little, Charles H. C. (1976), "A theorem on planar graphs", in Casse, Louis R. A.; Wallis, Walter D. (eds.), Combinatorial Mathematics IV: Proceedings of the Fourth Australian Conference Held at the University of Adelaide August 27–29, 1975, Lecture Notes in Mathematics, vol. 560, Springer, pp. 136–141, doi:10.1007/BFb0097375, ISBN 978-3-540-08053-4, MR 0427121
  28. ^ Page Module:Citation/CS1/styles.css has no content.Pach, János; Sharir, Micha (2009), "5.1 Crossings—the Brick Factory Problem", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127
Retrieved from "http://cosmopedia.co/index.php?title=Three_utilities_problem&oldid=39211"