Graph’s definition. Basic Consepts

 

Informally, a graph is a set of objects in which some of the objects are connected to each other in some way. The objects are called vertices or nodes, and the connections are called edges. For example, the United States can be represented by a graph where the vertices are states and the edges are the common borders between adjacent states. In this case, Hawaii and Alaska would be vertices without any edges connected to them. We say that two vertices are adjacent if there is an edge connecting them.

We can picture a graph in several ways. For example, Figure 3.1 shows two ways to represent the graph with vertices 1, 2, and 3 and edges connecting 1 to 2 and 1 to 3.

 

              

 

Figure 3.1

 

Let's do another example. Figure 3.2 represents a graph of those states in the United States and those provinces in Canada that touch the Pacific Ocean or that touch states and provinces that touch the Pacific Ocean.

 

Figure 3.2

 

An interesting problem dealing with maps is to try to color a map with the fewest number of colors subject to the restriction that any two adjacent areas must have distinct colors. From a graph point of view, this means that any two distinct adjacent vertices must have different colors.

A graph is n-colorable if there is an assignment of n colors to its vertices such that any two distinct adjacent vertices have distinct colors. The chromatic number of a graph is the smallest n for which it is n-colorable. For example, the chromatic number of the graph in Figure 3.2 is 3. A graph whose edges are the connections between all pairs of distinct vertices is called a complete graph. It's easy to see that the chromatic number of a complete graph with n vertices is n.

A graph is planar if it can be drawn on a plane such that no edges intersect. For example, the graph in Figure 3.2 is planar. A complete graph with four vertices is planar, but a complete graph with five vertices is not planar. A fundamental result on graph coloring – that remained an unproven conjecture for over 100 years – states that every planar graph is 4-colorable. The result was proven in 1976 by Kenneth Appel and Wolfgang Haken. They used a computer to test over 1900 special cases.

A directed graph (digraph for short) is a graph where each edge points in one direction. For example, the vertices could be cities and the edges could be the one-way air routes between them. For digraphs we use arrows to denote the edges. For example, Figure 3 shows two ways to represent the digraph with three vertices a, b, and ñ and edges from a to b, ñ to a, and ñ to b.

Figure 3.3

 

The degree of a vertex is the number of edges that it touches. For directed graphs the indegree of a vertex is the number of edges pointing at the vertex, while the outdegree of a vertex is the number of edges pointing away from the vertex. In a digraph a vertex is called a source if its indegree is zero and a sink if its outdegree is zero. For example, in the digraph of Figure 3.3, ñ is a source and b is a sink.

If a graph has more than one edge between some pair of vertices, the graph is called a multigraph, or a directed multigraph in case the edges point in the same direction. For example, there are usually two or more road routes between most cities. So a graph representing road routes between a set of cites is most likely a multigraph.

From a computational point of view, we need to represent graphs as data. This is easy to do because we can define a graph in terms of tuples, sets and bags. For example, we can define a graph G as an ordered pair (V, E), where V is a set of vertices and E is a set or bag of edges. If G is a digraph, then the edges in E can be represented by ordered pairs, where (a, b) represents the edge with an arrow from a to b. In this case the set E of edges is a subset of V×V. For example, the digraph in Figure 3 has vertex set {a, b, c} and edge set {‹a, b›, ‹c, b›, ‹c, a›}.

If G is a directed multigraph, then we can represent the edges as a bag (or multiset) of ordered pairs. For example, the bag {‹a, b›, ‹a, b›, ‹b, a›} represents three edges: two from a to b and one from b to a.

If a graph is not directed, we have more ways to represent the edges. We could still represent an edge as an ordered pair ‹a, b› and agree that it represents an undirected line between a and b. But we can also represent an edge between vertices a and b by a set {a,b}. For example, the graph in Figure 1 has vertex set {1, 2, 3} and edge set {{1, 2}, {1, 3}}.

We often encounter graphs that have information attached to each edge. For example, a good road map places distances along the roads between major intersections. A graph is called weighted if each edge is assigned a number, called a weight. We can represent an edge ‹a, b› that has weight w by the 3-tuple
‹a, b
, w›.

In some cases we might want to represent an unweighted graph as a weighted graph. For example, if we have a multigraph in which we wish to distinguish between multiple edges that occur between two vertices, then we can assign a different weight to each edge, thereby creating a weighted multigraph.

Sometimes it's useful to talk about portions of a graph. A subgraph of a graph ‹V, E› is any graph of the form ‹V', E'› where V'V and E'Å. For example, the four graphs in Figure 3.5 are subgraphs of the graph in Figure 3.4.

 

                                             Figure 3.4

 

               Figure 3.5