المحاضرة السادسة هياكل بيانات كورس ثاني

Graphs: basics
Basic types of graphs:
• Directed graphs
• Undirected graphs
CS 441 Discrete mathematics for CS
a
c
b
c d
a b
M. Hauskrecht
Complete graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.
CS 441 Discrete mathematics for CS
3
M. Hauskrecht
A cycle
A cycle Cn for n ? 3 consists of n vertices v1, v2 ,? , vn, and edges
{v1, v2}, {v2, v3} ,? , {vn-1, vn}, {vn, v1}.
CS 441 Discrete mathematics for CS
M. Hauskrecht
N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.
CS 441 Discrete mathematics for CS
4
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
5
M. Hauskrecht
Subgraphs
Definition: A subgraph of a graph G = (V,E) is a graph (W,F),
where W ? V and F ? E. A subgraph H of G is a proper subgraph
of G if H ? G.
Example: K5 and one of its subgraphs.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Subgraphs
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph (W,F),
where the edge set F contains an edge in E if and only if both
endpoints are in W.
Example: K5 and the subgraph induced by W = {a,b,c,e}.
CS 441 Discrete mathematics for CS
6
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
7
M. Hauskrecht
Adjacency matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| =
n. Arbitrarily list the vertices of G as v1, v2, … , vn. The adjacency
matrix AG of G, with respect to the listing of vertices, is the n × n
zero-one matrix with 1 as its (i, j)th entry when vi and vj are
adjacent, and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij],
then
Example:
CS 441 Discrete mathematics for CS
The ordering of
vertices is a, b, c, d.
M. Hauskrecht
Adjacency matrices
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position
of the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
Example: The adjacency matrix of the pseudograph shown here
using the ordering of vertices a, b, c, d.
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
Are the two graphs isomorphic?
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
u1 ? v1
u2 ? v4
u3 ? v2
u4 ? v3
Are the two graphs isomorphic?
9
M. Hauskrecht
Connectivity in the graphs, paths
Informal Definition: A path is a sequence of edges that begins at
a vertex of a graph and travels from vertex to vertex along edges of
the graph. As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these.
Applications: Numerous problems can be modeled with paths
formed by traveling along edges of graphs such as:
– determining whether a message can be sent between two
computers.
– efficiently planning routes for mail/message delivery.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Connectivity in the graphs
• We can use the adjacency matrix of a graph to find the number of
the different paths between two vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
Paths of length 4.
CS 441 Discrete mathematics for CS
A =
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
CS 441 Discrete mathematics for CS
A =
Paths of length 4: The adjacency matrix of
G (ordering the vertices as a, b, c, d) is
given above. Hence the number of paths of
length four from a to d is the (1, 4)th entry
of A4
A4 =
11
M. Hauskrecht
Trees
Definition: A tree is a connected undirected graph with no
simple circuits.
Examples:
CS 441 Discrete mathematics for CS
Tree: yes Tree: yes Tree: no Tree: no
M. Hauskrecht
Connectivity in the graphs
Definition: A forest is a graph that has no simple circuit, but is not
connected. Each of the connected components in a forest is a tree.
Example:
CS 441 Discrete mathematics for CS
12
M. Hauskrecht
Trees
Theorem: An undirected graph is a tree if and only if there is a
unique simple path between any two of its vertices.
CS 441 Discrete mathematics for CS
A
B
C D E
G F
M. Hauskrecht
Application of trees
Examples:
• The organization of a computer file system into directories,
subdirectories, and files is naturally represented as a tree.
• structure of organizations.
CS 441 Discrete mathematics for CS
13
M. Hauskrecht
Rooted trees
Definition: A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed away from the
root.
Note: An unrooted tree can be converted into different rooted trees
when one of the vertices is chosen as the root.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Rooted trees - terminology
• If v is a vertex of a rooted tree other than the root, the parent of v is
the unique vertex u such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u. Vertices with the
same parent are called siblings.
CS 441 Discrete mathematics for CS
Parent of g: a
Children of g: h,j,k
Siblings of g: b,f
14
M. Hauskrecht
Rooted trees - terminology
• The ancestors of a vertex are the vertices on the path from the root
to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an
ancestor.
CS 441 Discrete mathematics for CS
Ancestors of j: g,a
Descendants of j: l,m
M. Hauskrecht
Rooted trees - terminology
• A vertex of a rooted tree with no children is called a leaf. Vertices
that have children are called internal vertices.
CS 441 Discrete mathematics for CS
Leafs: d,e,k, l,m
Examples of internal nodes:
b,g,h
15
M. Hauskrecht
Rooted trees - terminology
• If a is a vertex in a tree, the subtree with a as its root is the
subgraph of the tree consisting of a and its descendants and all
edges incident to these descendants.
CS 441 Discrete mathematics for CS
M. Hauskrecht
M-ary tree
Definition: A rooted tree is called an m-ary tree if every internal
vertex has no more than m children. The tree is called a full m-ary
tree if every internal vertex has exactly m children. An m-ary tree
with m = 2 is called a binary tree.
Example: Are the following rooted trees full m-ary trees for some
positive integer m?
CS 441 Discrete mathematics for CS
16
M. Hauskrecht
Binary trees
Definition: A binary tree is an ordered rooted where each internal
vertex has at most two children. If an internal vertex of a binary
tree has two children, the first is called the left child and the second
the right child. The tree rooted at the left child of a vertex is called
the left subtree of this vertex, and the tree rooted at the right child
of a vertex is called the right subtree of this vertex.
CS 441 Discrete mathematics for CS
Graphs: basics
Basic types of graphs:
• Directed graphs
• Undirected graphs
CS 441 Discrete mathematics for CS
a
c
b
c d
a b
M. Hauskrecht
Complete graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.
CS 441 Discrete mathematics for CS
3
M. Hauskrecht
A cycle
A cycle Cn for n ? 3 consists of n vertices v1, v2 ,? , vn, and edges
{v1, v2}, {v2, v3} ,? , {vn-1, vn}, {vn, v1}.
CS 441 Discrete mathematics for CS
M. Hauskrecht
N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.
CS 441 Discrete mathematics for CS
4
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
5
M. Hauskrecht
Subgraphs
Definition: A subgraph of a graph G = (V,E) is a graph (W,F),
where W ? V and F ? E. A subgraph H of G is a proper subgraph
of G if H ? G.
Example: K5 and one of its subgraphs.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Subgraphs
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph (W,F),
where the edge set F contains an edge in E if and only if both
endpoints are in W.
Example: K5 and the subgraph induced by W = {a,b,c,e}.
CS 441 Discrete mathematics for CS
6
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
7
M. Hauskrecht
Adjacency matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| =
n. Arbitrarily list the vertices of G as v1, v2, … , vn. The adjacency
matrix AG of G, with respect to the listing of vertices, is the n × n
zero-one matrix with 1 as its (i, j)th entry when vi and vj are
adjacent, and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij],
then
Example:
CS 441 Discrete mathematics for CS
The ordering of
vertices is a, b, c, d.
M. Hauskrecht
Adjacency matrices
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position
of the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
Example: The adjacency matrix of the pseudograph shown here
using the ordering of vertices a, b, c, d.
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
Are the two graphs isomorphic?
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
u1 ? v1
u2 ? v4
u3 ? v2
u4 ? v3
Are the two graphs isomorphic?
9
M. Hauskrecht
Connectivity in the graphs, paths
Informal Definition: A path is a sequence of edges that begins at
a vertex of a graph and travels from vertex to vertex along edges of
the graph. As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these.
Applications: Numerous problems can be modeled with paths
formed by traveling along edges of graphs such as:
– determining whether a message can be sent between two
computers.
– efficiently planning routes for mail/message delivery.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Connectivity in the graphs
• We can use the adjacency matrix of a graph to find the number of
the different paths between two vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
Paths of length 4.
CS 441 Discrete mathematics for CS
A =
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
CS 441 Discrete mathematics for CS
A =
Paths of length 4: The adjacency matrix of
G (ordering the vertices as a, b, c, d) is
given above. Hence the number of paths of
length four from a to d is the (1, 4)th entry
of A4
A4 =
11
M. Hauskrecht
Trees
Definition: A tree is a connected undirected graph with no
simple circuits.
Examples:
CS 441 Discrete mathematics for CS
Tree: yes Tree: yes Tree: no Tree: no
M. Hauskrecht
Connectivity in the graphs
Definition: A forest is a graph that has no simple circuit, but is not
connected. Each of the connected components in a forest is a tree.
Example:
CS 441 Discrete mathematics for CS
12
M. Hauskrecht
Trees
Theorem: An undirected graph is a tree if and only if there is a
unique simple path between any two of its vertices.
CS 441 Discrete mathematics for CS
A
B
C D E
G F
M. Hauskrecht
Application of trees
Examples:
• The organization of a computer file system into directories,
subdirectories, and files is naturally represented as a tree.
• structure of organizations.
CS 441 Discrete mathematics for CS
13
M. Hauskrecht
Rooted trees
Definition: A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed away from the
root.
Note: An unrooted tree can be converted into different rooted trees
when one of the vertices is chosen as the root.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Rooted trees - terminology
• If v is a vertex of a rooted tree other than the root, the parent of v is
the unique vertex u such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u. Vertices with the
same parent are called siblings.
CS 441 Discrete mathematics for CS
Parent of g: a
Children of g: h,j,k
Siblings of g: b,f
14
M. Hauskrecht
Rooted trees - terminology
• The ancestors of a vertex are the vertices on the path from the root
to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an
ancestor.
CS 441 Discrete mathematics for CS
Ancestors of j: g,a
Descendants of j: l,m
M. Hauskrecht
Rooted trees - terminology
• A vertex of a rooted tree with no children is called a leaf. Vertices
that have children are called internal vertices.
CS 441 Discrete mathematics for CS
Leafs: d,e,k, l,m
Examples of internal nodes:
b,g,h
15
M. Hauskrecht
Rooted trees - terminology
• If a is a vertex in a tree, the subtree with a as its root is the
subgraph of the tree consisting of a and its descendants and all
edges incident to these descendants.
CS 441 Discrete mathematics for CS
M. Hauskrecht
M-ary tree
Definition: A rooted tree is called an m-ary tree if every internal
vertex has no more than m children. The tree is called a full m-ary
tree if every internal vertex has exactly m children. An m-ary tree
with m = 2 is called a binary tree.
Example: Are the following rooted trees full m-ary trees for some
positive integer m?
CS 441 Discrete mathematics for CS
16
M. Hauskrecht
Binary trees
Definition: A binary tree is an ordered rooted where each internal
vertex has at most two children. If an internal vertex of a binary
tree has two children, the first is called the left child and the second
the right child. The tree rooted at the left child of a vertex is called
the left subtree of this vertex, and the tree rooted at the right child
of a vertex is called the right subtree of this vertex.
CS 441 Discrete mathematics for CS
Graphs: basics
Basic types of graphs:
• Directed graphs
• Undirected graphs
CS 441 Discrete mathematics for CS
a
c
b
c d
a b
M. Hauskrecht
Complete graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.
CS 441 Discrete mathematics for CS
3
M. Hauskrecht
A cycle
A cycle Cn for n ? 3 consists of n vertices v1, v2 ,? , vn, and edges
{v1, v2}, {v2, v3} ,? , {vn-1, vn}, {vn, v1}.
CS 441 Discrete mathematics for CS
M. Hauskrecht
N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.
CS 441 Discrete mathematics for CS
4
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
5
M. Hauskrecht
Subgraphs
Definition: A subgraph of a graph G = (V,E) is a graph (W,F),
where W ? V and F ? E. A subgraph H of G is a proper subgraph
of G if H ? G.
Example: K5 and one of its subgraphs.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Subgraphs
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph (W,F),
where the edge set F contains an edge in E if and only if both
endpoints are in W.
Example: K5 and the subgraph induced by W = {a,b,c,e}.
CS 441 Discrete mathematics for CS
6
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
7
M. Hauskrecht
Adjacency matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| =
n. Arbitrarily list the vertices of G as v1, v2, … , vn. The adjacency
matrix AG of G, with respect to the listing of vertices, is the n × n
zero-one matrix with 1 as its (i, j)th entry when vi and vj are
adjacent, and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij],
then
Example:
CS 441 Discrete mathematics for CS
The ordering of
vertices is a, b, c, d.
M. Hauskrecht
Adjacency matrices
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position
of the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
Example: The adjacency matrix of the pseudograph shown here
using the ordering of vertices a, b, c, d.
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
Are the two graphs isomorphic?
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
u1 ? v1
u2 ? v4
u3 ? v2
u4 ? v3
Are the two graphs isomorphic?
9
M. Hauskrecht
Connectivity in the graphs, paths
Informal Definition: A path is a sequence of edges that begins at
a vertex of a graph and travels from vertex to vertex along edges of
the graph. As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these.
Applications: Numerous problems can be modeled with paths
formed by traveling along edges of graphs such as:
– determining whether a message can be sent between two
computers.
– efficiently planning routes for mail/message delivery.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Connectivity in the graphs
• We can use the adjacency matrix of a graph to find the number of
the different paths between two vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
Paths of length 4.
CS 441 Discrete mathematics for CS
A =
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
CS 441 Discrete mathematics for CS
A =
Paths of length 4: The adjacency matrix of
G (ordering the vertices as a, b, c, d) is
given above. Hence the number of paths of
length four from a to d is the (1, 4)th entry
of A4
A4 =
11
M. Hauskrecht
Trees
Definition: A tree is a connected undirected graph with no
simple circuits.
Examples:
CS 441 Discrete mathematics for CS
Tree: yes Tree: yes Tree: no Tree: no
M. Hauskrecht
Connectivity in the graphs
Definition: A forest is a graph that has no simple circuit, but is not
connected. Each of the connected components in a forest is a tree.
Example:
CS 441 Discrete mathematics for CS
12
M. Hauskrecht
Trees
Theorem: An undirected graph is a tree if and only if there is a
unique simple path between any two of its vertices.
CS 441 Discrete mathematics for CS
A
B
C D E
G F
M. Hauskrecht
Application of trees
Examples:
• The organization of a computer file system into directories,
subdirectories, and files is naturally represented as a tree.
• structure of organizations.
CS 441 Discrete mathematics for CS
13
M. Hauskrecht
Rooted trees
Definition: A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed away from the
root.
Note: An unrooted tree can be converted into different rooted trees
when one of the vertices is chosen as the root.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Rooted trees - terminology
• If v is a vertex of a rooted tree other than the root, the parent of v is
the unique vertex u such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u. Vertices with the
same parent are called siblings.
CS 441 Discrete mathematics for CS
Parent of g: a
Children of g: h,j,k
Siblings of g: b,f
14
M. Hauskrecht
Rooted trees - terminology
• The ancestors of a vertex are the vertices on the path from the root
to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an
ancestor.
CS 441 Discrete mathematics for CS
Ancestors of j: g,a
Descendants of j: l,m
M. Hauskrecht
Rooted trees - terminology
• A vertex of a rooted tree with no children is called a leaf. Vertices
that have children are called internal vertices.
CS 441 Discrete mathematics for CS
Leafs: d,e,k, l,m
Examples of internal nodes:
b,g,h
15
M. Hauskrecht
Rooted trees - terminology
• If a is a vertex in a tree, the subtree with a as its root is the
subgraph of the tree consisting of a and its descendants and all
edges incident to these descendants.
CS 441 Discrete mathematics for CS
M. Hauskrecht
M-ary tree
Definition: A rooted tree is called an m-ary tree if every internal
vertex has no more than m children. The tree is called a full m-ary
tree if every internal vertex has exactly m children. An m-ary tree
with m = 2 is called a binary tree.
Example: Are the following rooted trees full m-ary trees for some
positive integer m?
CS 441 Discrete mathematics for CS
16
M. Hauskrecht
Binary trees
Definition: A binary tree is an ordered rooted where each internal
vertex has at most two children. If an internal vertex of a binary
tree has two children, the first is called the left child and the second
the right child. The tree rooted at the left child of a vertex is called
the left subtree of this vertex, and the tree rooted at the right child
of a vertex is called the right subtree of this vertex.
CS 441 Discrete mathematics for CS
Graphs: basics
Basic types of graphs:
• Directed graphs
• Undirected graphs
CS 441 Discrete mathematics for CS
a
c
b
c d
a b
M. Hauskrecht
Complete graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.
CS 441 Discrete mathematics for CS
3
M. Hauskrecht
A cycle
A cycle Cn for n ? 3 consists of n vertices v1, v2 ,? , vn, and edges
{v1, v2}, {v2, v3} ,? , {vn-1, vn}, {vn, v1}.
CS 441 Discrete mathematics for CS
M. Hauskrecht
N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.
CS 441 Discrete mathematics for CS
4
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
5
M. Hauskrecht
Subgraphs
Definition: A subgraph of a graph G = (V,E) is a graph (W,F),
where W ? V and F ? E. A subgraph H of G is a proper subgraph
of G if H ? G.
Example: K5 and one of its subgraphs.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Subgraphs
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph (W,F),
where the edge set F contains an edge in E if and only if both
endpoints are in W.
Example: K5 and the subgraph induced by W = {a,b,c,e}.
CS 441 Discrete mathematics for CS
6
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
7
M. Hauskrecht
Adjacency matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| =
n. Arbitrarily list the vertices of G as v1, v2, … , vn. The adjacency
matrix AG of G, with respect to the listing of vertices, is the n × n
zero-one matrix with 1 as its (i, j)th entry when vi and vj are
adjacent, and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij],
then
Example:
CS 441 Discrete mathematics for CS
The ordering of
vertices is a, b, c, d.
M. Hauskrecht
Adjacency matrices
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position
of the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
Example: The adjacency matrix of the pseudograph shown here
using the ordering of vertices a, b, c, d.
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
Are the two graphs isomorphic?
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
u1 ? v1
u2 ? v4
u3 ? v2
u4 ? v3
Are the two graphs isomorphic?
9
M. Hauskrecht
Connectivity in the graphs, paths
Informal Definition: A path is a sequence of edges that begins at
a vertex of a graph and travels from vertex to vertex along edges of
the graph. As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these.
Applications: Numerous problems can be modeled with paths
formed by traveling along edges of graphs such as:
– determining whether a message can be sent between two
computers.
– efficiently planning routes for mail/message delivery.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Connectivity in the graphs
• We can use the adjacency matrix of a graph to find the number of
the different paths between two vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
Paths of length 4.
CS 441 Discrete mathematics for CS
A =
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
CS 441 Discrete mathematics for CS
A =
Paths of length 4: The adjacency matrix of
G (ordering the vertices as a, b, c, d) is
given above. Hence the number of paths of
length four from a to d is the (1, 4)th entry
of A4
A4 =
11
M. Hauskrecht
Trees
Definition: A tree is a connected undirected graph with no
simple circuits.
Examples:
CS 441 Discrete mathematics for CS
Tree: yes Tree: yes Tree: no Tree: no
M. Hauskrecht
Connectivity in the graphs
Definition: A forest is a graph that has no simple circuit, but is not
connected. Each of the connected components in a forest is a tree.
Example:
CS 441 Discrete mathematics for CS
12
M. Hauskrecht
Trees
Theorem: An undirected graph is a tree if and only if there is a
unique simple path between any two of its vertices.
CS 441 Discrete mathematics for CS
A
B
C D E
G F
M. Hauskrecht
Application of trees
Examples:
• The organization of a computer file system into directories,
subdirectories, and files is naturally represented as a tree.
• structure of organizations.
CS 441 Discrete mathematics for CS
13
M. Hauskrecht
Rooted trees
Definition: A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed away from the
root.
Note: An unrooted tree can be converted into different rooted trees
when one of the vertices is chosen as the root.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Rooted trees - terminology
• If v is a vertex of a rooted tree other than the root, the parent of v is
the unique vertex u such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u. Vertices with the
same parent are called siblings.
CS 441 Discrete mathematics for CS
Parent of g: a
Children of g: h,j,k
Siblings of g: b,f
14
M. Hauskrecht
Rooted trees - terminology
• The ancestors of a vertex are the vertices on the path from the root
to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an
ancestor.
CS 441 Discrete mathematics for CS
Ancestors of j: g,a
Descendants of j: l,m
M. Hauskrecht
Rooted trees - terminology
• A vertex of a rooted tree with no children is called a leaf. Vertices
that have children are called internal vertices.
CS 441 Discrete mathematics for CS
Leafs: d,e,k, l,m
Examples of internal nodes:
b,g,h
15
M. Hauskrecht
Rooted trees - terminology
• If a is a vertex in a tree, the subtree with a as its root is the
subgraph of the tree consisting of a and its descendants and all
edges incident to these descendants.
CS 441 Discrete mathematics for CS
M. Hauskrecht
M-ary tree
Definition: A rooted tree is called an m-ary tree if every internal
vertex has no more than m children. The tree is called a full m-ary
tree if every internal vertex has exactly m children. An m-ary tree
with m = 2 is called a binary tree.
Example: Are the following rooted trees full m-ary trees for some
positive integer m?
CS 441 Discrete mathematics for CS
16
M. Hauskrecht
Binary trees
Definition: A binary tree is an ordered rooted where each internal
vertex has at most two children. If an internal vertex of a binary
tree has two children, the first is called the left child and the second
the right child. The tree rooted at the left child of a vertex is called
the left subtree of this vertex, and the tree rooted at the right child
of a vertex is called the right subtree of this vertex.
CS 441 Discrete mathematics for CS
Graphs: basics
Basic types of graphs:
• Directed graphs
• Undirected graphs
CS 441 Discrete mathematics for CS
a
c
b
c d
a b
M. Hauskrecht
Complete graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.
CS 441 Discrete mathematics for CS
3
M. Hauskrecht
A cycle
A cycle Cn for n ? 3 consists of n vertices v1, v2 ,? , vn, and edges
{v1, v2}, {v2, v3} ,? , {vn-1, vn}, {vn, v1}.
CS 441 Discrete mathematics for CS
M. Hauskrecht
N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.
CS 441 Discrete mathematics for CS
4
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
5
M. Hauskrecht
Subgraphs
Definition: A subgraph of a graph G = (V,E) is a graph (W,F),
where W ? V and F ? E. A subgraph H of G is a proper subgraph
of G if H ? G.
Example: K5 and one of its subgraphs.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Subgraphs
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph (W,F),
where the edge set F contains an edge in E if and only if both
endpoints are in W.
Example: K5 and the subgraph induced by W = {a,b,c,e}.
CS 441 Discrete mathematics for CS
6
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
7
M. Hauskrecht
Adjacency matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| =
n. Arbitrarily list the vertices of G as v1, v2, … , vn. The adjacency
matrix AG of G, with respect to the listing of vertices, is the n × n
zero-one matrix with 1 as its (i, j)th entry when vi and vj are
adjacent, and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij],
then
Example:
CS 441 Discrete mathematics for CS
The ordering of
vertices is a, b, c, d.
M. Hauskrecht
Adjacency matrices
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position
of the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
Example: The adjacency matrix of the pseudograph shown here
using the ordering of vertices a, b, c, d.
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
Are the two graphs isomorphic?
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
u1 ? v1
u2 ? v4
u3 ? v2
u4 ? v3
Are the two graphs isomorphic?
9
M. Hauskrecht
Connectivity in the graphs, paths
Informal Definition: A path is a sequence of edges that begins at
a vertex of a graph and travels from vertex to vertex along edges of
the graph. As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these.
Applications: Numerous problems can be modeled with paths
formed by traveling along edges of graphs such as:
– determining whether a message can be sent between two
computers.
– efficiently planning routes for mail/message delivery.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Connectivity in the graphs
• We can use the adjacency matrix of a graph to find the number of
the different paths between two vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
Paths of length 4.
CS 441 Discrete mathematics for CS
A =
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
CS 441 Discrete mathematics for CS
A =
Paths of length 4: The adjacency matrix of
G (ordering the vertices as a, b, c, d) is
given above. Hence the number of paths of
length four from a to d is the (1, 4)th entry
of A4
A4 =
11
M. Hauskrecht
Trees
Definition: A tree is a connected undirected graph with no
simple circuits.
Examples:
CS 441 Discrete mathematics for CS
Tree: yes Tree: yes Tree: no Tree: no
M. Hauskrecht
Connectivity in the graphs
Definition: A forest is a graph that has no simple circuit, but is not
connected. Each of the connected components in a forest is a tree.
Example:
CS 441 Discrete mathematics for CS
12
M. Hauskrecht
Trees
Theorem: An undirected graph is a tree if and only if there is a
unique simple path between any two of its vertices.
CS 441 Discrete mathematics for CS
A
B
C D E
G F
M. Hauskrecht
Application of trees
Examples:
• The organization of a computer file system into directories,
subdirectories, and files is naturally represented as a tree.
• structure of organizations.
CS 441 Discrete mathematics for CS
13
M. Hauskrecht
Rooted trees
Definition: A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed away from the
root.
Note: An unrooted tree can be converted into different rooted trees
when one of the vertices is chosen as the root.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Rooted trees - terminology
• If v is a vertex of a rooted tree other than the root, the parent of v is
the unique vertex u such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u. Vertices with the
same parent are called siblings.
CS 441 Discrete mathematics for CS
Parent of g: a
Children of g: h,j,k
Siblings of g: b,f
14
M. Hauskrecht
Rooted trees - terminology
• The ancestors of a vertex are the vertices on the path from the root
to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an
ancestor.
CS 441 Discrete mathematics for CS
Ancestors of j: g,a
Descendants of j: l,m
M. Hauskrecht
Rooted trees - terminology
• A vertex of a rooted tree with no children is called a leaf. Vertices
that have children are called internal vertices.
CS 441 Discrete mathematics for CS
Leafs: d,e,k, l,m
Examples of internal nodes:
b,g,h
15
M. Hauskrecht
Rooted trees - terminology
• If a is a vertex in a tree, the subtree with a as its root is the
subgraph of the tree consisting of a and its descendants and all
edges incident to these descendants.
CS 441 Discrete mathematics for CS
M. Hauskrecht
M-ary tree
Definition: A rooted tree is called an m-ary tree if every internal
vertex has no more than m children. The tree is called a full m-ary
tree if every internal vertex has exactly m children. An m-ary tree
with m = 2 is called a binary tree.
Example: Are the following rooted trees full m-ary trees for some
positive integer m?
CS 441 Discrete mathematics for CS
16
M. Hauskrecht
Binary trees
Definition: A binary tree is an ordered rooted where each internal
vertex has at most two children. If an internal vertex of a binary
tree has two children, the first is called the left child and the second
the right child. The tree rooted at the left child of a vertex is called
the left subtree of this vertex, and the tree rooted at the right child
of a vertex is called the right subtree of this vertex.
CS 441 Discrete mathematics for CS
Graphs: basics
Basic types of graphs:
• Directed graphs
• Undirected graphs
CS 441 Discrete mathematics for CS
a
c
b
c d
a b
M. Hauskrecht
Complete graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.
CS 441 Discrete mathematics for CS
3
M. Hauskrecht
A cycle
A cycle Cn for n ? 3 consists of n vertices v1, v2 ,? , vn, and edges
{v1, v2}, {v2, v3} ,? , {vn-1, vn}, {vn, v1}.
CS 441 Discrete mathematics for CS
M. Hauskrecht
N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.
CS 441 Discrete mathematics for CS
4
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
5
M. Hauskrecht
Subgraphs
Definition: A subgraph of a graph G = (V,E) is a graph (W,F),
where W ? V and F ? E. A subgraph H of G is a proper subgraph
of G if H ? G.
Example: K5 and one of its subgraphs.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Subgraphs
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph (W,F),
where the edge set F contains an edge in E if and only if both
endpoints are in W.
Example: K5 and the subgraph induced by W = {a,b,c,e}.
CS 441 Discrete mathematics for CS
6
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
7
M. Hauskrecht
Adjacency matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| =
n. Arbitrarily list the vertices of G as v1, v2, … , vn. The adjacency
matrix AG of G, with respect to the listing of vertices, is the n × n
zero-one matrix with 1 as its (i, j)th entry when vi and vj are
adjacent, and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij],
then
Example:
CS 441 Discrete mathematics for CS
The ordering of
vertices is a, b, c, d.
M. Hauskrecht
Adjacency matrices
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position
of the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
Example: The adjacency matrix of the pseudograph shown here
using the ordering of vertices a, b, c, d.
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
Are the two graphs isomorphic?
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
u1 ? v1
u2 ? v4
u3 ? v2
u4 ? v3
Are the two graphs isomorphic?
9
M. Hauskrecht
Connectivity in the graphs, paths
Informal Definition: A path is a sequence of edges that begins at
a vertex of a graph and travels from vertex to vertex along edges of
the graph. As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these.
Applications: Numerous problems can be modeled with paths
formed by traveling along edges of graphs such as:
– determining whether a message can be sent between two
computers.
– efficiently planning routes for mail/message delivery.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Connectivity in the graphs
• We can use the adjacency matrix of a graph to find the number of
the different paths between two vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
Paths of length 4.
CS 441 Discrete mathematics for CS
A =
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
CS 441 Discrete mathematics for CS
A =
Paths of length 4: The adjacency matrix of
G (ordering the vertices as a, b, c, d) is
given above. Hence the number of paths of
length four from a to d is the (1, 4)th entry
of A4
A4 =
11
M. Hauskrecht
Trees
Definition: A tree is a connected undirected graph with no
simple circuits.
Examples:
CS 441 Discrete mathematics for CS
Tree: yes Tree: yes Tree: no Tree: no
M. Hauskrecht
Connectivity in the graphs
Definition: A forest is a graph that has no simple circuit, but is not
connected. Each of the connected components in a forest is a tree.
Example:
CS 441 Discrete mathematics for CS
12
M. Hauskrecht
Trees
Theorem: An undirected graph is a tree if and only if there is a
unique simple path between any two of its vertices.
CS 441 Discrete mathematics for CS
A
B
C D E
G F
M. Hauskrecht
Application of trees
Examples:
• The organization of a computer file system into directories,
subdirectories, and files is naturally represented as a tree.
• structure of organizations.
CS 441 Discrete mathematics for CS
13
M. Hauskrecht
Rooted trees
Definition: A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed away from the
root.
Note: An unrooted tree can be converted into different rooted trees
when one of the vertices is chosen as the root.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Rooted trees - terminology
• If v is a vertex of a rooted tree other than the root, the parent of v is
the unique vertex u such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u. Vertices with the
same parent are called siblings.
CS 441 Discrete mathematics for CS
Parent of g: a
Children of g: h,j,k
Siblings of g: b,f
14
M. Hauskrecht
Rooted trees - terminology
• The ancestors of a vertex are the vertices on the path from the root
to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an
ancestor.
CS 441 Discrete mathematics for CS
Ancestors of j: g,a
Descendants of j: l,m
M. Hauskrecht
Rooted trees - terminology
• A vertex of a rooted tree with no children is called a leaf. Vertices
that have children are called internal vertices.
CS 441 Discrete mathematics for CS
Leafs: d,e,k, l,m
Examples of internal nodes:
b,g,h
15
M. Hauskrecht
Rooted trees - terminology
• If a is a vertex in a tree, the subtree with a as its root is the
subgraph of the tree consisting of a and its descendants and all
edges incident to these descendants.
CS 441 Discrete mathematics for CS
M. Hauskrecht
M-ary tree
Definition: A rooted tree is called an m-ary tree if every internal
vertex has no more than m children. The tree is called a full m-ary
tree if every internal vertex has exactly m children. An m-ary tree
with m = 2 is called a binary tree.
Example: Are the following rooted trees full m-ary trees for some
positive integer m?
CS 441 Discrete mathematics for CS
16
M. Hauskrecht
Binary trees
Definition: A binary tree is an ordered rooted where each internal
vertex has at most two children. If an internal vertex of a binary
tree has two children, the first is called the left child and the second
the right child. The tree rooted at the left child of a vertex is called
the left subtree of this vertex, and the tree rooted at the right child
of a vertex is called the right subtree of this vertex.
CS 441 Discrete mathematics for CS
Graphs: basics
Basic types of graphs:
• Directed graphs
• Undirected graphs
CS 441 Discrete mathematics for CS
a
c
b
c d
a b
M. Hauskrecht
Complete graphs
A complete graph on n vertices, denoted by Kn, is the simple
graph that contains exactly one edge between each pair of distinct
vertices.
CS 441 Discrete mathematics for CS
3
M. Hauskrecht
A cycle
A cycle Cn for n ? 3 consists of n vertices v1, v2 ,? , vn, and edges
{v1, v2}, {v2, v3} ,? , {vn-1, vn}, {vn, v1}.
CS 441 Discrete mathematics for CS
M. Hauskrecht
N-dimensional hypercube
An n-dimensional hypercube, or n-cube, Qn, is a graph with 2n
vertices representing all bit strings of length n, where there is an
edge between two vertices that differ in exactly one bit position.
CS 441 Discrete mathematics for CS
4
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Bipartite graphs
Definition: A simple graph G is bipartite if V can be partitioned
into two disjoint subsets V1 and V2 such that every edge connects a
vertex in V1 and a vertex in V2. In other words, there are no edges
which connect two vertices in V1 or in V2.
Note: An equivalent definition of a bipartite graph is a graph
where it is possible to color the vertices red or blue so that no two
adjacent vertices are the same color.
CS 441 Discrete mathematics for CS
5
M. Hauskrecht
Subgraphs
Definition: A subgraph of a graph G = (V,E) is a graph (W,F),
where W ? V and F ? E. A subgraph H of G is a proper subgraph
of G if H ? G.
Example: K5 and one of its subgraphs.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Subgraphs
Definition: Let G = (V, E) be a simple graph. The subgraph
induced by a subset W of the vertex set V is the graph (W,F),
where the edge set F contains an edge in E if and only if both
endpoints are in W.
Example: K5 and the subgraph induced by W = {a,b,c,e}.
CS 441 Discrete mathematics for CS
6
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
M. Hauskrecht
Representation of graphs
Definition: An adjacency list can be used to represent a graph with
no multiple edges by specifying the vertices that are adjacent to
each vertex of the graph.
Example:
CS 441 Discrete mathematics for CS
7
M. Hauskrecht
Adjacency matrices
Definition: Suppose that G = (V, E) is a simple graph where |V| =
n. Arbitrarily list the vertices of G as v1, v2, … , vn. The adjacency
matrix AG of G, with respect to the listing of vertices, is the n × n
zero-one matrix with 1 as its (i, j)th entry when vi and vj are
adjacent, and 0 as its (i, j)th entry when they are not adjacent.
– In other words, if the graphs adjacency matrix is AG = [aij],
then
Example:
CS 441 Discrete mathematics for CS
The ordering of
vertices is a, b, c, d.
M. Hauskrecht
Adjacency matrices
• Adjacency matrices can also be used to represent graphs with loops
and multiple edges.
• A loop at the vertex vi is represented by a 1 at the (i, i)th position
of the matrix.
• When multiple edges connect the same pair of vertices vi and vj, (or
if multiple loops are present at the same vertex), the (i, j)th entry
equals the number of edges connecting the pair of vertices.
Example: The adjacency matrix of the pseudograph shown here
using the ordering of vertices a, b, c, d.
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
Are the two graphs isomorphic?
M. Hauskrecht
Graph isomorphism
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a one-to-one and onto function f from V1 to
V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2 , for all a and b in V1 . Such a
function f is called an isomorphism. Two simple graphs that are not
isomorphic are called nonisomorphic.
Example:
CS 441 Discrete mathematics for CS
u1 ? v1
u2 ? v4
u3 ? v2
u4 ? v3
Are the two graphs isomorphic?
9
M. Hauskrecht
Connectivity in the graphs, paths
Informal Definition: A path is a sequence of edges that begins at
a vertex of a graph and travels from vertex to vertex along edges of
the graph. As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these.
Applications: Numerous problems can be modeled with paths
formed by traveling along edges of graphs such as:
– determining whether a message can be sent between two
computers.
– efficiently planning routes for mail/message delivery.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Connectivity in the graphs
• We can use the adjacency matrix of a graph to find the number of
the different paths between two vertices in the graph.
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
Paths of length 4.
CS 441 Discrete mathematics for CS
A =
M. Hauskrecht
Connectivity in the graphs
Theorem: Let G be a graph with adjacency matrix A with respect
to the ordering v1, … , vn of vertices (with directed or undirected
edges, multiple edges and loops allowed). The number of different
paths of length r from vi to vj, where r >0 is a positive integer,
equals the (i,j)th entry of Ar.
Example:
CS 441 Discrete mathematics for CS
A =
Paths of length 4: The adjacency matrix of
G (ordering the vertices as a, b, c, d) is
given above. Hence the number of paths of
length four from a to d is the (1, 4)th entry
of A4
A4 =
11
M. Hauskrecht
Trees
Definition: A tree is a connected undirected graph with no
simple circuits.
Examples:
CS 441 Discrete mathematics for CS
Tree: yes Tree: yes Tree: no Tree: no
M. Hauskrecht
Connectivity in the graphs
Definition: A forest is a graph that has no simple circuit, but is not
connected. Each of the connected components in a forest is a tree.
Example:
CS 441 Discrete mathematics for CS
12
M. Hauskrecht
Trees
Theorem: An undirected graph is a tree if and only if there is a
unique simple path between any two of its vertices.
CS 441 Discrete mathematics for CS
A
B
C D E
G F
M. Hauskrecht
Application of trees
Examples:
• The organization of a computer file system into directories,
subdirectories, and files is naturally represented as a tree.
• structure of organizations.
CS 441 Discrete mathematics for CS
13
M. Hauskrecht
Rooted trees
Definition: A rooted tree is a tree in which one vertex has been
designated as the root and every edge is directed away from the
root.
Note: An unrooted tree can be converted into different rooted trees
when one of the vertices is chosen as the root.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Rooted trees - terminology
• If v is a vertex of a rooted tree other than the root, the parent of v is
the unique vertex u such that there is a directed edge from u to v.
When u is a parent of v, v is called a child of u. Vertices with the
same parent are called siblings.
CS 441 Discrete mathematics for CS
Parent of g: a
Children of g: h,j,k
Siblings of g: b,f
14
M. Hauskrecht
Rooted trees - terminology
• The ancestors of a vertex are the vertices on the path from the root
to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an
ancestor.
CS 441 Discrete mathematics for CS
Ancestors of j: g,a
Descendants of j: l,m
M. Hauskrecht
Rooted trees - terminology
• A vertex of a rooted tree with no children is called a leaf. Vertices
that have children are called internal vertices.
CS 441 Discrete mathematics for CS
Leafs: d,e,k, l,m
Examples of internal nodes:
b,g,h
15
M. Hauskrecht
Rooted trees - terminology
• If a is a vertex in a tree, the subtree with a as its root is the
subgraph of the tree consisting of a and its descendants and all
edges incident to these descendants.
CS 441 Discrete mathematics for CS
M. Hauskrecht
M-ary tree
Definition: A rooted tree is called an m-ary tree if every internal
vertex has no more than m children. The tree is called a full m-ary
tree if every internal vertex has exactly m children. An m-ary tree
with m = 2 is called a binary tree.
Example: Are the following rooted trees full m-ary trees for some
positive integer m?
CS 441 Discrete mathematics for CS
16
M. Hauskrecht
Binary trees
Definition: A binary tree is an ordered rooted where each internal
vertex has at most two children. If an internal vertex of a binary
tree has two children, the first is called the left child and the second
the right child. The tree rooted at the left child of a vertex is called
the left subtree of this vertex, and the tree rooted at the right child
of a vertex is called the right subtree of this vertex.
CS 441 Discrete mathematics for CS