1Appendix D
Graphs
Graphs
2Appendix D
Graphs
Graphs: Applications (1)
Graphs are important for a lot of different applications. Graphs capture
relationships between objects in a visual way.
3Appendix D
Graphs
Graphs: Applications (2)
Graphs are important for a lot of different applications. Graphs capture
relationships between objects in a visual way.
4Appendix D
Graphs
Historical Background (1)
1736: Leonhard Euler (1707-1783)
„7 Bridges of Königsberg“
Do you think we can
find a path that crosses
each bridge once?
5Appendix D
Graphs
Königsberg / Kaliningrad
6Appendix D
Graphs
Leonhard Euler
Rosen
p. 695
7Appendix D
Graphs
Historical Background (2)
1736: Leonhard Euler
„7 Bridges of Königsberg“
Do you think we can
find a path that crosses
each bridge once?
Euler’s idea: It doesn’t matter
where exactly you are.
You must come and go via a bridge.
Collapse the entire area to a point.
c
a
d
b
8Appendix D
Graphs
Directed Graph G = (V,E)
V = finite set of vertices, n=|V|, E = finite set of edges, m=|E|
Ex. V={A, B, C, D}, E={ e1, e2, e3, e4, e5},
e1=(D,B), e2=(B,C), e3=(C,D), e4 = (D,A), e5 = (B,D)
Edge e = (u,v)
• u and v are called adjacent or neighbors in G
• u is called the initial vertex of (u,v), and v is called the terminal vertex of (u,v)
• e connects u and v and is called incident with the vertices u and v
• if u=v, then e is a loop
• indeg(v) = deg – (v) = in-degree of v =
number of edges with v as their terminal vertex (a loop contributes 1)
• outdeg(v) = deg + (v) = out-degree of v =
number of edges with v as their initial vertex (a loop contributes 1)
• if indeg(u) = 0, then u is a source
if outdeg(v) = 0, then v is a sink
9Appendix D
Graphs
Undirected Graph G = (V, E)
If there is an edge from u to v, then there is also an edge from v to u. In this case,
we don’t need arrows on the edges (and the edges are assumed to go both ways):
V = finite set of vertices, n=|V|, E = finite set of edges, m=|E|
Ex. V={A, B, C, D}, E={ e1, e2, e3, e4}, e1={B,D}, e2={B,C}, e3={C,D}, e4={A,D}
Edge e = {u,v)}
• u and v are called adjacent or neighbors in G
• u and v are the endpoints of the edge e={u,v}
• e connects u and v and is called incident with the vertices u and v
• if u=v, then e is a loop
• deg(v) = degree of v =
number of edges incident with v (a loop contributes twice)
10Appendix D
Graphs
Simple (Di-)Graph and Multigraph
Simple Graph =
undirected graph with
no loops and
no parallel edges
Simple Directed Graph =
directed graph with
no loops and
no parallel edges
Multigraph =
undirected graph with
no loops but
multiple edges between a pair of vertices
Rosen
p. 644
11Appendix D
Graphs
Paths
• a path x0, x1, …, xn
from u=x0 to v=xn
of length n > 1
is a sequence of n edges
• length of the path =
number of edges
• a path is simple
if it does not contain
the same edge more than once
• a path is a circuit
if it begins and ends at the same vertex u
and has length greater or equal to 1
• a path is a cycle if it is a circuit
that does not repeat vertices (besides u)
Rosen
pp. 679-680
12Appendix D
Graphs
Max. Number of Edges in Undirected Graphs
If G is a simple undirected graph with n vertices, what is the maximum number m of edges
that G can have?
A) n2
B) n2/2
C) n(n-1)/2
D) n(n+1)/2
E) n
Proof by Induction.
13Appendix D
Graphs
Max. Number of Edges in Directed Graphs
If G is a directed graph with n vertices, what is the maximum number of ordered pairs of
vertices (u,v) that could be connected by edges in G?
A) n
B) 2n
C) n2
D) n(n-1)/2
E) 2n
Proof by Induction.
14Appendix D
Graphs
Complete graphs
A complete graph on n vertices, denoted by Kn,
is a simple graph that contains exactly one edge
between each pair of distinct vertices.
Graphs Kn, for n = 1, 2, 3, 4, 5, 6:
A simple graph for which there is at least one
pair of distinct vertices not connected by an edge
is called noncomplete.
Rosen
p. 655
15Appendix D
Graphs
Hypercubes
An n-dimensional hypercube, denoted by Qn, is a graph
that has vertices representing the 2n bit strings of length n.
Two vertices are adjacent if and only if the bit strings
that they represent differ in exactly one bit position.
Rosen
pp. 655-656
16Appendix D
Graphs
Bipartite graphs
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint
sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2
(so that no edge in G connects either two vertices in V1 or two vertices in V2). When this
condition holds, we call the pair (V1, V2) a bipartition of the vertex set V of G.
Complete Bipartite Graphs: A complete bipartite graph Km,n is a graph that has its vertex set
partitioned into two subsets of m and n vertices, respectively with an edge between two vertices
if and only if one vertex is in the first subset and the other vertex is in the second subset.
Rosen
pp. 656-658
17Appendix D
Graphs
Connected components (in undirected graphs)
An undirected graph G is called connected
if there is a path between every pair of distinct vertices of the graph.
Disconnected graphs can be broken up into pieces where each is connected.
These pieces are called connected components.
Rosen
pp. 681-682
18Appendix D
Graphs
Connected components (in directed graphs)
A directed graph is strongly connected
if there is a path from a to b and from b to a
whenever a and b are vertices in the graph.
A directed graph is weakly connected
if there is a path between every two vertices
in the underlying undirected graph.
Rosen
pp. 685-686
19Appendix D
Graphs
Trees: Definitions (1)
An undirected tree is a connected undirected graph with no cycles.
• Any tree is a simple graph.
• Any tree has a unique simple path between any two of its vertices.
• A tree with n vertices has n-1 edges.
A directed tree or rooted tree is a tree in which one vertex has been
designated as the root and each edge is directed away from the root.
Every vertex has exactly one edge pointing to it except for the root
(which has no incoming edges).
If v is a vertex other than the root, the parent of v is a unique vertex
u such that there is a directed edge from u to v.
When u is the parent of v, v is called a child of u.
A vertex of a rooted tree is called a leaf if it has no children.
Vertices that have children are called internal vertices.
Which of them are Trees?
(a) (b)
(c) (d)
Rosen
pp. 745-749
20Appendix D
Graphs
Trees: Definitions (2)
The level of a vertex v in a rooted tree is the length of the unique path
from the root to its vertex. The level of the root is defined to be zero.
The height of a rooted tree is the maximum of the levels of vertices.
A binary tree is a rooted tree where every vertex has no more than
two children. There are at most 2h leaves and between [h+1, 2h+1-1]
vertices in a binary tree of height h.
A binary tree of height h is balanced if all leaves are at levels
h or h-1.
In a full binary tree, every internal vertex has exactly two children.
A full binary tree with i internal vertices contains n=2i+1 vertices.
A complete binary tree is a full binary tree in which every leaf
is at the same level.
Full or not?
full
not full
not full
Rosen
pp. 750-751
Complete or not?
not complete
complete
21Appendix D
Graphs
Representing Graphs
Adjacency Matrix:
O(n2) space
22Appendix D
Graphs
Representing Graphs
When is an adjacency matrix an inefficient way to store a graph?
How can we represent a graph without a lot of edges (or rather, in which the
density of edges is low compared to the total number of vertices)?
23Appendix D
Graphs
Representing Graphs
Adjacency List:
O(n+m) space
Foliennummer 1
Graphs: Applications (1)
Graphs: Applications (2)
Historical Background (1)
Königsberg / Kaliningrad
Leonhard Euler
Historical Background (2)
Directed Graph G = (V,E)
Undirected Graph G = (V, E)
Simple (Di-)Graph and Multigraph
Paths
Max. Number of Edges in Undirected Graphs
Max. Number of Edges in Directed Graphs
Complete graphs
Hypercubes
Bipartite graphs
Connected components (in undirected graphs)
Connected components (in directed graphs)
Trees: Definitions (1)
Trees: Definitions (2)
Representing Graphs
Representing Graphs
Representing Graphs