다음과 같이 생긴 지도를 색을 칠하여 구분하려고 한다.

이 때 가능한 최소한의 색은 몇 개인가 구하여보시오.

 graph이론의 응용으로  4색문제에 관하여 학습한다.

   Four Color Problem

지도의 색칠

우선 다음 그림에 빨강, 파랑, 노랑 세 가지 색으로, 경계가 꼭 다른 색으로 구분되게 색칠할 수가 있는가 생각하여 보시오.

단, 한 점에서 접하는 경우에는 경계로 보지 않는다.

아마 잘 되지 않음을 쉽게 알 수 있을 것이다.  그러면 4색으로는 어떨까?  이것은 유명한 지도 색칠하기 문제이다.

이 문제의 기원은 앞에 학습한 Euler의 "쾨니히스베르크의 다리 건너기"문제와 같은 무렵이며, 그 이후 20C 들어와 새로이 각광을 받고 있는 수학의 topology와 다양한 수학들, 특히 이산수학의 graph이론의 연구의 결과로 해결이 되었다.

현대 수학은 magic에 관한 것들, 끈의 매듭, 미로, 한붓그리기, 앞뒤가 없는 뫼비우스의 띠, 내부 외부가 없는 Klein의 병, 지도 색칠하기, 최적 여행 경로도 등 우리 생활 주변의 여러 문제들은 모두 다 현대 수학의 연구 대상으로 되어수학이 우리 생활과 더욱 가깝게 생각되는 폭 넓은 학문으로 발전하게 되었다.

특히, graph이론의 응용은 고속도로의 인터체인지, 공장과 각 지점 사이의 제품 운반 경로, 전자 제품의 회로도 등 실용적인 면에서도 그 응용의 폭이 넓다.

위 문제는 4색으로는 가능하며, 그 이치를 더 쉽게 이해하려면 연결 상태가 같은 직선형 도선으로 바꾸어 생각하면 이해하기 빠르다.

지도의 색칠 방법은

어떤 복잡한 지도라도 4색만 있으면 구분이 가능하다

라는  4색 문제(four color problem)는뫼비우스 (독일 수학자 1790∼1868)가 1840년 강의를 시작함으로써 시작되었고, 그후 어떤 복잡한 지도라도 5색만 있으면 색칠하는 방법이 가능하다는 사실이 증명되었다.

소련의 젊은 수학자 브오르인스키 (1923∼1943년)는 4색 문제에 관한 정리를 발견하였다고는 하나 유감스럽게도 2차 대전 중 전사하였으므로 그 결과가 전해지지 않는다.

지도가 놓여 있는 공간의 모양은 4색문제의 일반화에서 중요하며다양한 응용결과를 얻을 수 있다. 만일 지도가 놓인 공간의 연결 상태가 공과 같은 것 위에 있는 임의의 지도는 은 4색,  도넛 모양인 입체 위에 있는 지도는 7색이 있어야 된다는 것도 현재 알려져 있다.

다음 그림은 위상적으로 동형인 지도에 대하여는 같은 개수의 색이 필요함을 보여준다.

Figure. Topological equivalence. Each of the maps shown is equivalent as far as the four colour problem is concerned; topologically there is no difference between any of them.

Four Color Theorem

(See also: The Mathematics Behind the Maps, The Most Colorful Math of All, and The Story of the Young Map Colorer.)

The Four Color Problem was famous and unsolved for many years. Has it been solved? What do you think?

The story of the problem

Since the time that mapmakers began making maps that show distinct regions (such as countries or states), it has been known among those in that trade, that if you plan well enough, you will never need more than four colors to color the maps that you make.

The basic rule for coloring a map is that no two regions that share a boundary can be the same color. (The map would look ambiguous from a distance.) It is okay for two regions that only meet at a single point to be colored the same color, however. If you look at a some maps or an atlas, you can verify that this is how all familiar maps are colored.

Mapmakers are not mathematicians, so the assertion that only four colors would be necessary for all maps gained acceptance in the map-making community over the years because no one ever stumbled upon a map that required the use of five colors. When mathematicians picked up the thread of the conversation, they began by asking questions like: Are you sure that four colors are enough? How do you know that no one can draw a map that requires five colors? What is it about the way that regions are arranged and touch each other in a map that would make such a thing true?

When the question came to the European mathematics community at the end of the 19th century, it was perceived as interesting but solvable. Prominent and experienced mathematicians who tackled the problem were surprised by their inability to solve it. Take for example, this account from The Four Color Problem: Assaults and Conquesst by Saaty and Kainen:

 

The great mathematician, Herman Minkowski, once told his students that the 4-Color Conjecture had not been settled because only third-rate mathematicians had concerned themselves with it. "I believe I can prove it," he declared. After a long period, he admitted, "Heaven is angered by my arrogance; my proof is also defective." (Saaty & Kainen , 1986,p.8)

 

A Special Role for the Computer

(4색 문제의 해결은 computer를 사용하였다.)

In 1976, the conjecture was apparently proved by Wolfgang Haken and Kenneth Appel at the Univeristiy of Illinois with the aid of a computer. The program that they wrote was thousands of lines long and took over 1200 hours to run. Since that time, a collective effort by interested mathematicians has been under way to check the program. So far the only errors that have been found are minor and were easily fixed.

Many mathematicians accept the theorem as true.

The proof of the 4-Color-Theorem is a doorway to some interesting questions about the role of human minds and computing machines in mathematics. Is it ``fair'' to accept as true what a computer can verify, even though no single person can? Does the nature or texture of what humans can discover about their world change with the use of computers as thinking tools? Computers are huge and powerful, but finite; will using them as thinking tools be ultimately limiting? These issues are raised and considered in Ad Infinitum: The Ghost in Turing's Machine by Brian Rotman, and Pi in the Sky by John Barrow.

Statements(명제), Conjectures (가설), and Theorems  (정리)

In Mathematics a statement or assertion is a sentence that you are trying to evaluate as true or false. A statement wouldn't have words in it like maybe, perhaps, or sometimes. When you make a statement, you try to make it as precise as possible.

When you think that a statement that you have made is true, you call it a conjecture.

When you have proved that the statement is true, it is called a theorem.

Writing Down Your Discoveries as Proofs

``Doing'' proofs often strikes fear into the heart of the non-mathematician, probably because they are associated with the dense, almost incomprehensible language packed with strange symbols and Greek letters that characterizes the proofs in a math book.

It is true that experienced mathematicians communicate the proofs of their theorems in a sparse language that wastes no ink on the page. Inexperienced mathematicians should remember that when they are communicating with one another, completeness, comprehensibility, and understanding are far more important than dense language. What matters the most is showing that the proof has been pursued logically, and that there are no leaps or gaps in the path to the conclusion.

Always in mathematics, it is important to ask, ``How do I know this?'' and ``Am I sure that this is true?'' and to communicate the answers to those questions in language that is clear in the mathematical community to which you belong.

It is important to remember that proof is not persuasion. Something is not proved mathematically because it seems believable. A statement is true mathematically when, by the rules of logic, it is irrefutable.

Understanding the three proof techniques of induction, deduction, and proof by contradiction can often give you ideas for approaches to take when you are struggling with a problem. You can think of these three techniques as patterns of reasoning. These patterns of reasoning are useful in two ways:

• Understanding them can help you follow someone else's reasoning better when you know what technique they are using.
• When you have made a conjecture and you want to try to prove that it is true, experimenting with the different proof techniques might help you find a proof.

Two other techniques, proof by typesetting and proof by intimidation are often used by the unscrupulous. Don't be fooled!

다음 그림의 지도는 그래프의 모양으로 바꾸어 생각할 수 있다.

지도를 색으로 구분할 수 있게 색칠한다는 것은  다음 그래프에서 인접한 vertex는 다른 색을 대응시켜야 한다는 것과 같다.  이것은 graph의coloring문제를 생각하여 해결할 수 있다.

Coloring Graphs

 G = (V , E , v) is  a graph with no multiple edges and C = { c_1,c_2,..._,c_x }

is a set of colors.

A function f : V → C is called a coloring of graph G using x colors    -   a coloring is proper if any two adjacent vertices have different colors.

- the smallest number of colors needed to produce a proper coloring of a graph G is called the chromatic number of G, denoted by x(G).

Chromatic polynomial P_G(x) is the number of ways to properly color G with x or fewer color

 

Theorem A.If G is a disconnected graph with components G1,G2,...,Gm then

 

Theorem B .

   graph이론의 응용으로  4색문제에 관하여 학습한다.

 다음 그림과 같은 두 개의 매듭은 같은 모양인가 생각하여 보시오.

 본 강의에서는 매듭이론에서의 기본적 용어에 대하여 알아보고, 다양한 매듭의 모양을 구별하여 본다.

Knots (매듭)

다음 여러 종류의 매듭의 모양을 보고 그 모양을

비교하여 보시오.

 Figure 53. Basic knots: (Ⅰ) overhand. (Ⅱ)figure-of-eight, (Ⅲ) trefoil (Ⅳ) four-knot. The first two are typen of knot that you might construct using a length of string. However, for a mathematical study the free ends have to be joined together to form a chlosed loop joining the ends of (Ⅰ) gives (Ⅲ): joining the ends of (Ⅱ) gives (Ⅳ). Drawings (Ⅲ) and (Ⅳ) are examples of what are known as knot diagrams.

다음 그림은 위상적인 방법의 강력함을 보여주는 전형적인 그림이다.   

 Figure 62. Solution to the ring puzzle (Figure 48). The sequence shown indicates how the original linked ring configuration can be deformed to an unlinked ring figure.

Here is one way to make a link:

• make a knot out of a piece of rope
• take a second piece of rope and pass it through at least one of the loops of the first knot
• make a knot out of that second piece of rope

When you make a link, you can use as many pieces of rope as you like, adding a new knot to the link each time you add another piece of rope.

In order to turn a link into two or more separate (un-linked) knots, you have to cut the rope. The number of times you would have to cut the rope to do this is called the link number. The link number can be thought of as a measure of how "linked up" the knots are.

When a braid is built from a series of components, the way that the ends are joined determines whether the resulting braid is a knot or a link. What determines the link number?

Every knot is a closed circular braid. Is every link a nice orderly pile of closed circular braids?

Braids and Knots

Because braids are strands of rope, fiber, hair, etc that are twisted together with the strands going under and over, it is not surprising that knot theorists study braids and think about knots in terms of braids.

Just like knots, braids must be finished off for mathematical consideration so that there are no loose ends that could move and change the braid (or unravel it completely) while it is being studied.

Also since braids can be arbitrarily long and quite complicated, it helps to think of them as being made from smaller parts or components.

Components of Braids

A braid is build from simpler units that mathematicians call components. Each unique way of crossing the strands of a braid is called a component.

In the real world, people braid rope to make it stronger, they braid their hair to make it look nice and keep it from flying about in the wind, or they may braid strands of fiber to make friendship bracelets or other attractive weavings. Do you know how to do any of these kinds of braiding? Can you list the components of a type of braid you know how to make? Listing the components is actually a good way to give directions for how to make the braid.

Perhaps you noticed that there is a pattern to the list of components for a braid to strengthen rope, make someone's hair look nice, or produce a weaving. You could invent ways to make such braids without a pattern, but the rope might not be as strong as it could be, and the hair or the weaving might look kind of random, knotted and strange. When mathematicians are studying braids and knots, however, there is not such a need to be limited to braids that show obvious patterns. Instead, all imaginable braids are of interest.

Think about this:

• Can two components of a braid cancel each other if they are put next to each other?
• Can two different components combine to form a third?
• In what ways is adding braid components together the same as adding knots? In what ways is it different?              
• Every Knot is a Closed Circular Braid

Every knot is a closed circular braid. This is a famous theorem of knot theory . But what does it mean?

It means that no matter how twisted, complex and entangled a knot might be, no matter how many crossings it has, the strands of rope can be rearranged into a single braided coil. When the knot is arranged this way and you follow the strand of rope all the way around, it will make a series of circles that cross over and under each other's strands. Every circle has the same center, there is no backtracking, and there are no extra loops.

Try reshaping some of the knots on the sheet of knot diagams into closed circular braids. For some knots, it is easy. For others it is not.

Make a huge and ridiculously complex knot out of a large piece of rope and try to rearrange it into a closed circular braid. It is possible. But why???

Because every knot is a closed circular braid, it is possible to describe any knot by listing the braid components., telling the order of their appearance, and telling how the ends are joined.

Try describing some of the knots in the sheet of knot diagrams as closed circular braids, and see if you think that this kind of description is useful for classifying knots and telling them apart.

 본 강의에서는 매듭이론에서의 기본적 용어에 대하여 알아보고, 다양한 매듭의 모양을 구별하여 본다.