E2011: Theoretical fundamentals
of computer science: Basic notions of graph theory
Vlad Popovici, Ph.D. Fac. of Science - RECETOX
Applications
• Molecular models
• Computer networks
• Planning and scheduling
• Solve shortest path problems between cities
• Electrical circuits
• ...and many, many, others...
Some more examples
• Navigation/GPS: find the shortest path (using algorithm's like Dijkstra)
• Games: e.g. chess - choices can be arrange in a tree-structure and best movement (within a given horizon) can be selected
• Computation distribution across machines of a cluster
• Neural networks
Euler and the 7 bridges of Königsberg
(a) Königsberg in 1736 (6) Euler's graphical representation
Definitions - graphs
• A graph G = (V, E) is an ordered pairs of a set of
vertices V and a set of edges
E.
• If needed, the notation could
be V(G) to specify the set of
vertices of graph G, and E(G) for the set of edges of the same graph.
Definitions - edge types
• Directed edge: an ordered set of vertices, denoted as a
tuple (u, v)
• Undirected edge: an
unordered set of vertices,
represented as a set {u, v}
Definitions - edge type
• Loop: an edge {u, v}(or (u, v)) with u = v
• Multiple edges: two or more edges connecting the same two vertices
Definitions - graph type
• Undirected (simple) graph: a
graph G(V,£), V ^ 0, and E a set of undirected edges
• Directed graph: the set of
edges contains oriented edges
• Multigraph: multiple edges are allowed
• Pseudograph: a multigraph with loops
• and combinations...
Terminology - undirected graphs
For an undirected graph G(V, E)\
u and v are called adjacent if e = {u, v} E E\ e is called incident with u and v; u and v are called endpoints of e
the degree of a vertex v (deg(v)) is the number of edges incident
on v
pendant
isolated
V
1
pendant vertex: deg(v) = 1 isolated vertex: deg(v) = 0
degO) = 2, Vw E {1,3,4}
Terminology - directed graphs
For a directed graph G(V, E)\
• for e = (u, v) E E\ u is adjacent
to v; v is adjacent from u\ u is
initial vertex and v is terminal vertex
• the in-degree of a vertex v (deg~(v)) is the number of edges incident with v terminal vertex
• the out-degree of a vertex v (deg+(v)) is the number of edges incident with v initial vertex
1
5
deg+(4) = 0 deg"(4) = 2
deg+(l) = 1 deg-(l) = 1
Some basic results
• Theorem (Euler): in an undirected graph, deg(v) = 21E | (handshaking theorem)
• Theorem (Euler): an undirected graph has an even number of vertices with odd degree
• Theorem: in a directed graph,
^ deg-(v) = ^ deg+(v) =\E\
Special cases
• Complete graph: Kn is a
simple graph where any two vertices are connected by an edge
• Cycle: Cn, n > 3 consists of n vertices such that
{vi, v2}, {v2, v3},..., {vn_v vn], {vn, vl} G E
C3 = K3 C4= {1,2,3,4}
1
^2      1 •-• 2
1
Special cases - Bipartite graph
• A simple graph G for which the vertices V set can be
V = Vx u V2, v1nV2 = 0,
such that all edges have one end in Vx and the other one in
• Complete bipartite graph Km
is a bipartite graph
(I Vi I = m, I V21 = tz) in which all the vertices in one partition are connected to all the vertices in the second partition
partitioned
1
Subgraphs
1
G = (V, E)
• Let G = (V, E) be a graph.
• A graph H = (V, E') is a subgraph of G if V C V and
1
1
tf2 = (V
Graph union
1
= (Yl,El)
LetGi = (V^EJand
G2 = (V2, E2) be two simple graphs
G2 = (V2,E2)
Then their union is a graph
G = GluG2 = (V,E)
such that Vi U V2 ar}d E = EluE2
G = Gj u G2
Graph representation
'2
G = (V,E);V= {v1,...,vn},E = {el9...,em}
• Incidence matrix (nXm matrix)
1   if e] is adjacent with v7-
0
otherwise
«1   ^2 ^3
allO £10 1 c   0   1 1
Adjacency matrix (nXn matrix)
^0, otherwise
a b c
a 0  1 1
£10 1
c   1   1 0
Graph isomorphism
• Two graphs G1 = (V^E^) and
G2 = (V2, E2) are isomorphic if there exists a bijective function/: V1 -> V2suchthat {u, v} G Ei if and only if
{f(u),f(v)}GE2,
Vw, v e vx.
• The function/is called isomorphism.
f(a) = x;f(b) = u;f(c) = z;f(d) = y
Connectivity
• Path: a sequence of edges of the form
{vi,v2}, {v2,v3},{v,-,vy-}, {tyv*}
• Length of a path: number of edges
• A cycle: a path with first vertex identical to the last vertex
• A simple path: no edge is traversed more than once
• A graph is connected if there is a path between any pair of its vertices
2 4 6
3 5 7
Example of a path:
{1,2}, {2,5}, {5,4}, {4,7}
Cuts
In an undirected graph,
• an articulation point (cut vertex) is vertex whose removal would increase the number of connected components
• a cut edge is an edge whose removal would increase the number of connected components
cut edge
3 5 7
A
cut vertex
Connectivity of directed graphs
A directed graph is
• strongly connected if for any two
vertices n,vG Vthere is a path from u to v and from v to u
• weakly connected if, by
disregarding the orientation of the edges the resulting (undirected) graph is connected
Number of paths between 2 vertices
• Theorem: Let G be a graph with adjacency matrix A (for a fixed permutation of vertices vl5..vn). Then, the number of different paths of length r > 0 between two vertices vt and V; is [Ar]tj (the (/,j)-th element of the matrix Ar).
Eulerian graphs
• An Eulerian path/cycle is a path/cycle that contains all the edges exactly once.
• A graph is called traversable if it contains an Eulerian path.
• A graph is called Eulerian if it contains an Eulerian cycle.
(a) Königsberg in 1736 (6) Euler's graphical representation
• Theorem 1: A connected graph G is Eulerian if and only if it has no vertices of odd degree.
• Theorem 2: A connected graph contains an Eulerian path from
vertex u to vertex v ^ u if and only
if it is connected and u, v are the only two vertices of odd degree.
Conclusion: there is no solution to Königsberg 7 bridges problem.
Graph connectivity test
Output : List M of marked vertices in the component Input   : Graph G (e.g., adjacency list) Input   : Starting vertex s
L :— {s}; M :— {s};
% Repeat while there are still nodes to explore while L ^ 0 do choose u £ /_;
if 3 (a, v) e E such that v £ M then
choose (u, v) with v of smallest index;
/_:=/_ U {v}\ M:=MU {>}; % Mark and augment
else
|    L := Z.\{(/}; % Prune end
end
Graph connectivity test - example
L Mark
Questions?