In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge, a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e; the definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs there may be multiple dual graphs, depending on the choice of planar embedding of the graph; the first form of graph duality to be recognized was the association of the Platonic solids into pairs of dual polyhedra. Graph duality is a topological generalization of the geometric concepts of dual polyhedra and dual tessellations, is in turn generalized algebraically by the concept of a dual matroid. Variations of planar graph duality include a version of duality for directed graphs, duality for graphs embedded onto non-planar two-dimensional surfaces.
However, these notions of dual graphs should not be confused with a different notion, the edge-to-vertex dual or line graph of a graph. The term "dual" is used because the property of being a dual graph is symmetric, meaning that if H is a dual of a connected graph G G is a dual of H; when discussing the dual of a graph G, the graph G itself may be referred to as the "primal graph". Many other graph properties and structures may be translated into other natural properties and structures of the dual. For instance, cycles are dual to cuts, spanning trees are dual to the complements of spanning trees, simple graphs are dual to 3-edge-connected graphs. Graph duality can help explain the structure of mazes and of drainage basins. Dual graphs have been applied in computer vision, computational geometry, mesh generation, the design of integrated circuits; the unique planar embedding of a cycle graph divides the plane into only two regions, the inside and outside of the cycle, by the Jordan curve theorem.
However, in an n-cycle, these two regions are separated from each other by n different edges. Therefore, the dual graph of the n-cycle is a multigraph with two vertices, connected to each other by n dual edges; such a graph is called a dipole graph. Conversely, the dual to an n-edge dipole graph is an n-cycle. According to Steinitz's theorem, every polyhedral graph must be planar and 3-vertex-connected, every 3-vertex-connected planar graph comes from a convex polyhedron in this way; every three-dimensional convex polyhedron has a dual polyhedron. Whenever two polyhedra are dual, their graphs are dual. For instance the Platonic solids come in dual pairs, with the octahedron dual to the cube, the dodecahedron dual to the icosahedron, the tetrahedron dual to itself. Polyhedron duality can be extended to duality of higher dimensional polytopes, but this extension of geometric duality does not have clear connections to graph-theoretic duality. A plane graph is said to be self-dual; the wheel graphs provide an infinite family of self-dual graphs coming from self-dual polyhedra.
However, there exist self-dual graphs that are not polyhedral, such as the one shown. Servatius & Christopher describe two operations and explosion, that can be used to construct a self-dual graph containing a given planar graph, it follows from Euler's formula that every self-dual graph with n vertices has 2n − 2 edges. Every simple self-dual planar graph contains at least four vertices of degree three, every self-dual embedding has at least four triangular faces. Many natural and important concepts in graph theory correspond to other natural but different concepts in the dual graph; because the dual of the dual of a connected plane graph is isomorphic to the primal graph, each of these pairings is bidirectional: if concept X in a planar graph corresponds to concept Y in the dual graph concept Y in a planar graph corresponds to concept X in the dual. The dual of a simple graph need not be simple: it may have self-loops or multiple edges connecting the same two vertices, as was evident in the example of dipole multigraphs being dual to cycle graphs.
As a special case of the cut-cycle duality discussed below, the bridges of a planar graph G are in one-to-one correspondence with the self-loops of the dual graph. For the same reason, a pair of parallel edges in a dual multigraph corresponds to a 2-edge cutset in the primal graph. Therefore, a planar graph is only if its dual has no 1 - or 2-edge cutsets; the simple planar graphs whose duals are simple are the 3-edge-connected simple planar graphs. This class of graphs includes, but is not the same as, the class of 3-vertex-connected simple planar graphs. For instance, the figure showing a self-dual graph is 3-edge-connected but is not 3-vertex-connected; because the dual graph depends on a particular embedding, the dual graph of a p
Hassler Whitney was an American mathematician. He was one of the founders of singularity theory, did foundational work in manifolds, immersions, characteristic classes, geometric integration theory. Hassler Whitney was born on March 23, 1907, in New York City, where his father Edward Baldwin Whitney was the First District New York Supreme Court judge, his mother, A. Josepha Newcomb Whitney, was an artist and active in politics, his paternal grandfather was William Dwight Whitney, professor of Ancient Languages at Yale University and Sanskrit scholar. Whitney was the great grandson of Connecticut Governor and US Senator Roger Sherman Baldwin, the great-great-grandson of American founding father Roger Sherman, his maternal grandparents were astronomer and mathematician Simon Newcomb, a Steeves descendant, Mary Hassler Newcomb, granddaughter of the first superintendent of the Coast Survey Ferdinand Rudolph Hassler. His great uncle Josiah Whitney was the first to survey Mount Whitney, he married three times: his first wife was Margaret R. Howell, married on the 30 May 1930.
They had three children, James Newcomb and Marian. After his first divorce, on January 16, 1955 he married Mary Barnett Garfield, he and Mary had Sarah Newcomb and Emily Baldwin. Whitney divorced his second wife and married Barbara Floyd Osterman on 8 February 1986. Whitney and his first wife Margaret made an innovative decision in 1939 that influenced the history of modern architecture in New England, when they commissioned the architect Edwin B. Goodell, Jr. to design a new residence for their family in Weston, Massachusetts. They purchased a rocky hillside site on a historic road, next door to another International Style house by Goodell from several years earlier, designed for Richard and Caroline Field. Distinctively featuring flat roofs, flush wood siding, corner windows—all of which were unusual architectural elements at the time—the Whitney House was a creative response to its site, in that it placed the main living spaces one floor above ground level, with large banks of windows opening to the south sun and to views of the beautiful property.
The Whitney House survives today, along with the Field House, more than 75 years following its original construction. Throughout his life he pursued two particular hobbies with excitement: mountain-climbing. An accomplished player of the violin and the viola, Whitney played with the Princeton Musical Amateurs, he would run outside, 6 to 12 miles every other day. As an undergraduate, with his cousin Bradley Gilman, Whitney made the first ascent of the Whitney–Gilman ridge on Cannon Mountain, New Hampshire in 1929, it was the hardest and most famous rock climb in the East. He was a member of the Swiss Alpine Society and the Yale Mountaineering Society and climbed most of the mountain peaks in Switzerland. Three years after his third marriage, on 10 May 1989, Whitney died in Princeton, after suffering a stroke. In accordance with his wish, Hassler Whitney ashes rest atop mountain Dents Blanches in Switzerland where Oscar Burlet, another mathematician and member of the Swiss Alpine Club, placed them on August 20, 1989.
Whitney attended Yale University where he received baccalaureate degrees in physics and in music in 1928 and in 1929. In 1932, he earned a PhD in mathematics at Harvard University, his doctoral dissertation was The Coloring of Graphs, written under the supervision of George David Birkhoff. At Harvard, Birkhoff got him a job as Instructor of Mathematics for the years 1930–31, an Assistant Professorship for the years 1934–35. On he held the following working positions: NRC Fellow, Mathematics, 1931–33, he was a member of the National Academy of Science. In 1947 he was elected member of the American Philosophical Society. In 1969 he was awarded the Lester R. Ford Award for the paper in two parts "The mathematics of Physical quantities". In 1976 he was awarded the National Medal of Science. In 1980 he was elected honorary member of the London Mathematical Society. In 1983 he received the Wolf Prize from the Wolf Foundation, in 1985, he was awarded the Steele Prize from the American Mathematical Society.
Whitney's earliest work, from 1930 to 1933, was on graph theory. Many of his contributions were to the graph-coloring, the ultimate computer-assisted solution to the four-color problem relied on some of his results, his work in graph theory culminated in a 1933 paper, where he laid the foundations for matroids, a fundamental notion in modern combinatorics and representation the
W. T. Tutte
William Thomas "Bill" Tutte OC FRS FRSC was a British codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a major Nazi German cipher system, used for top-secret communications within the Wehrmacht High Command; the high-level, strategic nature of the intelligence obtained from Tutte's crucial breakthrough, in the bulk decrypting of Lorenz-enciphered messages contributed and even decisively, to the defeat of Nazi Germany. He had a number of significant mathematical accomplishments, including foundation work in the fields of graph theory and matroid theory. Tutte's research in the field of graph theory proved to be of remarkable importance. At a time when graph theory was still a primitive subject, Tutte commenced the study of matroids and developed them into a theory by expanding from the work that Hassler Whitney had first developed around the mid 1930s. Though Tutte's contributions to graph theory have been influential to modern graph theory and many of his theorems have been used to keep making advances in the field, most of his terminology was not in agreement with their conventional usage and thus his terminology is not used by graph theorists today.
"Tutte advanced graph theory from a subject with one text toward its present active state." Tutte was born in Newmarket in Suffolk. He was the younger son of William John Tutte, an estate gardener, Annie, a housekeeper. Both parents worked at Fitzroy House stables; the family spent some time in Buckinghamshire, County Durham and Yorkshire before returning to Newmarket, where Tutte attended Cheveley Church of England primary school. In 1927, when he was ten, Tutte won a scholarship to the County High School for Boys, he took up his place there in 1928. In 1935 he won a scholarship to study natural sciences at Trinity College, where he specialized in chemistry and graduated with first-class honours in 1938, he continued with physical chemistry as a graduate student, but transferred to mathematics at the end of 1940. As a student, he became one of the first to solve the problem of squaring the square, the first to solve the problem without a squared subrectangle. Together the four created the pseudonym Blanche Descartes, under which Tutte published for years.
Soon after the outbreak of the Second World War, Tutte's tutor, Patrick Duff, suggested him for war work at the Government Code and Cypher School at Bletchley Park. He was interviewed and sent on a training course in London before going to Bletchley Park, where he joined the Research Section. At first, he worked on the Hagelin cipher, being used by the Italian Navy; this was a rotor cipher machine, available commercially, so the mechanics of enciphering was known, decrypting messages only required working out how the machine was set up. In the summer of 1941, Tutte was transferred to work on a project called Fish. Intelligence information had revealed that the Germans called the wireless teleprinter transmission systems "Sägefisch"; this led the British to use the code Fish for the German teleprinter cipher system. The nickname Tunny was used for the first non-Morse link, it was subsequently used for the Lorenz SZ machines and the traffic that they enciphered. Telegraphy used the 5-bit International Telegraphy Alphabet No. 2.
Nothing was known about the mechanism of enciphering other than that messages were preceded by a 12-letter indicator, which implied a 12-wheel rotor cipher machine. The first step, had to be to diagnose the machine by establishing the logical structure and hence the functioning of the machine. Tutte played a pivotal role in achieving this, it was not until shortly before the Allied victory in Europe in 1945, that Bletchley Park acquired a Tunny Lorenz cipher machine. Tutte's breakthroughs led to bulk decrypting of Tunny-enciphered messages between the German High Command in Berlin and their army commands throughout occupied Europe and contributed—perhaps decisively—to the defeat of Germany. On 31 August 1941, two versions of the same message were sent using identical keys, which constituted a "depth"; this allowed John Tiltman, Bletchley Park's veteran and remarkably gifted cryptanalyst, to deduce that it was a Vernam cipher which uses the Exclusive Or function, to extract the two messages and hence obtain the obscuring key.
After a fruitless period during which Research Section cryptanalysts tried to work out how the Tunny machine worked and some other keys were handed to Tutte, asked to "see what you can make of these". At his training course, Tutte had been taught the Kasiski examination technique of writing out a key on squared paper, starting a new row after a defined number of characters, suspected of being the frequency of repetition of the key. If this number was correct, the columns of the matrix would show more repetitions of sequences of characters than chance alone. Tutte knew that the Tunny indicators used 25 letters for 11 of the positions, but only 23 letters for the other, he therefore tried Kasiski's technique on the first impulse of the key characters, using a repetition of 25 × 23 = 575. He did not observe a large number of column repetitions with this period, but he did observe the phenomenon on a diagonal, he therefore tried again with 574. Recognising that the prime factors of this number are 2, 7 and 41, he tried again with a period of 41 and "got a rectangle of dots and crosses, replete with repetitions".
It was clear