Graph (mathematics)
In graph theory a graph is used to represent the connection between two sets. One of the sets contains nodes (which are officially called vertices), the other one contains the connections (which are officially called edges). There are two classes of graphs, which are distinguished by the nature of the edges. Some edges can be travelled in both directions, other can only be travelled in one direction. Edges that can be travelled in one direction only are called directed, and the graph is called a directed graph or digraph. The ones which do not have a direction are called undirected, and the graph is called an undirected graph. If two vertices are connected by an edge, they are called adjacent.
The order of a graph, written as [math]\displaystyle{ |V| }[/math], is given by the number of vertices. A graph's size is [math]\displaystyle{ |E| }[/math], the number of edges. The degree of a vertex is the number of edges that connect to it, where an edge that connects to the vertex at both ends (a loop) is counted twice.
Vertices or edges may have weights. In general, weigts are used to show the costs associated with using the respective vertex or edge. In a graph that shows the cities of a region, the cost associated with a vertex may be the distance between two cities, or the amount of time it takes to travel between the two.
A graph were 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 loop is an edge that connects to the same vertex. Loops are only allowed in multigraphs.
A simple graph, where every vertex is directly connected to every other is called complete graph.
A sequence of vertices where two vertices which are next to each other in the sequence are connected by an edge is called a path.
A path which starts and ends at the same edge is called a cycle. The directed graph below with a cycle has the paths BCEDB, CEDBC, EDBCE andDBCED which are cycles.
-
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
