Graphs

A graph is a non-linear data structure consisting of vertices (also known as nodes) and edges (links between vertices). Usually this is denoted as G = <V, E>, where V is a set of vertices, and E is a set of edges. Each edge is a pair (x,y), where x and y belongs to V. If the edge pair is ordered, the edge is called directed and thus the graph is directed graph. Otherwise, the graph is called undirected. Sometimes, an edge has a component called edge cost (or weight).

Graphs have applications in many areas: a city map, airports, computer networks, electrical circuits, and so on.

Here is the directed weighted graph

The graph has 5 vertices

V = {v1,v2,v3,v4,v5}

and 6 edges

E ={(v1,v2), (v2,v5), (v5,v3), (v4,v5), (v4,v3), (v4,v1)}

A graph is simple if there is no more than one edge between any two vertices. Otherwise, a graph is called multigraph. We also assume that a graph has no loops - an edge connecting the same vertex. I this course we will consider only simple graphs, without self-loops or multiple edges.

In a directed graph, an edge leaves its origin and ends in the destination. The out-degree of a vertex is the number of edges leaving the vertex. The in-degree of a vertex is the number of edges entering the vertex. The degree of a vertex is the number of edges entering and leaving the vertex. In the above example, the vertex v5 has the in-degree = 2, and the out-degree = 1, thus the degree is 3. The sink is a node, which has out-degree 0. A path is a sequence of distinctive vertices connected by edges. The path length is the number of edges on the path. In the weighted graph, the length is the sum of the costs along the path. A cycle in a directed graph is a path that begins and ends at the same vertex. A forest is a graph without cycles. A graph is connected, if there is a path between any two vertices. A tree is a connected graph without cycles. An alternative definition, a tree is a connected forest.

Proposition 1.

In a directed graph, the sum of in-degrees (or out-degrees) is equal the number of edges.

Reasoning: In a directed graph, any edge (x, y) contributes one unit to all in-degrees and one unit to all out-degrees.

Proposition 2.

In a connected graph with m edges the sum of degrees of all vertices is 2*m.

Reasoning: The proposition follows from the previous one.

Exercise. Suppose a simple graph has 15 edges, 3 vertices of degree 4, and all others of degree 3. How many vertices does the graph have? 3*4 + (x-3)*3 = 30

Exercise. Given a graph with 7 vertices; 3 of them of degree two and 4 of degree one. Is this graph is connected? No, 3*2 + 4*1=10 must have 10/2 = 5 edges

Proposition 3.

In an undirected graph with n vertices, there are at most n*(n-1)/2 edges.
In a directed graph with n vertices, there are at most n*(n-1) edges.

Reasoning: Consider an undirected graph with n vertices and choose any vertex. The possible number of edges leaving this vertex is n-1. Take another vertex. The possible number of edges leaving this vertex is n-2 (don't count the edge between these vertices twice!), and so on. We have

(n-1) + (n-2) + ... + 1 = n(n-1)/2

For all graphs, the number of edges and vertices satisfies the following inequality |E|<|V|^2, meaning that the number of edges is always less than the number of vertices squared. If the number of edges is close to |V|^2, we say that this is a dense graph, it has a large number of edges. Otherwise, this is a sparse graph. In most cases, the graph is relatively sparse.

Proposition 4.

Let G be an undirected graph.

• If G is connected, then |E| >= |V|-1
• If G is a tree, then |E| = |V|-1
• If G is a forest, then |E| <= |V|-1

A complete graph is a graph in which every vertex is adjacent (i.e., connected) to every other vertex.

o o---o o o-o
 / \ |x|
 o---o o-o

A subgraph of a graph G is a graph whose vertices and edges are subsets of the vertices and edges of G. If a graph is not connected, its maximal connected subgraphs are called connected components.

 
 v2 v3 v2 v3
 o o o o
 |\ /| \ /
 | \ / | \ /
 | \ / | \ /
 | ov1 | o v1
 | / \ | / \
 | / \ | / \
 |/ \| / \
 o o o o
 v5 v4 v5 v4
 graph subgraph
 

A spanning tree of a graph is a subgraph, which is a tree and contains all vertices of the graph. An example,

 2
 A------B A------B
 | / |  /
9| / |6 /
 | 3/ | /
 | / | /
 D------C D-----C
 5 spanning tree

Representation:

In a directed graph, vertex x is adjacent to vertex y if and only if there is an edge (x, y) between them.

There are two standard ways to represent a graph:

· as a collection of adjacency lists

· or as an adjacency matrix

The adjacency-list representation is used for representation of the sparse graphs. An adjacency-matrix representation may be preferred when the graph is dense.

The adjacency-list representation of a graph G consists of an array of linked lists, one for each vertices. Each such list contains all vertices adjacent to a chosen one. Here is an adjacency-list representation:

Vertices in an adjacency list are stored in an arbitrary order. A potential disadvantage of the adjacency-list representation is that there is no quicker way to determine if there is an edge between two given vertices. This disadvantage is eliminated by an adjacency-matrix representation.

For the adjacency-matrix representation we assume that the vertices are numbered 0, 1, 2, ..., N-1. The adjacency-matrix representation of a directed graph G = <V, E>  then consists of a |V| x |V| matrix, such that

matrix[i][j] = cost (or binary 1), if there is an edge between i and j
matrix[i][j] = INFINITY (or binary 0), otherwise
 

Here is the adjacency-matrix for the graph on the first page:

	v1	v2	v3	v4	v5
v1	inf	5	inf	inf	inf
v2	inf	inf	inf	inf	6
v3	inf	inf	inf	inf	inf
v4	25	inf	11	inf	19
v5	inf	inf	33	inf	inf

The adjacency-matrix implementation:

It consists of two classes. The matrix class

 
public class Matrix
{
 private Double [][] M;
 protected final static Double INFINITY = Double.MAX_VALUE;
 
 public Matrix(int n)
 {
 M = new Double[n][n];
 for (int i = 0; i < n; i++)
 for (int j = 0; j < n ; j++)
 M[i][j] = INFINITY;
 }
 
 //methods: get, set, toString
}

and the Graph class

 
public class Graph extends Matrix
{
 private int numEdges;
 private int numVertices;
 
 public Graph(int n)
 {
 super(n);
 numEdges = 0;
 numVertices = n;
 }
 
 //methods: addEdge, removeEdge, ...
}
 

Exercise 1.

Implement the method inDegree, which computes the in-degree of a given vertex.

Exercise 2.

Implement the method removeEdge, which removes an edge from a graph.

Exercise 3.

How many graphs are there which have n vertices? Don't count graphs with vertices connected to themselves.

Comparison of both representations:

Adjacency List Adjacency Matrix

sparse |E| << |V|^2 dense |E| ~ |V|^2

Space O(|V| + |E|) O(|V|^2)

Edge access O(|V|) O(1)