The Four-Color Theorem and Basic Graph Theory by McMullen Chris

Author:McMullen, Chris [McMullen, Chris]
Language: eng
Format: epub
Publisher: Zishka Publishing
Published: 2020-05-24T16:00:00+00:00

Let’s apply Kirchhoff’s loop rule to the closed loop shaded gray above:

• Let’s begin at the vertex colored 2 and travel clockwise.

• Going from 2 to 4, the color difference is 4 – 2 = 2.

• Going from 4 to 1, the color difference is 1 – 4 = –3.

• Going from 1 to 4, the color difference is 4 – 1 = 3.

• Going from 4 to 1, the color difference is 1 – 4 = –3.

• Going from 1 to 2, the color difference is 2 – 1 = 1.

• The sum of these color differences is: 2 + (–3) + 3 + (–3) + 1 = 6 – 6 = 0.

Note that we have only defined one sort of circuit element with a property called color difference. If you want to think about three properties (like resistance, current, and voltage, or like charge, capacitance, and voltage), you will need to develop more than just color difference.

One way to introduce the concept of charge to a graph is to literally sprinkle charges on the vertices, edges, or faces. (Placing a positive charge at each vertex and inside each face and a negative charge along each edge, where the charges are equal apart from the signs, one can prove that Vq + Fq = Eq + 2q, which reduces to Euler’s formula, V + F = E + 2. One way to do this is to show that all of the charges cancel except for the charges at two of the vertices. Challenge problem 2 of this chapter asks you to do this.)

Another example that applies the concept of charge to graph theory is the process of discharging used in Appel and Haken’s computer-assisted proof of the four-color theorem [14] (Appel and Haken’s proof is mentioned briefly in Chapter 28, but to learn about the discharging process, you’ll need to read their paper).

(If you wish to learn more about Kirchhoff’s rules for electric circuits, consult a standard introductory physics textbook. The second volume typically covers electricity and magnetism with some chapters on circuits. The author’s Essential Physics Study Guide Workbooks , Volume 2, include a chapter on Kirchhoff’s rules.)

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.