المحاضرة 4 كورس ثاني

Relations IV
Equivalence relation
Definition: A relation R on a set A is called an equivalence
relation if it is reflexive, symmetric and transitive.
Equivalence relation
Definition: A relation R on a set A is called an equivalence
relation if it is reflexive, symmetric and transitive.
Example: Let A = {0,1,2,3,4,5,6} and
• R= {(a,b)| a,b ? A, a ? b mod 3} (a is congruent to b modulo 3)
Congruencies:
• 0 mod 3 = 0 1 mod 3 = 1 2 mod 3 = 2 3 mod 3 = 0
• 4 mod 3 = 1 5 mod 3 = 2 6 mod 3 = 0
Relation R has the following pairs:
• (0,0) (0,3), (3,0), (0,6), (6,0)
• (3,3), (3,6) (6,3), (6,6) (1,1),(1,4), (4,1), (4,4)
• (2,2), (2,5), (5,2), (5,5)
Equivalence relation
• Relation R on A={0,1,2,3,4,5,6} has the following pairs:
(0,0) (0,3), (3,0), (0,6), (6,0)
(3,3), (3,6) (6,3), (6,6) (1,1),(1,4), (4,1), (4,4)
(2,2), (2,5), (5,2), (5,5)
• Is R reflexive? Yes.
• Is R symmetric? Yes.
• Is R transitive. Yes.
Then
• R is an equivalence relation.
1
2
3
4
5
6
Equivalence class
Definition: Let R be an equivalence relation on a set A. The set
{ x ? A ? a R x} is called the equivalence class of a, denoted
by [a]R or simply [a]. If b ? [a] then b is called a representative
of this equivalence class.
Example:
• Assume R={(a,b) | a ? b mod 3} for A={0,1,2,3,4,5,6}
R= {(0,0), (0,3), (3,0), (0,6), (6,0),(3,3), (3,6) (6,3), (6,6),
(1,1),(1,4), (4,1), (4,4), (2,2), (2,5), (5,2), (5,5)}
• Pick an element a =0.
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
• Element 3: [3]R= {0,3,6} = [0]R = [6]R
• Element 4: [4]R= {1,4} = [1]R Element 5: [5]R= {2,5} = [2]R
CS 441 Discrete mathematics for CS M. Hauskrecht
Equivalence class
Example:
• Assume R={(a,b) | a ? b mod 3} for A={0,1,2,3,4,5,6}
• R= {(0,0), (0,3), (3,0), (0,6), (6,0),(3,3), (3,6) (6,3), (6,6),
(1,1),(1,4), (4,1), (4,4), (2,2), (2,5), (5,2), (5,5)}
Three different equivalence classes all together:
• [0]R = [3]R =[6]R = {0,3,6}
• [1]R= [4]R= {1,4}
• [2]R= [5]R= {2,5}
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Partition of a set S
Definition: Let S be a set. A collection of nonempty subsets of S
A1, A2, ..., Ak is called a partition of S if:
• Ai ? Aj = ?, i ? j and ?
k
i
i S A
?1
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Partition of a set S
Definition: Let S be a set. A collection of nonempty subsets of S
A1, A2, ..., Ak is called a partition of S if:
• Ai ? Aj = ?, i ? j and
Example: Let S={1,2,3,4,5,6} and
• A1 ={0,3,6} A2 ={1,4} A3 = {2,5}
• Is A1, A2,, A3 a partition of S ? Yes.
• Give a partition of S ?
• {0,2,4,6} {1,3,5}
• {0} {1,2} {3,4,5} {6}
? k
i
i S A
?1
?
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Equivalence classes and partitions
Theorem: Let R be an equivalence relation on a set A. Then the
union of all the equivalence classes of R is A:
Proof: an element a of A is in its own equivalence class [a]R so
union cover A.
Theorem: The equivalence classes form a partition of A.
Proof: The equivalence classes split A into disjoint subsets.
Theorem : Let {A1, A2, .. Ai ,..} be a partitioning of S. Then there is
an equivalence relation R on S, that has the sets Ai as its
equivalence classes.
? k
a A
R A a
?
? [ ]
CS 441 Discrete mathematics for CS M. Hauskrecht
Partial orderings
Definition: A relation R on a set S is called a partial ordering, or
partial order, if it is reflexive, antisymmetric, and transitive. A
set together with a partial ordering R is called a partially ordered
set, or poset, and is denoted by (S, R). Members of S are called
elements of the poset.
Example: Assume R denotes the “greater than or equal” relation
(??) on the set S={1,2,3,4,5}.
• Is the relation reflexive? Yes
• Is it antisymmetric? Yes
• Is it transitive? Yes
• Conclusion: R is a partial ordering.
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Partial orderings
Example: Assume R is the divisibility relation (?) on the set of
integers S={1,2,3,4,5,6}
• Is the relation reflexive? Yes
• Is it antisymmetric? Yes
• Is it transitive? Yes
• Conclusion: R is a partial ordering.
CS 441 Discrete mathematics for CS M. Hauskrecht
Comparability
Definition 1: The elements a and b of a poset (S,? ) are
comparable if either a ? b or b ? a. When a and b are elements
of S so that neither a ? b nor b ? a holds, then a and b are
called incomparable.
Definition 2: If (S,? ) is a poset and every two elements of S are
comparable, S is called a totally ordered or linearly ordered set,
and ? is called a total order or a linear order. A totally ordered
set is also called a chain.
Definition 3: (S,? ) is a well-ordered set if it is a poset such that ?
is a total ordering and every nonempty subset of S has a least
element.
7
M. Hauskrecht
Lexicographical ordering
Definition: Given two posets (A1,?1) and (A2,?2), the lexicographic
ordering on A1 ? A2 is defined by specifying that (a1, a2) is less
than (b1,b2), that is, (a1, a2) ? (b1,b2), either if a1 ?1 b1 or if a1 ??
b1 then a2 ?2 b2.
The definition can be extended to a lexicographic ordering on strings
Example: Consider strings of lowercase English letters. A
lexicographic ordering can be defined using the ordering of the
letters in the alphabet. This is the same ordering as that used in
dictionaries.
– discreet ? discrete, because these strings differ in the seventh
position and e ? t.
– discreet ? discreetness, because the first eight letters agree, but
the second string is longer.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Hasse diagram
Definition: A Hasse diagram is a visual representation of a
partial ordering that leaves out edges that must be present
because of the reflexive and transitive properties.
(a) A partial ordering. The loops are due to the reflexive property
(b) The edges that must be present due to the transitive property
are deleted
(c) The Hasse diagram for the partial ordering (a).
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Procedure for constructing Hasse diagram
• To represent a finite poset (S,? ) using a Hasse diagram, start with
the directed graph of the relation:
– Remove the loops (a, a) present at every vertex due to the
reflexive property.
– Remove all edges (x, y) for which there is an element z ? S
such that x ? z and z ? y. These are the edges that must be
present due to the transitive property.
– Arrange each edge so that its initial vertex is below the terminal
vertex. Remove all the arrows, because all edges point upwards
toward their terminal vertex.
CS 441 Discrete mathematics for CS
CS 441 Discrete mathematics for CS M. Hauskrecht
CS 441 Discrete Mathematics for CS
Lecture 24b
Milos Hauskrecht
milos@cs.pitt.edu
5329 Sennott Square
Graphs
(chapter 10)
9
M. Hauskrecht
Definition of a graph
• Definition: A graph G = (V, E) consists of a nonempty set V of
vertices (or nodes) and a set E of edges. Each edge has either one
or two vertices associated with it, called its endpoints. An edge is
said to connect its endpoints.
• Example:
CS 441 Discrete mathematics for CS
a
c
b
d
M. Hauskrecht
Terminology
• In a simple graph each edge connects two different vertices and
no two edges connect the same pair of vertices.
• Multigraphs may have multiple edges connecting the same two
vertices. When m different edges connect the vertices u and v, we
say that {u,v} is an edge of multiplicity m.
• An edge that connects a vertex to itself is called a loop.
• A pseudograph may include loops, as well as multiple edges
connecting the same pair of vertices.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Terminology
• In a simple graph each edge connects two different vertices and no
two edges connect the same pair of vertices.
• Multigraphs may have multiple edges connecting the same two
vertices. When m different edges connect the vertices u and v, we
say that {u,v} is an edge of multiplicity m.
• An edge that connects a vertex to itself is called a loop.
• A pseudograph may include loops, as well as multiple edges
connecting the same pair of vertices.
CS 441 Discrete mathematics for CS
a b
c
M. Hauskrecht
Directed graph
Definition: An directed graph (or digraph) G = (V, E) consists of a
nonempty set V of vertices (or nodes) and a set E of directed edges
(or arcs). Each edge is associated with an ordered pair of vertices.
The directed edge associated with the ordered pair (u,v) is said to
start at u and end at v.
Remark:
– Graphs where the end points of an edge are not ordered are said
to be undirected graphs.
CS 441 Discrete mathematics for CS
11
M. Hauskrecht
Directed graph
• A simple directed graph has no loops and no multiple
edges.
Example:
• A directed multigraph may have multiple directed edges.
When there are m directed edges from the vertex u to the
vertex v, we say that (u,v) is an edge of multiplicity m.
Example:
• multiplicity of (a,b) is ?
• and the multiplicity of ??b,c?? is ?
CS 441 Discrete mathematics for CS
a b
c
c
Equivalence class
Definition: Let R be an equivalence relation on a set A. The set
{ x ? A ? a R x} is called the equivalence class of a, denoted
by [a]R or simply [a]. If b ? [a] then b is called a representative
of this equivalence class.
Example:
• Assume R={(a,b) | a ? b mod 3} for A={0,1,2,3,4,5,6}
R= {(0,0), (0,3), (3,0), (0,6), (6,0),(3,3), (3,6) (6,3), (6,6),
(1,1),(1,4), (4,1), (4,4), (2,2), (2,5), (5,2), (5,5)}
• Pick an element a =0.
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
• Element 3: [3]R= {0,3,6} = [0]R = [6]R
• Element 4: [4]R= {1,4} = [1]R Element 5: [5]R= {2,5} = [2]R
CS 441 Discrete mathematics for CS M. Hauskrecht
Equivalence class
Example:
• Assume R={(a,b) | a ? b mod 3} for A={0,1,2,3,4,5,6}
• R= {(0,0), (0,3), (3,0), (0,6), (6,0),(3,3), (3,6) (6,3), (6,6),
(1,1),(1,4), (4,1), (4,4), (2,2), (2,5), (5,2), (5,5)}
Three different equivalence classes all together:
• [0]R = [3]R =[6]R = {0,3,6}
• [1]R= [4]R= {1,4}
• [2]R= [5]R= {2,5}
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Partition of a set S
Definition: Let S be a set. A collection of nonempty subsets of S
A1, A2, ..., Ak is called a partition of S if:
• Ai ? Aj = ?, i ? j and ?
k
i
i S A
?1
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Partition of a set S
Definition: Let S be a set. A collection of nonempty subsets of S
A1, A2, ..., Ak is called a partition of S if:
• Ai ? Aj = ?, i ? j and
Example: Let S={1,2,3,4,5,6} and
• A1 ={0,3,6} A2 ={1,4} A3 = {2,5}
• Is A1, A2,, A3 a partition of S ? Yes.
• Give a partition of S ?
• {0,2,4,6} {1,3,5}
• {0} {1,2} {3,4,5} {6}
? k
i
i S A
?1
?
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Equivalence classes and partitions
Theorem: Let R be an equivalence relation on a set A. Then the
union of all the equivalence classes of R is A:
Proof: an element a of A is in its own equivalence class [a]R so
union cover A.
Theorem: The equivalence classes form a partition of A.
Proof: The equivalence classes split A into disjoint subsets.
Theorem : Let {A1, A2, .. Ai ,..} be a partitioning of S. Then there is
an equivalence relation R on S, that has the sets Ai as its
equivalence classes.
? k
a A
R A a
?
? [ ]
CS 441 Discrete mathematics for CS M. Hauskrecht
Partial orderings
Definition: A relation R on a set S is called a partial ordering, or
partial order, if it is reflexive, antisymmetric, and transitive. A
set together with a partial ordering R is called a partially ordered
set, or poset, and is denoted by (S, R). Members of S are called
elements of the poset.
Example: Assume R denotes the “greater than or equal” relation
(??) on the set S={1,2,3,4,5}.
• Is the relation reflexive? Yes
• Is it antisymmetric? Yes
• Is it transitive? Yes
• Conclusion: R is a partial ordering.
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Partial orderings
Example: Assume R is the divisibility relation (?) on the set of
integers S={1,2,3,4,5,6}
• Is the relation reflexive? Yes
• Is it antisymmetric? Yes
• Is it transitive? Yes
• Conclusion: R is a partial ordering.
CS 441 Discrete mathematics for CS M. Hauskrecht
Comparability
Definition 1: The elements a and b of a poset (S,? ) are
comparable if either a ? b or b ? a. When a and b are elements
of S so that neither a ? b nor b ? a holds, then a and b are
called incomparable.
Definition 2: If (S,? ) is a poset and every two elements of S are
comparable, S is called a totally ordered or linearly ordered set,
and ? is called a total order or a linear order. A totally ordered
set is also called a chain.
Definition 3: (S,? ) is a well-ordered set if it is a poset such that ?
is a total ordering and every nonempty subset of S has a least
element.
7
M. Hauskrecht
Lexicographical ordering
Definition: Given two posets (A1,?1) and (A2,?2), the lexicographic
ordering on A1 ? A2 is defined by specifying that (a1, a2) is less
than (b1,b2), that is, (a1, a2) ? (b1,b2), either if a1 ?1 b1 or if a1 ??
b1 then a2 ?2 b2.
The definition can be extended to a lexicographic ordering on strings
Example: Consider strings of lowercase English letters. A
lexicographic ordering can be defined using the ordering of the
letters in the alphabet. This is the same ordering as that used in
dictionaries.
– discreet ? discrete, because these strings differ in the seventh
position and e ? t.
– discreet ? discreetness, because the first eight letters agree, but
the second string is longer.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Hasse diagram
Definition: A Hasse diagram is a visual representation of a
partial ordering that leaves out edges that must be present
because of the reflexive and transitive properties.
(a) A partial ordering. The loops are due to the reflexive property
(b) The edges that must be present due to the transitive property
are deleted
(c) The Hasse diagram for the partial ordering (a).
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Procedure for constructing Hasse diagram
• To represent a finite poset (S,? ) using a Hasse diagram, start with
the directed graph of the relation:
– Remove the loops (a, a) present at every vertex due to the
reflexive property.
– Remove all edges (x, y) for which there is an element z ? S
such that x ? z and z ? y. These are the edges that must be
present due to the transitive property.
– Arrange each edge so that its initial vertex is below the terminal
vertex. Remove all the arrows, because all edges point upwards
toward their terminal vertex.
CS 441 Discrete mathematics for CS
CS 441 Discrete mathematics for CS M. Hauskrecht
CS 441 Discrete Mathematics for CS
Lecture 24b
Milos Hauskrecht
milos@cs.pitt.edu
5329 Sennott Square
Graphs
(chapter 10)
9
M. Hauskrecht
Definition of a graph
• Definition: A graph G = (V, E) consists of a nonempty set V of
vertices (or nodes) and a set E of edges. Each edge has either one
or two vertices associated with it, called its endpoints. An edge is
said to connect its endpoints.
• Example:
CS 441 Discrete mathematics for CS
a
c
b
d
M. Hauskrecht
Terminology
• In a simple graph each edge connects two different vertices and
no two edges connect the same pair of vertices.
• Multigraphs may have multiple edges connecting the same two
vertices. When m different edges connect the vertices u and v, we
say that {u,v} is an edge of multiplicity m.
• An edge that connects a vertex to itself is called a loop.
• A pseudograph may include loops, as well as multiple edges
connecting the same pair of vertices.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Terminology
• In a simple graph each edge connects two different vertices and no
two edges connect the same pair of vertices.
• Multigraphs may have multiple edges connecting the same two
vertices. When m different edges connect the vertices u and v, we
say that {u,v} is an edge of multiplicity m.
• An edge that connects a vertex to itself is called a loop.
• A pseudograph may include loops, as well as multiple edges
connecting the same pair of vertices.
CS 441 Discrete mathematics for CS
a b
c
M. Hauskrecht
Directed graph
Definition: An directed graph (or digraph) G = (V, E) consists of a
nonempty set V of vertices (or nodes) and a set E of directed edges
(or arcs). Each edge is associated with an ordered pair of vertices.
The directed edge associated with the ordered pair (u,v) is said to
start at u and end at v.
Remark:
– Graphs where the end points of an edge are not ordered are said
to be undirected graphs.
CS 441 Discrete mathematics for CS
11
M. Hauskrecht
Directed graph
• A simple directed graph has no loops and no multiple
edges.
Example:
• A directed multigraph may have multiple directed edges.
When there are m directed edges from the vertex u to the
vertex v, we say that (u,v) is an edge of multiplicity m.
Example:
• multiplicity of (a,b) is ?
• and the multiplicity of ??b,c?? is ?
CS 441 Discrete mathematics for CS
a b
c
c
Equivalence class
Definition: Let R be an equivalence relation on a set A. The set
{ x ? A ? a R x} is called the equivalence class of a, denoted
by [a]R or simply [a]. If b ? [a] then b is called a representative
of this equivalence class.
Example:
• Assume R={(a,b) | a ? b mod 3} for A={0,1,2,3,4,5,6}
R= {(0,0), (0,3), (3,0), (0,6), (6,0),(3,3), (3,6) (6,3), (6,6),
(1,1),(1,4), (4,1), (4,4), (2,2), (2,5), (5,2), (5,5)}
• Pick an element a =0.
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
• Element 3: [3]R= {0,3,6} = [0]R = [6]R
• Element 4: [4]R= {1,4} = [1]R Element 5: [5]R= {2,5} = [2]R
CS 441 Discrete mathematics for CS M. Hauskrecht
Equivalence class
Example:
• Assume R={(a,b) | a ? b mod 3} for A={0,1,2,3,4,5,6}
• R= {(0,0), (0,3), (3,0), (0,6), (6,0),(3,3), (3,6) (6,3), (6,6),
(1,1),(1,4), (4,1), (4,4), (2,2), (2,5), (5,2), (5,5)}
Three different equivalence classes all together:
• [0]R = [3]R =[6]R = {0,3,6}
• [1]R= [4]R= {1,4}
• [2]R= [5]R= {2,5}
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Partition of a set S
Definition: Let S be a set. A collection of nonempty subsets of S
A1, A2, ..., Ak is called a partition of S if:
• Ai ? Aj = ?, i ? j and ?
k
i
i S A
?1
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Partition of a set S
Definition: Let S be a set. A collection of nonempty subsets of S
A1, A2, ..., Ak is called a partition of S if:
• Ai ? Aj = ?, i ? j and
Example: Let S={1,2,3,4,5,6} and
• A1 ={0,3,6} A2 ={1,4} A3 = {2,5}
• Is A1, A2,, A3 a partition of S ? Yes.
• Give a partition of S ?
• {0,2,4,6} {1,3,5}
• {0} {1,2} {3,4,5} {6}
? k
i
i S A
?1
?
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Equivalence classes and partitions
Theorem: Let R be an equivalence relation on a set A. Then the
union of all the equivalence classes of R is A:
Proof: an element a of A is in its own equivalence class [a]R so
union cover A.
Theorem: The equivalence classes form a partition of A.
Proof: The equivalence classes split A into disjoint subsets.
Theorem : Let {A1, A2, .. Ai ,..} be a partitioning of S. Then there is
an equivalence relation R on S, that has the sets Ai as its
equivalence classes.
? k
a A
R A a
?
? [ ]
CS 441 Discrete mathematics for CS M. Hauskrecht
Partial orderings
Definition: A relation R on a set S is called a partial ordering, or
partial order, if it is reflexive, antisymmetric, and transitive. A
set together with a partial ordering R is called a partially ordered
set, or poset, and is denoted by (S, R). Members of S are called
elements of the poset.
Example: Assume R denotes the “greater than or equal” relation
(??) on the set S={1,2,3,4,5}.
• Is the relation reflexive? Yes
• Is it antisymmetric? Yes
• Is it transitive? Yes
• Conclusion: R is a partial ordering.
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Partial orderings
Example: Assume R is the divisibility relation (?) on the set of
integers S={1,2,3,4,5,6}
• Is the relation reflexive? Yes
• Is it antisymmetric? Yes
• Is it transitive? Yes
• Conclusion: R is a partial ordering.
CS 441 Discrete mathematics for CS M. Hauskrecht
Comparability
Definition 1: The elements a and b of a poset (S,? ) are
comparable if either a ? b or b ? a. When a and b are elements
of S so that neither a ? b nor b ? a holds, then a and b are
called incomparable.
Definition 2: If (S,? ) is a poset and every two elements of S are
comparable, S is called a totally ordered or linearly ordered set,
and ? is called a total order or a linear order. A totally ordered
set is also called a chain.
Definition 3: (S,? ) is a well-ordered set if it is a poset such that ?
is a total ordering and every nonempty subset of S has a least
element.
7
M. Hauskrecht
Lexicographical ordering
Definition: Given two posets (A1,?1) and (A2,?2), the lexicographic
ordering on A1 ? A2 is defined by specifying that (a1, a2) is less
than (b1,b2), that is, (a1, a2) ? (b1,b2), either if a1 ?1 b1 or if a1 ??
b1 then a2 ?2 b2.
The definition can be extended to a lexicographic ordering on strings
Example: Consider strings of lowercase English letters. A
lexicographic ordering can be defined using the ordering of the
letters in the alphabet. This is the same ordering as that used in
dictionaries.
– discreet ? discrete, because these strings differ in the seventh
position and e ? t.
– discreet ? discreetness, because the first eight letters agree, but
the second string is longer.
CS 441 Discrete mathematics for CS
M. Hauskrecht
Hasse diagram
Definition: A Hasse diagram is a visual representation of a
partial ordering that leaves out edges that must be present
because of the reflexive and transitive properties.
(a) A partial ordering. The loops are due to the reflexive property
(b) The edges that must be present due to the transitive property
are deleted
(c) The Hasse diagram for the partial ordering (a).
CS 441 Discrete mathematics for CS
8
M. Hauskrecht
Procedure for constructing Hasse diagram
• To represent a finite poset (S,? ) using a Hasse diagram, start with
the directed graph of the relation:
– Remove the loops (a, a) present at every vertex due to the
reflexive property.
– Remove all edges (x, y) for which there is an element z ? S
such that x ? z and z ? y. These are the edges that must be
present due to the transitive property.
– Arrange each edge so that its initial vertex is below the terminal
vertex. Remove all the arrows, because all edges point upwards
toward their terminal vertex.
CS 441 Discrete mathematics for CS
CS 441 Discrete mathematics for CS M. Hauskrecht
CS 441 Discrete Mathematics for CS
Lecture 24b
Milos Hauskrecht
milos@cs.pitt.edu
5329 Sennott Square
Graphs
(chapter 10)
9
M. Hauskrecht
Definition of a graph
• Definition: A graph G = (V, E) consists of a nonempty set V of
vertices (or nodes) and a set E of edges. Each edge has either one
or two vertices associated with it, called its endpoints. An edge is
said to connect its endpoints.
• Example:
CS 441 Discrete mathematics for CS
a
c
b
d
M. Hauskrecht
Terminology
• In a simple graph each edge connects two different vertices and
no two edges connect the same pair of vertices.
• Multigraphs may have multiple edges connecting the same two
vertices. When m different edges connect the vertices u and v, we
say that {u,v} is an edge of multiplicity m.
• An edge that connects a vertex to itself is called a loop.
• A pseudograph may include loops, as well as multiple edges
connecting the same pair of vertices.
CS 441 Discrete mathematics for CS
10
M. Hauskrecht
Terminology
• In a simple graph each edge connects two different vertices and no
two edges connect the same pair of vertices.
• Multigraphs may have multiple edges connecting the same two
vertices. When m different edges connect the vertices u and v, we
say that {u,v} is an edge of multiplicity m.
• An edge that connects a vertex to itself is called a loop.
• A pseudograph may include loops, as well as multiple edges
connecting the same pair of vertices.
CS 441 Discrete mathematics for CS
a b
c
M. Hauskrecht
Directed graph
Definition: An directed graph (or digraph) G = (V, E) consists of a
nonempty set V of vertices (or nodes) and a set E of directed edges
(or arcs). Each edge is associated with an ordered pair of vertices.
The directed edge associated with the ordered pair (u,v) is said to
start at u and end at v.
Remark:
– Graphs where the end points of an edge are not ordered are said
to be undirected graphs.
CS 441 Discrete mathematics for CS
11
M. Hauskrecht
Directed graph
• A simple directed graph has no loops and no multiple
edges.
Example:
• A directed multigraph may have multiple directed edges.
When there are m directed edges from the vertex u to the
vertex v, we say that (u,v) is an edge of multiplicity m.
Example:
• multiplicity of (a,b) is ?
• and the multiplicity of ??b,c?? is ?
CS 441 Discrete mathematics for CS
a b
c
c