请输入您要查询的字词:

 

单词 KempeChain
释义

Kempe chain


Alfred B. Kempe(http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Kempe.htmlbio at St Andrews)first used these chains, now called after him,in 1879 in a “proof” of the four-color conjecture. Although Percy Heawoodfound a flaw in his proof 11 years later, the idea of Kempe chainsMathworldPlanetmath itself isquite sound. Heawood used it to prove 5 colors suffice for maps on the plane,and the 1976 proof by Appel, Haken and Koch is also based on Kempe’s ideas.

The original Kempe chains were used in the context of coloringsMathworldPlanetmath of countrieson a map, or in modern terminology face colorings of a plane graphMathworldPlanetmath G(such that no two adjacent faces receive the same color). The idea wasextended by Heawood to embeddingsMathworldPlanetmathPlanetmath of a graph in any other surface. Here

  • a Kempe chain of colors a and b is a maximal connected set of facesthat have either of those colors. as in: you can travel from any face in the set to any other, through the set. Maximal as in: there are no more faces of those colors you could enlarge the set with, i.e. that border the area you’ve already got.

In the modern dual formulation of the four-color theorem, faces of G arereplaced by vertices of the dual graph G* (and vice versa); vertices areadjacent (linked by an edge) in G* whenever the corresponding faces of Gwere adjacent (sharing a border). It now becomes a vertex coloringproblem (again, adjacent vertices must receive different colors). Here

  • a Kempe chain of colors a and b is a maximal connected subgraphcontaining only vertices of those colors. ConnectedPlanetmathPlanetmath as usual in graph theoryMathworldPlanetmath(there’s a path between any two vertices) and maximal as in: there are nomore vertices of those colors you could enlarge the subgraphMathworldPlanetmath with, i.e. thatare adjacent to a vertex you’ve already got.

    An alternative formulation: let G(a,b) be the subgraph induced by all thevertices of color a or b (that is, with all the edges that run betweenthose vertices). Now any connected componentMathworldPlanetmathPlanetmath H(a,b) of G(a,b) is a Kempechain.

While faces imply an embedding in a surface, the vertex version of thedefinition does not rely on any embedding. The chains are more useful inthe context of an embedding though.

Kempe chains of edges

With edge coloringMathworldPlanetmath of graphs (again, with different colors for adjacentedges i.e. those that meet at a vertex), an analogous concept can defined.Here

  • a Kempe chain of colors a and b is a maximal connected subgraphwhere the edges have either of those colors. Connected and maximal as before.

    An alternative formulation: let G(a,b) be the subgraph consisting of all theedges of color a or b (with any vertices incidentPlanetmathPlanetmath to them). Now anyconnected component H(a,b) of G(a,b) is a Kempe chain.

While superficially similar to the previous definition, these “Kempe chains”are rather different animals. Their structureMathworldPlanetmath is far simpler. At any vertex ofH(a,b), there can be at most one edge of color a and one edge of color b(at most two edges in all). Two things can happen:

  • Every vertex in the chain has two such edges. In a finitegraph, this must mean a closed path (cycle). Note that, being coloredalternatingly, the number of edges must now be even.

  • A vertex misses out on having an edge of one of those colors,and the chain stops there (it can’t miss out on both colors because thenit wouldn’t be part of the chain). In a finite graph, the other end ofthe chain must now also terminate somewhere (at a vertex that missesout either one of the colors). The chain is an open path of one ormore edges (its length can be even or odd).

Kempe chain arguments

One technique that can be used with all these types of chains is

  • swapping the colors in one H(a,b). This is always possible:by definition, there are no adjacent items that couldlead to a color clash.

    Kempe slipped up when he swapped an H(a,b) and an H(a,c) withouttaking in account that swapping colors a and b in part of thegraph could alter the shape and connectedness of any H(a,c), butswapping colors in one Kempe chain at a time (and then taking stock ofthe lay of the land afresh) is quite safe.

    Swapping can be used to free up a color somewhere, see thehttp://planetmath.org/node/6932proof of Vizing’s theoremMathworldPlanetmath for a repeated useof this ploy on edge-based Kempe chains.

Specific to the use in plane graphs we have that

  • if a Kempe chain forms a cycle, it disconnects the sphere or plane areainto disjoint parts (on the plane, inside and outside the cycle).

Specifically when four colors are used for faces:

  • The whole area is divided into red/green swathes and yellow/blue ones.Alternatively, into red/yellow and green/blue ones. Or red/blue andyellow/green ones.

Specifically for edge-based Kempe chains in regularPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath ρ-valent graphs, ifwe try to edge-color the graph with only ρ colors:

  • No vertex can miss out on any of the ρ colors, so every H(a,b)must be a cycle (of even length).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 9:30:31