CS 207 Discrete Mathematics – 2012-2013
Nutan Limaye
Indian Institute of Technology, Bombay nutan@cse.iitb.ac.in
Mathematical Reasoning and Mathematical Objects Lecture 6: Relations
Aug 09, 2012
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 1 / 10
Last few classes
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 2 / 10
Recap
Proofs, proof methods.
Sets and properties of sets Functions, properties of functions
Infinite sets and properties of infinite sets.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 3 / 10
Recap
Proofs, proof methods.
Sets and properties of sets
Functions, properties of functions
Infinite sets and properties of infinite sets.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 3 / 10
Recap
Proofs, proof methods.
Sets and properties of sets Functions, properties of functions
Infinite sets and properties of infinite sets.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 3 / 10
Recap
Proofs, proof methods.
Sets and properties of sets Functions, properties of functions
Infinite sets and properties of infinite sets.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 3 / 10
Today
Relations: generalisations of functions
Types and properties of relations
Representation of functions - directed graphs
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 4 / 10
Today
Relations: generalisations of functions Types and properties of relations
Representation of functions - directed graphs
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 4 / 10
Today
Relations: generalisations of functions Types and properties of relations
Representation of functions - directed graphs
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 4 / 10
What are relations?
Relation are used to talk about elements of a set.
A relation R from setAto set B,R(A,B) is a subset ofA×B.
IfA=B for some relation, we denote the relation as R(A). Examples:
A function is a special case of a relation.
R(Z) ={(a,b)|a,b∈Zanda≤b}. R is a relation on the set of integers under which aRb holds for two numbersa,b∈Zif and only ifa≤b.
Let S be a set R(P(S)) ={(A,B)|A,B ∈ P(S) andA⊆B}. Relational databases: practical examples of relations.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 10
What are relations?
Relation are used to talk about elements of a set.
A relation R from setAto set B,R(A,B) is a subset ofA×B.
IfA=B for some relation, we denote the relation as R(A).
Examples:
A function is a special case of a relation.
R(Z) ={(a,b)|a,b∈Zanda≤b}. R is a relation on the set of integers under which aRb holds for two numbersa,b∈Zif and only ifa≤b.
Let S be a set R(P(S)) ={(A,B)|A,B ∈ P(S) andA⊆B}. Relational databases: practical examples of relations.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 10
What are relations?
Relation are used to talk about elements of a set.
A relation R from setAto set B,R(A,B) is a subset ofA×B.
IfA=B for some relation, we denote the relation as R(A).
Examples:
A function is a special case of a relation.
R(Z) ={(a,b)|a,b∈Zanda≤b}. R is a relation on the set of integers under which aRb holds for two numbersa,b∈Zif and only ifa≤b.
Let S be a set R(P(S)) ={(A,B)|A,B ∈ P(S) andA⊆B}. Relational databases: practical examples of relations.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 10
What are relations?
Relation are used to talk about elements of a set.
A relation R from setAto set B,R(A,B) is a subset ofA×B.
IfA=B for some relation, we denote the relation as R(A).
Examples:
A function is a special case of a relation.
R(Z) ={(a,b)|a,b∈Zanda≤b}. R is a relation on the set of integers under which aRb holds for two numbersa,b∈Zif and only ifa≤b.
Let S be a set R(P(S)) ={(A,B)|A,B ∈ P(S) andA⊆B}. Relational databases: practical examples of relations.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 10
What are relations?
Relation are used to talk about elements of a set.
A relation R from setAto set B,R(A,B) is a subset ofA×B.
IfA=B for some relation, we denote the relation as R(A).
Examples:
A function is a special case of a relation.
R(Z) ={(a,b)|a,b∈Zanda≤b}. R is a relation on the set of integers under which aRb holds for two numbersa,b∈Zif and only ifa≤b.
We useaRb to denote ais related to b.
Let S be a set R(P(S)) ={(A,B)|A,B ∈ P(S) andA⊆B}. Relational databases: practical examples of relations.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 10
What are relations?
Relation are used to talk about elements of a set.
A relation R from setAto set B,R(A,B) is a subset ofA×B.
IfA=B for some relation, we denote the relation as R(A).
Examples:
A function is a special case of a relation.
R(Z) ={(a,b)|a,b∈Zanda≤b}. R is a relation on the set of integers under which aRb holds for two numbersa,b∈Zif and only ifa≤b.
Let S be a set R(P(S)) ={(A,B)|A,B ∈ P(S) andA⊆B}.
Relational databases: practical examples of relations.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 10
What are relations?
Relation are used to talk about elements of a set.
A relation R from setAto set B,R(A,B) is a subset ofA×B.
IfA=B for some relation, we denote the relation as R(A).
Examples:
A function is a special case of a relation.
R(Z) ={(a,b)|a,b∈Zanda≤b}. R is a relation on the set of integers under which aRb holds for two numbersa,b∈Zif and only ifa≤b.
Let S be a set R(P(S)) ={(A,B)|A,B ∈ P(S) andA⊆B}.
Relational databases: practical examples of relations.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 5 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive:
R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa. Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa. Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
I IsR(Z) ={(a,b)|a,b∈Zanda≤b} reflexive?
I IsR(Z) ={(a,b)|a,b∈Zanda<b} reflexive?
I IsR(P(S)) ={(A,B)|A,B∈ P(S),A⊆B} ?
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa. Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric:
R(A) is called symmetric if∀a,b ∈A aRb implies bRa. Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
I IsR(Z) ={(a,b)|a,b∈Zanda≤b} symmetric?
I IsR(YourClass) ={(a,b)|a,b∈YourClass anda friend ofb}
symmetric?
I IsR(P(S)) ={(A,B)|A∩B=∅}symmetric?
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive:
R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
I IsR(Z) ={(a,b)|a,b∈Zanda≤b} transitive?
I IsR(N) ={(a,b)|a(mod b)6= 0}transitive?
I IsR(P(S)) ={(A,B)|A⊆B} transitive?
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric:
R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
I IsR(Z) ={(a,b)|a,b∈Zanda≤b} anti-symmetric?
I IsR(Z) ={(a,b)|a,b∈Zanda|b} anti-symmetric?
I IsR(P(S)) ={(A,B)|A⊆B} anti-symmetric?
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Properties of relations
Here we list a few definitions which define different types of relations.
Let Abe a set and let R(A) be a relation onA.
Reflexive: R(A) is called reflexive if aRa ∀a∈A.
Symmetric: R(A) is called symmetric if∀a,b ∈A aRb implies bRa.
Transitive: R(A) is called transitive if∀a,b,c ∈A aRb andbRc impliesaRc.
Anti-symmetric: R(A) is called anti-symmetric if∀a,b∈A aRb and bRa impliesa=b.
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 6 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)} R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx = suff(y)} R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)} R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx = suff(y)} R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)} R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx = suff(y)} R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)} R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx = suff(y)} R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)} R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx = suff(y)} R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)}
R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx = suff(y)} R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)}
R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx= suff(y)}
R(N) ={(a,b)|a (mod b)6= 0} R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)}
R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx= suff(y)}
Σ is a finite alphabet. Σ∗ are strings of arbitrary length over Σ
R(N) ={(a,b)|a (mod b)6= 0} R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)}
R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx= suff(y)}
R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)}
R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx= suff(y)}
R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b ∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Types of relations
We will study the following two types of relations:
Equivalence relations Partial orders
reflexive transitive symmetric anti-symmetric
equivalence X X X
relation
partial order X X X
Classify the following:
R(Z) ={(a,b)|a,b∈Zanda≤b}
R(Z) ={(a,b)|a,b∈Zanda≡b (mod n)}
R(Σ∗) ={(x,y)|x,y ∈Σ∗ andx= suff(y)}
R(N) ={(a,b)|a (mod b)6= 0}
R(R) ={(a,b)|a,b ∈Z anda2 ≤b2}
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 7 / 10
Posets, Chains and Anti-chians
Definition
A set S along with a relation , (S,), is called a poset if defines a partial order on S.
Definition
If (S,) is a poset and every pair of elements in S is comparable, then (S,) is called a totally ordered set. A totally ordered set is called achain.
Definition
Let (S,) be a poset. A subsetA⊆S is called an anti-chain if no two elements of Aare related to reach other under .
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 8 / 10
Posets, Chains and Anti-chians
Definition
A set S along with a relation , (S,), is called a poset if defines a partial order on S.
Definition
If (S,) is a poset and every pair of elements in S is comparable, then (S,) is called a totally ordered set.
A totally ordered set is called achain.
Definition
Let (S,) be a poset. A subsetA⊆S is called an anti-chain if no two elements of Aare related to reach other under .
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 8 / 10
Posets, Chains and Anti-chians
Definition
A set S along with a relation , (S,), is called a poset if defines a partial order on S.
Definition
If (S,) is a poset and every pair of elements in S is comparable, then (S,) is called a totally ordered set. A totally ordered set is called achain.
Definition
Let (S,) be a poset. A subsetA⊆S is called an anti-chain if no two elements of Aare related to reach other under .
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 8 / 10
Posets, Chains and Anti-chians
Definition
A set S along with a relation , (S,), is called a poset if defines a partial order on S.
Definition
If (S,) is a poset and every pair of elements in S is comparable, then (S,) is called a totally ordered set. A totally ordered set is called achain.
Definition
Let (S,) be a poset. A subsetA⊆S is called an anti-chain if no two elements of Aare related to reach other under .
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 8 / 10
Representing partial orders as directed graphs
What is a graph?
Definition
A graph can be described by two sets: set V is called a set of vertices and set E is a subset of V ×V and is called a set of edges,G = (V,E). Vertices u,v ∈V are said to be neighbours if (u,v)∈E.
The graph is called directed ifE is a set of ordered pairs. What are the examples of graphs you may have seen:
Social network graphs Tum-tum route graphs ...
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 10
Representing partial orders as directed graphs
What is a graph?
Definition
A graph can be described by two sets: set V is called a set of vertices and set E is a subset of V ×V and is called a set of edges,G = (V,E).
Vertices u,v ∈V are said to be neighbours if (u,v)∈E. The graph is called directed ifE is a set of ordered pairs. What are the examples of graphs you may have seen:
Social network graphs Tum-tum route graphs ...
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 10
Representing partial orders as directed graphs
What is a graph?
Definition
A graph can be described by two sets: set V is called a set of vertices and set E is a subset of V ×V and is called a set of edges,G = (V,E).
Vertices u,v ∈V are said to be neighbours if (u,v)∈E.
The graph is called directed ifE is a set of ordered pairs. What are the examples of graphs you may have seen:
Social network graphs Tum-tum route graphs ...
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 10
Representing partial orders as directed graphs
What is a graph?
Definition
A graph can be described by two sets: set V is called a set of vertices and set E is a subset of V ×V and is called a set of edges,G = (V,E).
Vertices u,v ∈V are said to be neighbours if (u,v)∈E. The graph is called directed ifE is a set of ordered pairs.
What are the examples of graphs you may have seen:
Social network graphs Tum-tum route graphs ...
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 10
Representing partial orders as directed graphs
What is a graph?
Definition
A graph can be described by two sets: set V is called a set of vertices and set E is a subset of V ×V and is called a set of edges,G = (V,E).
Vertices u,v ∈V are said to be neighbours if (u,v)∈E. The graph is called directed ifE is a set of ordered pairs.
What are the examples of graphs you may have seen:
Social network graphs Tum-tum route graphs ...
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 9 / 10
Representing partial orders as directed graphs
Let S ={1,2,3}. Recall the poset (P(S),⊆).
[CW] Describe (P(S),⊆). A graph representing the poset:
∅
{1} {2} {3}
{1,2} {1,3} {2,3} {1,2,3}
[CW] What are the chains in this poset? [CW] What are the anti-chains in this poset?
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 10
Representing partial orders as directed graphs
Let S ={1,2,3}. Recall the poset (P(S),⊆).
[CW] Describe (P(S),⊆).
A graph representing the poset:
∅
{1} {2} {3}
{1,2} {1,3} {2,3} {1,2,3}
[CW] What are the chains in this poset? [CW] What are the anti-chains in this poset?
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 10
Representing partial orders as directed graphs
Let S ={1,2,3}. Recall the poset (P(S),⊆).
[CW] Describe (P(S),⊆).
A graph representing the poset:
∅
{1} {2} {3}
{1,2} {1,3} {2,3}
{1,2,3}
[CW] What are the chains in this poset? [CW] What are the anti-chains in this poset?
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 10
Representing partial orders as directed graphs
Let S ={1,2,3}. Recall the poset (P(S),⊆).
[CW] Describe (P(S),⊆).
A graph representing the poset:
∅
{1} {2} {3}
{1,2} {1,3} {2,3}
{1,2,3}
[CW] What are the chains in this poset?
[CW] What are the anti-chains in this poset?
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 10
Representing partial orders as directed graphs
Let S ={1,2,3}. Recall the poset (P(S),⊆).
[CW] Describe (P(S),⊆).
A graph representing the poset:
∅
{1} {2} {3}
{1,2} {1,3} {2,3}
{1,2,3}
[CW] What are the chains in this poset?
[CW] What are the anti-chains in this poset?
Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 10 / 10
