Забыли?

?

# The Four Color Theorem (4CT)

код для вставкиСкачать
```The Four Color Theorem
(4CT)
Emily Mis
Discrete Math Final Presentation
Origin of the 4CT
вЂў First introduced by Francis Guthrie in the early 1850вЂ™s
вЂ“ Communicated to Augustus De Morgan in 1852
вЂў First printed reference of the theorem in 1878 in the
Proceedings of the London Mathematical Society
вЂў The original problem was stated to be:
вЂњвЂ¦the greatest number of colors to be used in coloring
a map so as to avoid identity of color in lineally
contiguous districts is four.вЂќ
-Frederick Guthrie to the
Royal Society of Edinburgh (1880)
Graph Theory for the Four Color Conjecture
Graph Theory for the Four Color Conjecture
Graph Theory for the Four Color Conjecture
Any Planar Map Is Four-Colorable
Planar graph - a graph drawn in a
plane without any of its edges
crossing or intersecting
Each vertex (A,B,C,D,E) represents
a region in a graph
Each edge represents regions that
share a boundary
вЂњIn any plane graph each vertex can be assigned
exactly one of four colors so that adjacent vertices have
different colors.вЂќ
-Four-Color Conjecture
вЂњProvingвЂќ the Conjecture
вЂў A. B. Kempe in 1879
вЂ“ Found to be flawed by Heawood in 1890
вЂ“ Introduced a new technique now called KempeвЂ™s
chains
KempeвЂ™s Chains
A four-sided region R is
surrounded by Regions 1 - 4
by the four available colors
KempeвЂ™s Chains
A four-sided region R is
surrounded by Regions 1 - 4
by the four available colors
First consider all regions colored b
and d.
Either there is a chain of regions
colored b and d connecting Region
2 and Region 4, or no such chain
exists. If no chain exists, you can
change the color of either Region 4
or Region 2 in order to free up the
other color for the center region R.
вЂњProvingвЂќ the Conjecture
вЂў A. B. Kempe in 1879
вЂ“ Found to be flawed by Heawood in 1890
вЂ“ Introduced a new technique now called KempeвЂ™s
chains
вЂў P. G. Tait in 1880
вЂ“Found to be flawed by Peterson in 1891
вЂ“Found an equivalent formulation of the 4CT in
terms of three-edge coloring
No two edges coming
from the same vertex
share the same color
вЂњProvingвЂќ the Conjecture
вЂў A. B. Kempe in 1879
вЂ“ Found to be flawed by Heawood in 1890
вЂ“ Introduced a new technique now called KempeвЂ™s
chains
вЂў P. G. Tait in 1880
вЂ“Found to be flawed by Peterson in 1891
вЂ“Found an equivalent formulation of the 4CT in
terms of three-edge coloring
вЂў 1900вЂ™s brought proofs on limited sets of
regions
вЂ“ Increased to a 90-region proof in 1976 by Mayer
other concerned parties
вЂў Sir William Hamilton
вЂў Arthur Cayley
вЂў Lewis Carroll
"A is to draw a fictitious map divided into counties.
B is to color it (or rather mark the counties with
names of
colours) using as few colours as possible.
Two adjacent counties must have different colours.
A's object is to force B to use as many colours
as possible. How many can he force B to use?"
other concerned parties
вЂў Sir William Hamilton
вЂў Arthur Cayley
вЂў Lewis Carroll
"A is to draw a fictitious map divided into counties.
B is to color it (or rather mark the counties with
names of
colours) using as few colours as possible.
Two adjacent counties must have different colours.
A's object is to force B to use as many colours
as possible. How many can he force B to use?"
The New Proof of the 4CT
вЂў Completed by Appel and Haken in 1976
вЂ“ Based on KempeвЂ™s chains
вЂ“ Required 1200 hours of computation
вЂў Used mostly to perform reductions and
discharges on planar configurations using
KempeвЂ™s original idea of chains
вЂў Introduced a collection of 1476 reducible
configurations
вЂ“ These configurations are an unavoidable set that
must be tested to show that they are reducible
вЂ“ No member of this set can appear in a minimal
counterexample
Discharging - Why do it?
Discharging -- moving a charge along a circuit of connected vertices in
order to cancel positive and negative values as much as possible
Sites where a positive value remains are often part of a reducible
configuration
G is the smallest maximal plane graph which cannot be four-colored
each vertex in G gets a charge (6-deg v)
from Euler, we know that the sum of all G is 12
A charge is then moved around the circuit to change the charges of
individual vertices
Discharging is used to show that a certain set S is an unavoidable set
WeвЂ™re not in Kansas anymore
вЂў A new version of the computer-based proof was
produced by Robertson, Sanders, Seymour and
Thomas in 1996
вЂ“ Used a quadratic algorithm for four-color planar graphs
вЂ“ Decreased the size of the unavoidable set to 633
вЂў The fears:
вЂ“ Is this a movement towards computer-based proof
вЂ“ Does this proof вЂњqualifyвЂќ as a proof based on the
original definition of a вЂњproofвЂќ?
Works Cited
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
Thomas, Robin (1998) An Update on the Four-Color Theorem, Notices
of the AMS, 45: 7:848-859
Brun, Yuriy The Four Color Theorem, MIT Undergraduate Journal of
Mathematics pp 21-28
Calude, Andreea (2001)The Journey of the Four Colour Theorem
Through Time, The New Zealand Mathematics Magazine, 38:3:27-35
Cayley (1879) On the colouring of maps, Proceedings of the Royal
Geographical Society and Monthly Record of Geography New Monthly
Series, 1:4:259-261
Robertson et al (1996) A New Proof of the Four-Colour Theorem,
Electronic Research Announcements of the AMS, 2:1:17-25
Mitchem, John (1981) On the History and Solution of the Four-Color
Map Problem, The Two-Year College Mathematics Journal, 12:2:108116
Bernhart (1991) Review of Every Planar Map is Four Colorable by
Appel and Haken, American Mathematical Society, Providence RI,
1989
May, Kenneth (1965) The Origin of the Four-Color Conjecture, Isis,
56:3:346-348
Saaty, Thomas (1967) Remarks on the Four Color Problem: the Kempe
Catastrophe, Mathematics Magazine, 40:1:31-36
```
###### Документ
Категория
Презентации
Просмотров
17
Размер файла
251 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа