Graph Theory Glossary

This series of definitions and discussions uses mathematical language, and is intended to set forth as precisely as possible the conceptual terminology used within the mathematical side of Manifold.

Changes in Nomenclature

Manifold System versions before Release 3.00 use the standard mathematical terminology of graph theory. Manifold releases from Release 3.00 onward use a more commercial, relaxed style of language that is drawn from networking industry terminology.

The following table shows changes in terminology that have occurred throughout menu systems, command names, and the non-mathematical portions of Manifold System documentation. Note that the more technical and more mathematical parts of Manifold documentation have not been rewritten using the simpler terminology, nor have the technical names of Manifold functions used within scripts or C++ programming.

Previous	New
graph	network
vertex	node
edge	link
articulation points	critical points
isthmuses	critical links
oriented network	directed network
unoriented network	undirected network
Hamilton cycle	Loop through all Nodes
Euler cycle	Loop through all Links
Euler chain	Path through all Links
chain	path
cycle	loop

Our motivation for making these changes has been to make Manifold and the practical utilization of graph theory more usable by a wider audience. We feel that whereas mathematicians will immediately know that a "path through all links" is an Euler chain, very few computer users would recognize the term "Euler chain". If we use the terminology "path through all links" then everyone knows what it is all of the time.

Graph Theory Glossary

Directed Graph

A graph in which every edge is associated with an ordered pair of vertices. Since an ordered pair of vertices implies a sense of direction from one vertex to another, that means that for two vertices u and v the vertex pairs (u,v) and (v,u) are considered to be different pairs. The edges of directed graph are often referred to as arcs, while the term edge is used to describe undirected graphs. Vertex u of the arc (u,v) is called the origin and vertex v is called the end of the arc. Figure 1.3.1 shows a directed graph with vertices 1, 2, 3, 4 and arcs a, b, c, d, e.

$images\fig_131.gif$

Fig. 1.3.1

Undirected Graph

A graph in which every edge is associated with an unordered pair of vertices. For undirected graphs the vertex pairs (u, v) and (v, u) are considered to be the same pair. In Figure 1. 3. 2 vertices 2 and 3 are joined by two edges b and c.

$images\fig_132.gif$

Fig. 1.3.2

Simple Graph

An undirected graph without self-loops or multiple edges. A simple graph, G, could be defined as a pair of sets (V, E), where V is a set of vertices and E is a set of edges, with each edge running between a non-ordered pair of distinct vertices. (see fig 1.3.3)

$images\fig_133.gif$

Fig. 1.3.3

Multigraph

A graph in which multiple edges exist. Figure 1.3.2 is a multigraph in addition to being an undirected graph.

Weighted Graph

A weighted graph has one or more numbers associated with each edge. The numbers are called edge weights and the graph is said to have weighted edges. Like edges, vertices may also be weighted. A graph in which every vertex is associated with one or more numbers, called vertex weights, is referred to as graph with weighted vertices. Edge weights are often used to represent some physical parameter of interest in applications of graph theory. For example, Figure 1.3.4 shows a graph that represents a system of roads between vertices A, B, C, D, and E, where the numbers attached to each edge, the edge weights, represent the length in kilometers of that edge.

$images\fig_134.gif$

Fig. 1.3.4

Vertex Adjacency

Two graph vertices are adjacent if there is an edge joining the vertices. For example, vertices 1 and 3 in the graph shown in Figure 1.3.1 are adjacent, while in the graph from Figure 1.3.2 these vertices are not adjacent. A set of vertices adjacent to a given vertex is called the neighborhood of that vertex.

$images\fig_131.gif$

Fig. 1.3.1 (repeated)

Edge Adjacency

Two graph edges are adjacent if they have a vertex in common. For example, in the graph shown in Figure 1.3.1, the edge a is adjacent to each of the edges b, c, and d but is not adjacent to the edge e. In the graph, shown in Figure 1.2.3, all edges are adjacent to each other, excluding e, which is adjacent only to a.

Incidence

An edge is incident to a vertex if the vertex is at one end of the edge. A vertex is incident to an edge if that edge is incident to the vertex. In the graph shown in Figure 1.3.1, vertex 3 is incident to edges b, c, d, e.

Arc

An edge in a directed graph. By definition, an arc is associated with an ordered pair of vertices (a, b). Vertex a is called the origin and vertex b is called the end of the arc. An arc is said to leave vertex a and come in to vertex b.

Self-loop

An edge associated with a pair of vertices of the form (a, a). A more intuitive definition is that a self-loop is an edge between a vertex and the same vertex. Figure 1.3.2 shows a self-loop at vertex 1.

$images\fig_132.gif$

Fig. 1.3.2 (repeated)

Vertex Degree

The number of edges incident to a given vertex. Each vertex in a directed graph has both an indegree, the number of edges coming in to the vertex as well as an outdegree, the number of edges going out of the vertex. Let’s point out vertex degrees for the graph shown in Figure 1.3.5:

$images\fig_135.gif$

Fig. 1.3.5

vertex	degree	indegree	outdegree
1	2	0	2
2	3	2	1
3	3	2	1
4	2	1	1

Complete Graph

A graph containing all varieties of edges which are allowed in that type of graph. In a simple complete graph every pair of vertices is joined by an edge. This kind of graph is denoted as Kn where n is the number of vertices. In a directed complete graph any two vertices are joined by two opposite directed edges. If self-loops are acceptable, then there is a self-loop at every vertex in a complete graph. Figure 1.3.6 a shows a complete undirected graph with five vertices, Figure 1.3.6 b shows a complete oriented graph with three vertices. Both of them have no self-loops

$images\fig_136a.gif$

Fig 1.3.6 a

$images\fig_136b.gif$

Fig. 1.3.6 b

Empty Graph

A graph with no edges. An empty gray with n vertices is written On. Figure 1.3.7 shows an empty graph with three vertices.

$images\fig_137.gif$

Fig. 1.3.7

Bipartite graph

A bipartite graph is a simple graph where the set of vertices can be separated into two subsets, called parts, so that every edge in the graph joins vertices from separate parts. For example, Figure 1.3.8 shows a simple graph which is also a bipartite graph because it may be divided into two parts, given by the subsets {1, 2} and {3, 4, 5}, where every edge in the graph goes from a vertex in one part to a vertex in the other part.

$images\fig_138.gif$

Fig. 1.3.8

Complete Bipartite Graph

A bipartite graph in which every vertex in one part is connected with every vertex in the other part. A complete bipartite graph in which one part consists of p vertices while the other part consists of q vertices is denoted as Kp,q. Figure 1.3.9 shows the graph K2,3. It also could be denoted as K3,2.

$images\fig_139.gif$

Fig. 1.3.9

Star

A complete bipartite graph with only one vertex in one part and one or more vertices in the other part. If n is the number of vertices in the other part, we may use the nomenclature K1, n to refer to a star. The edges of a star are called beams. Figure 1.3.10 shows a star K1, 4.

$images\fig_1310.gif$

Fig. 1.3.10

Route

A route is sequence of elements of the type v0, e1, v1, e2, ..., ek, vk, where v0, v1, v2, ... are vertices and e1, e2, ... are edges in the graph so that edge ei runs between vertices vi-1 and vi for all i = 1, ..., k. A route begins at the vertex v0 and then continues through an edge incident to that vertex and on to the next vertex, the next edge, and so on to the last vertex, vk.

A route is said to pass through the vertices v0, v1, ..., vk and pass along the edges e1, ..., ek. A route joins vertices v0 and vk . The number, k, of vertices in the route is called the length of the route.

Recall that directed graphs are graphs in which the edges are oriented, in that they run from an origin vertex to an end vertex. In a directed graph a route is referred to as a directed route if for every i from 1 to k, vertex vi-1 is the origin of edge ei while vi is the end of that edge ei.

Said in more ordinary language, a directed route is a route in a directed graph where all the edges in the route from the first vertex to the last vertex are oriented "the right way" to continue on in sequence from the first vertex in the route to the last. In this case vertex vk is said to be reachable from the vertex v0 . Think of directed graphs as connecting vertices with "one way" streets, and a directed route from v0 to vk must run along the right sequence of "one way" streets and vertices so that vk is reachable from v0.

In a graph without multiple edges a route could be given as a sequence of vertices, since in such graphs there is only one edge between any pair of vertices.

The sequence v3, e1, v1, e2, v4, e5, v2, e6, v5, e3, v1, e2, v4. is an example of a route in the graph shown in Figure 1.3.11. Notice, that edge e2 is passed twice.

$images\fig_1311.gif$

Fig. 1.3.11

Path

A path is a route with different edges. A path with different vertices is called a simple path. For example, the sequence 1, a, 2, e, 4, f, 3, d, 2 is a paths in the graph shown in Figure 1.3.12. Note that in the path edges e, f and d are passed against their oriented direction. This path is not simple, since vertex 2 is passed twice.

$images\fig_1312.gif$

Fig 1.3.12

Directed Path

A directed path is a path in a directed graph such that the origin of the next edge coincides with the end of the previous one. In the graph shown in Figure 1.3.12, for example, the sequence 1, b, 2, d, 3, f, 4, e, 2 comprises a directed path. The same path could be represented as the sequence of edges b, d, f, e.

Chain

This word is used in two meanings. The first meaning is as a synonym for path.

The second meaning defines a type of simple graph which may be diagrammed akin to an open strand of pearls: A chain is a simple graph with a set of vertices {1, 2, ..., n} and a set of edges {(i, i + 1): i = 1, ..., n - 1}. [Or, in plain language, the set of edges defined by the vertex pairs (i, i + 1) for all the vertex pairs from (1, 2), (2, 3) and so forth up to (n-1, n)]. Such a chain is denoted as Pn. Figure 1.3.13 shows a chain P4.

$images\fig_1313.gif$

Fig. 1.3.13

Cycle

A loop, that is, a path in which the first and the last vertices are the same. A cycle is said to be simple if all of its vertices are different, that is, if a vertex is not repeated.

Just like the word chain, this word has a second, somewhat analogous meaning: a cycle is a simple graph with a set of vertices {1, 2, ..., n} where n ³ 3 and a set of edges {(i, i +1) : i = 1, ..., n - 1} È {(n, 1)}, denoted as Cn. Perhaps a more intuitive definition is that linking the last vertex of a chain to the first vertex creates a cycle, which may be diagrammed akin to a closed strand of pearls. The set notation used earlier in this paragraph to define a cycle is simply a way of describing that set of edges which comes about from the union of the set of edges that form a chain and the edge defined by the pair of vertices consisting of the last vertex (the nth vertex) and the first vertex, vertex 1.

In the graph shown in Figure 1.3.14 a, cycles are represented, for example, by sequences of vertices 1, 5, 4, 2, 3, 4, 1 and 1, 2, 3, 4, 5, 1. The first cycle is not simple whereas the second cycle is simple.

Figure 1.3.14 b shows a simple graph which illustrates an example of the second meaning of the word cycle in the form of the cycle C5.

$images\fig_1314a.gif$

Fig. 1.3.14 a

$images\fig_1314b.gif$

Fig. 1.3.14 b

Tree

A connected graph with no cycles (see. fig. 1. 3. 15).

$images\fig_1315.gif$

Fig. 1.3.15

Forest

A graph with no cycles. Every connected subnet of the forest represents a tree.

Directed Cycle

A cycle in a directed graph such that the end of every edge coincides with the origin of the next edge. For example in the graph shown in Figure 1. 3. 12, cycles 2, d, 3, f, 4, e, 2 and 1, b, 2, a, 1 are directed cycles. The same cycles could be represented as sequences of vertices 2, 3, 4, 2 and 1, 2, 1, and as sequences of edges d, f, e and b, a.

Circuit

The same as directed cycle.

Acyclic Graph

A directed graph with no directed cycles (see. fig. 1. 3. 16)

$images\fig_1316.gif$

Fig. 1.3.16

Hamiltonian Cycle or Hamiltonian Path

A simple cycle or path that traverses all graph vertices. There are no Hamiltonian cycles in the graph shown in Figure 1. 3. 3. In Figure 1. 3. 4 the sequence of vertices A, B, C, D, E, A specifies a Hamiltonian cycle.

$images\fig_134.gif$

Fig. 1.3.4 (repeated)

Euler Cycle

A cycle that passes all the edges of the graph, traversing each edge just once. For a graph which is different from the cycle C n, (that is, a simple cycle which ends at its own beginning), the Euler cycle is not a simple cycle. The graph shown in Figure 1. 3. 4 has no Euler cycle, while the graph, shown in Figure 1. 3. 6, contains an Euler cycle, represented by the sequence of vertices 1, 2, 3, 5, 4, 1, 3, 4, 2, 5, 1.

Subgraph

A graph G1 is called a subgraph of graph G2, if every vertex of the first graph is a vertex in the second graph, every edge of the first graph is an edge in the second graph, and every edge of the first graph joins the same vertices as it does in the second graph. The graph shown in Figure 1.3.17b is a subgraph of the graph shown in Figure 1.3.17a.

$images\fig_1317a.gif$

Fig. 1.3.17 a

$images\fig_1317b.gif$

Fig. 1.3.17 b

Spanning Subgraph

A subgraph G1 of the graph G2 is said to be a spanning subgraph of G2 if the sets of their vertices coincide. Figure 1.3.18 shows a graph with three spanning subgraphs.

$images\fig_1318a.gif$

Fig. 1.3.18 a

$images\fig_1318b.gif$

Fig.1.3.18 b

$images\fig_1318c.gif$

Fig. 1.3.18 c

$images\fig_1318d.gif$

Fig. 1.3.18d

Induced Subgraph

A subgraph G1 of the graph G2 is said to be induced by some subset of vertices X, if the set of its vertices coincide with X, and any edge in G2 with ends belonging to X, is an edge in G1.

Taking the graph in Figure 1.3.19a, the set of vertices {1, 2, 3, 4} induces the subgraph shown in Figure 1.3.19b.

$images\fig_1319a.gif$

Fig. 1.3.19 a

$images\fig_1319b.gif$

Fig. 1.3.19 b

Connected Graph

A graph in which every two vertices are joined by a route. Figure 1.3.20a shows a connected graph, while the graph shown in Figure 1.3.20b is not connected, for there is no route joining, for example, vertex 1 with vertex 5.

$images\fig_1320a.gif$

Fig. 1.3.20 a

$images\fig_1320b.gif$

Fig. 1.3.20 b

Strongly Connected Graph

A directed graph in which there is a directed route from every vertex to every other vertex. Figure 1.3.21a shows a strongly connected graph while the graph shown in Figure 1.3.21b is not strongly connected.

$images\fig_1321.gif$

Fig. 1.3.21

Connected Component

A connected component is a connected subgraph which is not part of any larger connected subgraph. Such a connected subgraph is also said to be a maximum connected subgraph, For any two vertices belonging to the same component there is a path joining them, while there is no such path between vertices from different components. The graph shown in Figure 1.3.22 has three connected components - they are induced by the sets of vertices {1, 2, 3, 4}, {5, 6}, and {7}.

$images\fig_1322.gif$

Fig. 1.3.22

Strongly Connected Component

Any maximum strongly connected subgraph, that is a subgraph which is not part of any larger strongly connected subgraph. In a strongly connected component, for any two vertices a and b belonging to the same component, there is a directed path from a to b, and a directed path from b to a as well. For vertices from different components at least one of these two paths does not exist. For the graph shown in Figure 1.3.23, subgraphs induced by the sets {1, 6}, {2, 3, 4} and {5} are strongly connected components,

$images\fig_1323.gif$

Fig. 1.3.23

Isthmus

An isthmus is an edge of a graph which if deleted would decrease the number of connected subnets. Both graphs shown in Figure 1.3.14, have no isthmuses, while edges (3, 6), (2,4), (4,5), and (4,9) in the graph shown in Figure 1.3.24 are isthmuses.

$images\fig_1324.gif$

Fig. 1.3.24

Leaf

A graph with no isthmuses. For example, both graphs shown in Figure 1.3.14 are leaves.

Graph Leaves

An induced connected subgraph with no isthmuses which is not the part of any larger subgraph with identical features. In Figure 1.3.24, the subgraphs induced by the sets of vertices {1, 2, 3, 10}, {4}, {5}, {9}, and {6, 7, 8}, are leaves.

Articulation Point

A vertex of a graph, which if deleted along with any incident edges would increase the number of connected subnets. There are four articulation points in the graph shown in Figure 1. 3. 24, vertices 2, 3, 4, and 6. Note that some authors refer to articulation points as cutpoints.

Block

A graph with no articulation points. For example, both of the graphs in Figure 1. 3. 14 are blocks.

Graph Block

An induced connected subgraph with no own articulation points which is not the part of any larger subgraph with identical features. A block can hold a single vertex (vertex 7 in fig. 1. 3. 22) or two adjacent vertices (vertices 5 and 6 in the same figure). When a block holds more then two vertices, there must be a simple cycle through any two vertices, while there is no such a cycle for the vertices from different blocks. The graph shown in Figure 1. 3. 24 has blocks induced by the sets of vertices {1, 2, 3, 10}, {2, 4}, {4, 5}, {4, 9}, {3, 6}, and {6, 7, 8}.

Connectivity Number

In an undirected graph the minimum number of vertices or edges to be deleted from the graph so that it is not connected is called the vertex or edge connectivity number, respectively. In the case of a directed graph the vertex or edge connectivity number is the number of vertices or edges, respectively, to be deleted so that the graph is no longer strongly connected. For convenience, we may simply use the term "connectivity" instead of "connectivity number."

The vertex connectivity for the graph shown in Figure 1.3.25 is 2. Deleting vertices 1 and 6 makes the graph non-connected, while deleting any single vertex keeps the graph connected. The edge connectivity of this graph is 3, for there are three edges that if deleted would make the graph no longer connected, for example, edges (2, 1), (2, 3), (2, 6), but deleting any two edges does not break connectivity.

Note that the vertex and edge connectivity of a disconnected unoriented graph (or non-strongly connected oriented graph) is 0, while both vertex and edge connectivity are 1 or more in a connected unoriented graph (or strongly connected oriented graph).

$images\fig_1325.gif$

Fig. 1.3.25

Graph Clique

A maximum complete subgraph, or simply subgraph, which is not a part of any larger complete subgraph. The graph shown in Figure 1. 3. 26 has three cliques induced by the sets of vertices {1, 2}, {1, 3, 5}, and {3, 4, 5, 6}.

$images\fig_1326.gif$

Fig. 1.3.26

Graph Clique Number

The maximum size (that is, the maximum number of vertices) of a graph clique. The clique number of the graph shown in Figure 1.3.26 is 4.

Independent Set of Graph Vertices

A set of vertices which are nonadjacent in pairs. In more ordinary language, a set of vertices where any two vertices taken from the set are not adjacent. Examples of independent sets in the graph shown in Figure 1.3.27 are the sets {1,4}, {1, 5, 6}, and {2, 3, 5, 6}.

$images\fig_1327.gif$

Fig. 1.3.27

Independence Number

The maximum size of an independent set of a graph. For example, the independence number of the graph shown in Figure 1.3.27 is 4.

Matching

A set of edges which are nonadjacent in pairs. In more ordinary language, a set of edges where any two edges taken from the set are not adjacent. For example, in the graph shown in Figure 1.3.28 a possible matching is {(1,2), (3,6), (4,5)}.

$images\fig_1328.gif$

Fig. 1.3.28

Coloring of Graph Vertices or Edges

A coloring of the vertices (or edges) of a graph is the partitioning of the set of graph vertices (or edges) into subsets. A coloring is said to be a proper coloring if no two vertices in the same subset are adjacent. In more ordinary language, a proper vertex coloring is the arrangement of a set of vertices into subsets of vertices so that for any two vertices taken from the same subset there is no edge that connects them. For edges, a proper coloring organizes the edges into subsets so that any two edges taken from the same subset do not have a vertex in common. The subsets specified in colorings are referred to as colors.

Thus we can say in a proper vertex coloring no two vertices (or two edges, in the case of edge coloring) of the same color are adjacent. If the coloring is proper, the set of vertices of the same color in a vertex coloring is independent, and the set of edges of the same color in an edge coloring makes up a matching.

Although the terminology "coloring" is that of partitioning into sets, the non-mathematical meaning of the word "color" is a useful way of visualizing the assignment of vertices or edges into different sets: take a graph and paint each edge so that no edge is ever the same color as an adjacent edge, and you have a proper edge coloring. Obviously, this is easily done if each edge is a different color: the task normally is finding the smallest number of colors which need to be used to achieve a proper coloring.

The vertices of the graph shown in Figure 1.3.29 may be properly colored in four colors: the first color for vertex 1, the second color for vertices 2, and 7, the third color for vertices 4, and 5, and the fourth color for vertices 3, and 6. Note that three colors are insufficient for the proper coloring of this graph. Figure 1.3.30 shows a proper coloring of edges in three colors with the color number pointed out at each edge. Note that it is impossible to properly color the edges of this graph with fewer than three colors since there are three edges incident to vertex 1; therefore, at least three different colors must be used.

$images\fig_1329.gif$

Fig. 1.3.29

$images\fig_1330.gif$

Fig. 1.3.30

Graph Chromatic Number or Chromatic Class

The minimum number of colors required for a proper coloring of vertices (chromatic number) or edges (chromatic class). The chromatic number of the graph shown in Figure 1.3.29 is 4, while the chromatic class of the graph shown in Figure 1.3.30 is 3.

Graph Isomorphism

The simple graphs G1 and G2 are isomorphic if there is one-to-one correspondence between their sets of vertices which preserves vertex adjacency. For directed graphs the one-to-one correspondence must preserve adjacency while also preserving relative origins and ends of edges.

Figure 1.3.31 b, c, and d shows three graphs which are isomorphic in pairs. The graph shown in Figure 1.3.31 a is not isomorphic to them.

$images\fig_1331a.gif$

Fig. 1.3.31 a

$images\fig_1331b.gif$

Fig. 1.3.31 b

$images\fig_1331c.gif$

Fig. 1.3.31 c

$images\fig_1331d.gif$

Fig. 1.3.31 d

Complementary Graph

The complementary graph to a simple graph, G, is the graph $images\ebx_-65343451.gif$ with the same set of vertices, such that two vertices are adjacent if and only if they are not adjacent in G. Figure 1.3.32 shows a graph and its complementary graph.

$images\fig_1332.gif$

Fig. 1.3.32

Standard notation for various types of graphs

P n - chain with n vertices;

Cn - cycle of length n;

On - graph with n vertices and no edges (empty graph);

Kn - complete graph with n vertices;

Kp,q - complete bipartite graph with parts of size p and q.