GRAPH THEORY

Please note that the material on this website is not intended to be exhaustive.
This is intended as a summary and supplementary material to the required textbook.

Graph

G = ( V, E ) ( or G = < N, E > ) is a set of finite and non–empty vertices V = { v₀, v₁, ¼, v_k} ( or nodes ) and a set of finite and non–empty edges E = { e₁, e₂, ¼, e_j} where an edge connects two vertices.

Path

is a sequence of vertices that traces the "travel" from an initial vertex to a terminal vertex.

Edges can either be undirected or directed.

Undirected edge

e that is associated with vertices v_i and v_j is denoted as e = ( v_i, v_j) or e = ( v_j, v_i).

Directed Edge

is a unique ordered pair of vertices e = ( v_i, v_j) which takes on the form of an arrow originating at the initial vertex of the edge, v_i, and terminates at the terminal vertex of the edge, v_j.

Incident

A directed or undirected edge e that is associated with vertices v_i and v_j is said to be incident on v_i and v_j.  Vertices v_i and v_j are then said to be incident on e and are adjacent vertices.  A vertex v that is not incident to an edge is said to be an isolated vertex.

Directed Graph or Digraph

is a graph whose edges are all directed and where the set of ordered pairs of vertices are called arcs.

Multigraph

Two vertices of a graph that are connected by more than one edge are said to contain parallel edges or multiple edges.  A graph with multiple edges is called a multigraph.

Loop

is an edge connecting a vertex to itself or is incident on a single vertex.

Pseudograph

is a graph with loops.

Simple Graph

is a graph with no parallel or multiple edges nor loops.

Complete Graph

on n vertices is the simple graph with n vertices in which there is an edge between every pair of distinct vertices and is denoted by K_n.

Bipartite Graph

G = { V, E } is one where there are two subsets V₁ and V₂ of V such that V₁ V₂ = Æ, V₁ V₂ = V, and each edge in E is incident to one vertex in V₁ and one vertex in V₂.

Complete Bipartite Graph

on m and n vertices is the simple graph whose vertex set is partitioned into sets | V₁ | = m vertices and | V₂ | = n vertices in which there is an edge between each pair of vertices v₁ ÎV₁ and v₂ ÎV₂ and it is denoted by K_m,n.

Weighted Graph

is a graph with labelled edges.  If edge e is labelled k, then it is said that the weight of e is k.

Length

of a path in a weighted graph is the sum of the weights of the edges in the path.

Hypercube or n–cube

is an important model of computation which describes parallel processing, i.e where a computer system is able to have more than 2ⁿ processors instead of just one.

The construction of the n–cube is as follows:

1. The 1–cube consists of 2 processors labeled 0 and 1.

   

   

   

   

2. Suppose H₁ is an (n–1)–cubes.  Make a duplicate copy of H₁, say call it H₂.  To form an n–cube, connect with an edge all corresponding vertices in H₁ and H₂, i.e. vertices with the same labels.  Then re–label the vertices in H₁ to 0L and the vertices in H₂ to 1L.

Since the world is a three dimensional world, it is not readily possible to illustrate n–cube, where n > 4.

Connected Graph

G is one where there is a path from any vertex v of G to any other vertex w of G, otherwise G is disconnected.

Bridge

is an edge e of graph G which renders G disconnected when e is removed.

Biconnected Graph

G is one where G is connected and does not have a bridge.

k–edge Connected

graph G is one where G is still connected when any k edges are removed from G.

k–vertex Connected

graph G is one where G is still connected when any k vertices are removed from G.

A finite graph G is always a finite union of maximal connected graphs which are called connected components of G.

Strongly Connected

digraph G is one where there is a directed path from any vertex of G to any other vertex of G.

Subgraph

of graph G = ( V, E ) is a graph G' = ( V', E' ) where V' Í V and E' Í E and for every edge e' Î E', if e' is incident on v' and w', then v', w' Î V'.

Walk

on a graph G is an alternating sequence of vertices and edges v₀, e₁, v₁, e₂, ¼, e_n, v_n beginning and ending with a vertex such that each edge is immediately preceded and followed by the two vertices which lie on it.

Trail

is a walk whose edges are all distinct.

Simple Path

is a walk whose vertices are all distinct.

Closed Walk

is one where v₀ = v_n.

Cycle or Circuit

is a closed path where n ³ 3.

Simple Cycle

is a cycle whose vertices are distinct except for the beginning vertex and the ending vertex.

Example:	Consider the following garph
	Consider the walk    v1 e5 v5 e4 v4 e6 v1 e8 v3 e2 v2 e11 v3 e10 v5 e7 v2 e1 v1 Is the walk above a trail? If not, can you modify it to create a trail? Is the walk above a path? If not, can you modify it to create a path? Is the walk above a closed walk? If not, can you modify it to create a closed walk? Is the walk above a cycle? If not, can you modify it to create a cycle?

Directed Cycle

in digraph G is a closed directed path.

Directed Cyclic Graph

G is a graph that has no directed cycles.

Euler cycle

is a cycle in a graph G that includes all the edges and vertices of G.

Degree

of a vertex v is the number of edges incident on v and is denoted by d(v).

THEOREM:

If a graph G has an Euler cycle, then G is connected and every vertex has even degree.

THEOREM:

If G is a connected graph and every vertex has even degree, then G has an Euler cycle.

THEOREM:

If G is a graph with m edges and vertices { v₁, v₂, ¼, v_n}, then Sd(v_i) = 2m

In particular, the sum of the degrees of all the vertices in a graph is even.

CORROLARY:

In any graph, there are an even number of vertices of odd degree.

THEOREM:

A graph has a path with no repeated edges from v to w ( v ¹w ) containing all the edges and vertices if and only if it is connected and v and w are the only vertices having odd degree.

THEOREM:

If a graph G contains a cycle from v to v, then G contains a simple cycle from v to v.

Hamiltonian Cycle

is a cycle in a graph G that contains each vertex in G exactly once except for the starting and ending vertex that appears twice.  This was named in honor of Sir William Rowan Hamilton.

Dodecahedron

In other words, if each vertex in a dodecahedron were to represent a city, the problem consists of visiting all the cities passing through each city once and only once except for the start and the end.

Traveling Salesman Problem

A related problem is the traveling salesman problem, i.e. given a weighted graph G, find a minimum–length Hamiltonian cycle in G.  This can be likened to the cities and the edge weights as distances.  Hence, the traveling salesman problem consists of finding a shortest route in which a salesman can visit each city once and only one time, starting and ending at the same city.

Ring Model

Consider a ring model for parallel computation where the vertices represent processors and an edge betweeen processors p and q indicates direct communication between the two processors.  Observe that the graph of the model contains a simple cycle.

The n–cube is another model for parallel computation offering greater connectivity among its processors.  Observe that for an n–cube to contain a Hamiltonian cycle, it must have n ³ 2 since a 1–cube contains no cycles.  Recall that the vertices of the n–cube may be labelled 0, 1, ¼, 2ⁿ–1 such that an edge connects two vertices if and only if the binary representation of their labels differs in exactly on bit.  Furthermore, the n–cube has a Hamiltonian cycle if there is a sequence s₁, s₂, ¼, s_2ⁿ called Gray code where each s_i is a string of n bits, satisfying:

• Every n–bit string appears somewhere in the sequence.
• s_i and s_i+1 differ in exactly one bit, i = 1, 2, ¼, 2ⁿ–1.
• s_2ⁿ and s₁ differ in exactly one bit.

When n ³ 2, a Gray Code

s₁, s₂, ¼, s_2ⁿ

corresponds to the Hamiltonian cycle

s₁, s₂, ¼, s_2ⁿ, s₁

THEOREM:

Let G₁ denote the sequence 0, 1.  Define G_n in terms of G_n–1 by the following rules:

1. Let G^R_n–1 denote the sequence G_n–1 written in reverse.
2. Let G'_n–1 denote the sequence obtained by prefixing each member of G_n–1 with 0.
3. Let G"_n–1 denote the sequence obatined by prefixing each member of G^R_n–1 with 1.
4. Let G_n be the sequence consisting of G'_n–1 followed by G"_n–1.

Then G_n is a Gray code for every positive integer n.

Knight's Tour

Another related problem is the Knight's Tour where a knight chess piece traverses each square in a chess board once and only once.  A graph of legal moves for a knight piece in an n x n chess board is said to be a GK_n.  Then there is a knight's tour on the n x n chess board if and only if GK_n has a Hamiltonian cycle.

In a connected weighted graph G, a common problem is finding a shortest path.

Dijkstra's Shortest–Path Algorithm

This algorithm finds the length of a shortest path from vertex a to vertex z in a connected weighted graph.  Let w(i, j) > 0 denote the weight of edge (i, j) and let L(x) denote the label of vertex x.  At termination, L(z) is the length of a shortest path from a to z.

Let T denote the set of vertices having temporary labels.  Let circled vertex denote vertices having permanent label.

Input:	A connected weighted graph in which all weights are positive Vertices a to z
Output:	L(z), the length of a shortest path from a to z.
Algorithm:	procedure dijkstra (w, a, z, L)      L(a) := 0      for all vertices x ¹a do          L(x) :=      T := set of all vertices      // T is the set of vertices whose shortest distance from a has not been found      while z ÎT do          begin              choose v ÎT with minimum L(v)              T := T – {v}              for each x ÎT adjacent to v do                  L(v) := min {L(x), L(v) + w(v, x)}          end end

THEOREM:

Dijkstra's shortest–path algorithm correctly finds the length of a shortest path from a to z.

ASSIGNMENT

---

© 2000-07-07 cpsm; last update 2008-10-15 20:09

---