Undirected Graph

G = (V, E)

  • G - an undirected graph
  • V - a set of vertices
  • E - a set of edges

e = (u, v)

  • e - an edge
  • (u, v) - an unordered pair of vertices

 

Directed Graph

G = (V, E) 

  • G - a directed graph
  • V - a set of vertices
  • E - a set of edges

e = (u, v)

  • e - an edge
  • (u, v) - an ordered pair of vertices

We say that the edge in the directed graph goes from u to v.

 

Sparse Graph

A sparse graph has much fewer edges than vertices:

|E| << |V|^2

 

Bipartite Graphs

G = (X, Y, E)

The vertices of a bipartite graph are partitioned into two disjoint sets X and Y (V = X u Y). There are no vertices within the same set that are adjacent i.e. each edge (E) connects a vertex in X with a vertex in Y rather than X to X or Y to Y.

An example of a bipartite graph:

Terminology

  • Two adjacent vertices belong to the same edge.
  • The neighbours of a vertex are vertices that form edges with the vertex. 
  • An edge (u,v) is said to be incident on vertices u and v.
  • The degree of a vertex is the number of edges incident to the vertex.
  • In a directed graph:
    • The out-degree of a vertex is the number of edges from the vertex to other vertices.
    • The in-degree of a vertex is the number of edges from other vertices to the vertex.
  • A path p = [v0, v1, ..., vk] from v0 to vk is a sequence of vertices such that two adjacent vertices form an edge. Any edge may be used only once in a path.
  • A cycle is a path whose end vertices are the same, i.e. v0 = vk.
  • A walk w = [v0, v1, ..., vk] from v0 to vk is a sequence of vertices such that two adjacent vertices form an edge. Edges and vertices may be repeated.
  • A walk is closed when its end vertices are the same, i.e. v0 = vk.
  • A graph is connected if there is a path between every pair of vertices.
  • A directed graph is strongly connected if there is a path between every pair of vertices in each direction.
  • A forest is an acyclic, undirected graph.
  • A tree is a connected forest.
  • A directed acyclic graph (DAG) is a directed graph without cycles.
  • A rooted tree has one vertex designated as the root. All edges of the rooted tree are directed away from the root.
  • In any directed edge (u,v) of the rooted tree, u is v's parent and v is u's child.
  • The descendants of a vertex are all vertices that are reachable by directed paths starting from the vertex. This includes the vertex itself.
  • Leaves are vertices that have no children.
  • A binary tree is a rooted tree in which each node has at most two children - the left child and the right child. Each child, in turn, is a root for the left subtree and the right subtree respectively.

The gray vertex has three neighbours:

The gray vertex has two out-degree vertices and one in-degree vertex:

 

Graph Representation

Graphs can be represented using:

The adjacency list - an array of linked lists.

  • Each linked list represents a vertex.
  • The entries in the linked list represent adjacent vertices.

The adjacency matrix - an n x n array

  • The [i,j] entry in the array is 1 if the graph has an edge between vertices i and j, otherwise 0.

 

Tree Traversal Techniques

The major tree traversal techniques are:

  • preorder - The root of a subtree is processed before its descendants.
  • postorder - The root of a subtree is processed after its descendants.
  • inorder - The root of a subtree is processed after all vertices in its left subtree have been processed, but before any of the vertices in its right subtree are processed (this traversal technique applies only to binary trees).

 

Depth-First Search

The depth-first search is a fundamental graph searching technique:

1. Initialize all vertices of the graph as unvisited.

2. Pick an arbitrary vertex u (the root vertex).

3. For each adjacent unvisited vertex v of u: 

     3a. Mark v as visited.

     3b. Repeat the step 3 for each adjacent unvisited vertex of v.

Steps 3, 3a, and 3b form recursive calls.

A sequence of traversing the nodes of a graph using the depth-first search algorithm:

 

Breadth-First Search

The breadth-first search (BFS) algorithm starts at a root vertex and then adds other vertices to a queue as they are discovered. The vertices are processed in FIFO order.

 

Shortest Paths Algorithms

  • Dijkstra's Algorithm
  • Bellman-Ford Algorithm - works correctly for graphs that have edges of negative length

 

Minimum Spanning Trees

Minimum spanning trees have applications in network design:

  • A set of sites is connected by a network
  • Each site is represented by a vertex
  • Links between sites are represented by edges
  • Each edge has a cost
  • A tree is a minimal network that connects a set of nodes
  • The cost of a tree is the sum of the costs of its edges
  • A minimum-cost tree is called a minimum spanning tree

Algorithms for finding the minimum spanning trees:

  • Prim's Algorithm - grows a single tree
  • Kruskal's Algorithm - grows a forest

Prim's vs. Dijkstra's algorithms:

  • Both algorithms start building a tree from a single vertex 
  • Both algorithms grow the tree by adding one vertex at a time
  • The difference is in the rule for deciding when the current label is updated for vertices outside the tree

 

Matching Problems and Network Flows

The network flow models the problem of efficiently moving entities from one place to another in a network.

  • The matching problem is a special case of the network flow problem.
  • The assignment problem is a generalization of the matching problem to the weighted case.

The matching problem definition: given a graph G = (V,E), a matching M is a subset of the edges such that no two edges in M share a common vertex i.e. the problem is that of finding a set of independent edges that have no incident vertices in common. The cardinality of M is referred to as its size.

The assignment problem is that of finding perfect matching of maximum (or minimum) total weight.

The travelling salesman problem asks for a minimum length tour of a graph that visits all of the vertices exactly once.

 

References

[1] Allen B. Tucker. "Computer Science Handbook, Second Edition". Chapman and Hall/CRC, 2 edition, 2004