Graph theory

Graph theory is a branch of mathematics concerned with points and lines. It is not the study of charts, such as bar graphs, as its name suggests. In this branch of mathematics, points are called vertices (V), and lines that connect points are called edges (E). Graph theory considers the ways in which vertices can be connected by edges.

Graph theory is often used in the fields of engineering and computer science. Engineers use it extensively to design circuit connections. Computer programmers use graph theory in the study of algorithms, which are rules to be followed to solve problems. Graph theory is also used to display the flight networks between cities and to show the chemical and molecular structure of a substance.

Background

Graph theory began in 1735 when Leonhard Euler, a Swiss mathematician, solved a puzzle called the "Kӧnigsberg bridge problem." The city of Kӧnigsberg, which was then in Germany, had seven bridges that crossed the river Preger. The bridges connected two islands with the mainland. For many years, people had wondered if there was a way to cross all the bridges only once. Euler used graph theory to solve the problem. Using dots and lines to represent the bridges and landmasses, he drew a graph that proved it was impossible to cross all the bridges just once. In his graph, every landmass was represented by a vertex (dot), and every bridge was represented by an edge (line) connecting the two points. Because the graph he drew had vertices connected to an odd number of edges—as opposed to an even number of edges—it showed that it was impossible to cross a bridge only once.

Overview

Graph theory is the study of graphs consisting of points (vertices) and lines (edges). Graph theory is often used to determine the ways in which vertices can be connected by edges. The traveling salesman problem (TSP) is a classic example of how graph theory can be used in business. The parameters of this example are as follows: The participant is given a set of cities and the distance between the cities. He must start and end the trip in his home city. He must visit each city exactly once. To solve the TSP, he must determine the shortest route from city to city.

The four-color theorem is another famous problem related to graph theory. The objective is to prove that only four colors are needed to color any map of countries so that no two adjacent countries are the same color. Using graph theory, every country is converted to a vertex. Whenever there is a border between two countries, their vertices are connected with an edge. Then vertices connected by an edge are colored in different colors—and just four colors are needed.

Real-world applications of graph theory include mapping the evolution of animals and languages and the spread of disease. Graph theory is used to represent road and flight networks. It is also used to design computer chips, tiny modules that contain memory and logic circuitry. Computer chips contain integrated circuits (ICs), which have millions of transistors that need to be connected. Graph theory is used to show the ways in which these transistors can be connected so the best connections are found, and the chip performs at its best.

Basic Terms

In graph theory, a graph is a diagram consisting of points and lines connecting the points. A vertex, or node, is a point where more than one line meets. In a diagram, vertices are usually labeled with letters, such as vertex a and vertex b.

An edge is a line that connects two vertices. An edge looks like a straight line with a dot at each end. If an edge is drawn from a vertex and back to the same vertex, it is called a loop. If an arch is drawn above an edge and connects the same two vertices, they are called parallel edges—even though the arch and the edge are not parallel. A vertex in a graph that is not connected by an edge is called an isolated vertex. Suppose a square has a vertex at each corner and a vertex in the center, which is not connected to an edge. It is an isolated vertex.

Graphs

A graph is a diagram in which all vertices are connected by lines. The following are some basic graphs:

• A graph with vertices but without edges is called a null graph.
• A graph with only one vertex and no edges is called a trivial graph.
• A simple graph has no loops or parallel edges. A two-dimensional square with four vertices and four edges is a simple graph.

When one pair of vertices is joined by more than one edge, it is called a multi-graph. A square with four vertices and three edges and one set of parallel edges is a multi-graph.

In a complete graph, each vertex is connected to every other vertex. Imagine a square with four vertices and four edges. Now imagine two diagonal lines in the square forming an X. Each vertex in the square is connected to every other vertex. The same is true of a triangle with three vertices and three edges. It is a complete graph because each vertex is connected to every other vertex.

A directed graph has arrows on the edges to indicate direction, or path. An undirected graph does not have arrows indicating direction.

Degree of Vertex

Each vertex has a number assigned to it called degree. This is not the same as the degree of an angle in geometry. In graph theory, a vertex's degree is the number of edges that enter and exit from it. In the example of the square consisting of four vertices and four edges, each vertex has a degree of two because one edge enters it and a second edge exits it. In the example of a square consisting of four vertices and four edges and two diagonal lines forming an X, each vertex has a degree of three because three edges either enter or exit it.

A vertex can be connected by an edge with any vertex in a graph except itself. This means that the highest a vertex's degree can be is the number of vertices in a graph minus one.

Bibliography

Adamchik, Victor. "Graph Theory." Carnegie Mellon University, www.cs.cmu.edu/~adamchik/21-127/lectures/graphs‗1‗print.pdf. Accessed 19 May 2017.

Benjamin, Arthur, and Gary Chartrand. The Fascinating World of Graph Theory. Princeton UP, 2017.

Carlson, Stephen, C. "Graph Theory." Britannica, 8 Nov. 2024.

Deo, Narsingh. Graph Theory with Applications to Engineering and Computer Science. Dover Books of Mathematics, 2016.

"Graph Theory." Mathigon, world.mathigon.org/Graph‗Theory. Accessed 19 May 2017.

"Graph Theory." OpenCourseWare, Massachusetts Institute of Technology, ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6‗042JF10‗chap05.pdf. Accessed 19 May 2107.

Klarreich, Erica. "Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem." Wired, 30 Jan. 2013, www.wired.com/2013/01/traveling-salesman-problem/. Accessed 19 May 2017.

Rodrigue, Dr. Jean-Paul, and Dr. Cesar Ducruet. "Graph Theory: Definitions and Properties." The Geography of Transport Systems, Hofstra University, people.hofstra.edu/geotrans/eng/methods/ch1m2en.html. Accessed 19 May 2017.

Trudeau, Richard. Introduction to Graph Theory. Dover Books of Mathematics, 1994.