Graph (mathematics)

Real-world example of a graph: The central part of the London Underground map.

In mathematics, a graph is used to show how things are connected. The mathematical study on graph is called graph theory. The things being connected are called vertices, and the connections among them are called edges. If vertices are connected by an edge, they are called adjacent. The degree of a vertex is the number of edges that connect to it. A graph's size [math]\displaystyle{ |E| }[/math]is the number of edges in total. The number of vertices, written as [math]\displaystyle{ |V| }[/math], is called the order of a graph.

Edges may have weights, which show the costs associated with using each edge. In a graph of cities on a map, the cost may be the distance between two cities, or the amount of time it takes to travel between the two.

Directed graphs go in one direction, like water flowing through a bunch of pipes. Undirected graphs don't have a direction, like a mutual friendship. A graph where there is more than one edge between two vertices is called multigraph. One where there is at most one edge is called a simple graph. A simple graph, where every vertex is directly connected to every other is called complete graph. A loop is an edge that connects to its own vertex. Loops are only allowed in multigraphs.

A sequence of edges is called a path. A path which starts and ends at the same edge is called a cycle.

• 

  An undirected graph with six vertices and seven edges.

• 

  A directed graph with a cycle

• 

  A directed graph, without a cycle

• 

  Undirected graph, with the cycle highlighted in red

• 

  A multigraph with multiple edges (red) and several loops (blue). Not all authors allow multigraphs to have loops.

• 

  A graph with a loop on vertex 1. Vertex 1 has a degree of 4, vertices 2,4,5 have a degree 3, vertex 3 has a degree of 2, and vertex 6 has a degree of 1

• 

  A complete graph with 5 vertices