Graph Theory

Author:              Zhiming Ou

                         Mattermatics Learning Center

Publisher:       3265 Public Way

ISBN:978-1-0677109-0-3

 

Summary

Graph theory is widely used in real life: (1) Internet and computer networks (2) GPS and route planning, (3) Biology (gene/neuron networks), (4) Social networks, and (5) Electrical circuits. At its core, graph theory is about answering this question: How are things connected, and what can we do with those connections?

There are some classic problems in graph theory, such as shortest path problem (e.g., Dijkstra’s algorithm), Traveling salesman problem, Eulerian paths and Hamiltonian cycles, and map coloring. By solving these problems, people can understand the positional relationship between objects.

 

Content

Chapter 1 Introduction        2

The Konigsberg Seven Bridge Problem        3

The Four-Color Problem         4

Matching         5

 

Chapter 2 Undirected Graphs      8

• 2.1 Components and Types of Graphs 9
• 2.2 Describe a Graph Quantitatively 13

Adjacency Matrix    

• 2.3 Isomorphic and automorphic Graphs 15

 

Chapter 3 Eulerian and Hamiltonian Graphs         18

• 3.1 Euler Circuits and Euler Graphs 18

Dijkstra’s Algorithm

• 3.2 Hamiltonian Circuits 23

 

Chapter 4 Planar Graphs and Map Coloring       30

• 4.1 Planar Graphs 30
• 4.2 Map Coloring and the Five Color Theorem 35
• 4.3 Dual Graphs 37

 

Chapter 5 Trees       39

• 5.1 Definition and Properties 39
• 5.2 Spanning Trees 40

 

Chapter 6 Directed Graphs and Shortest Route      44

• 6.1 Examples and Definitions 44
• 6.2 Finding the Shortest Route 45

 

Chapter 7 Graph Coloring        49

• 7.1 Edge Coloring 49
• 7.2. Ramsey Theory 51
• 7.3 Vertex Coloring 56