Lecture 126 of 400Week 4
Revisiting Representations of a Relation
Prof. Sudarshan Iyengar · IIT Ropar
Credits and licence
- From
- Discrete Mathematics, IIT Ropar (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
- Who can watch
- Teens profiles and older. How courses are placed
All the lectures
- Motivation for Counting
- Paper Folding Example
- Rubik's Cube Example
- Factorial Example
- Counting in Computer Science
- Motivation for Catalan numbers
- Rule of Sum and Rule of Product
- Problems on Rule of Sum and Rule of Product
- Factorial Explained
- Proof of n! - Part 1
- Proof of n! - Part 2
- Astronomical Numbers
- Permutations - Part 1
- Permutations - Part 2
- Permutations - Part 3
- Permutations - Part 4
- Problems on Permutations
- Combinations - Part 1
- Combinations - Part 2
- Combinations - Part 3
- Combinations - Part 4
- Problems on Combinations
- Difference between Permutations and Combinations
- Combinations with Repetition - Part 1
- Combinations with Repetition - Part 2
- Combination with Repetition - Problems
- Binomial Theorem
- Applications of Binomial Theorem
- Properties of Binomial Thoerem
- Multinomial Theorem
- Problems on Binomial and Multinomial Theorem
- Pascal's Triangle
- Fun facts on Pascal's Triangle
- Catalan Numbers - Part 1
- Catalan numbers - Part 2
- Catalan Numbers - Part 3
- Catalan Numbers - Part 4
- Examples of Catalan Numbers
- Chapter Summary
- Introduction to Set Theory
- Example, definiton and notation
- Sets - Problems Part 1
- Subsets - Part 1
- Subsets - Part 2
- Subsets - Part 3
- Union and intersections of sets
- Union and intersections of sets - Part 1
- Union and intersections of sets - Part 2
- Union and intersections of sets - Part 3
- Cardinality of Union of two sets - Part 1
- Cardinality of Union of sets - Part 2
- Cardinality of Union of three sets
- Power Set - Part 1
- Power set - Part 2
- Power set - Part 3
- Connection betwenn Binomial Theorem and Power Sets
- Power set - Problems
- Complement of a set
- De Morgan's Laws - Part 1
- De Morgan's Laws - Part 2
- A proof technique
- De Morgan's Laws - Part 3
- De Morgan's Laws - Part 4
- Set difference - Part 1
- Set difference - Part 2
- Symmetric difference
- History
- Summary
- Motivational example
- Introduction to Statements
- Examples and Non-examples of Statements
- Introduction to Negation
- Negation - Explanation
- Negation - Truthtable
- Examples for Negation
- Motivation for OR operator
- Introduction to OR operator
- Truthtable for OR operator
- OR operator for 3 Variables
- Truthtable for AND operator
- AND operator for 3 Variables
- Primitive and Compound statements - Part 1
- Primitive and Compound statements - Part 2
- Problems involoving NOT, OR and AND operators
- Introduction to implication
- Examples and Non-examples of Implication - Part 1
- Examples and Non-examples of Implication - Part 2
- Explanation of Implication
- Introduction to Double Implication
- Explanation of Double Implication
- Converse, Inverse and Contrapositive
- XOR operator - Part 1
- XOR operator - Part 2
- XOR operator - Part 3
- Problems
- Tautology, Contradiction - Part 1
- Tautology, Contradiction - Part 2
- Tautology, Contradiction - Part 3
- SAT Problem - Part 1
- SAT Problem - Part 2
- Logical Equivalence - Part 1
- Logical Equivalence - Part 2
- Logical Equivalence - Part 3
- Logical Equivalence - Part 4
- Motivation for laws of logic
- Double negation - Part 1
- Double negation - Part 2
- Laws of Logic
- De Morgan's Law - Part 1
- De Morgan's Law - Part 2
- Rules of Inferences - Part 1
- Rules of Inferences - Part 2
- Rules of Inferences - Part 3
- Rules of Inferences - Part 4
- Rules of Inferences - Part 5
- Rules of Inferences - Part 6
- Rules of Inferences - Part 7
- Conclusion
- Introduction to Relation
- Graphical Representation of a Relation
- Various sets
- Matrix Representation of a Relation
- Relation - An Example
- Cartesian Product
- Set Representation of a Relation
- Revisiting Representations of a Relation
- Examples of Relations
- Number of relations - Part 1
- Number of relations - Part 2
- Reflexive relation - Introduction
- Example of a Reflexive relation
- Reflexive relation - Matrix representation
- Number of Reflexive relations
- Symmetric Relation - Introduction
- Symmetric Relation - Matrix representation
- Symmetric Relation - Examples and non examples
- Parallel lines revisited
- Number of symmetric relations - Part 1
- Number of symmetric relations - Part 2
- Examples of Reflexive and Symmetric Relations
- Pattern
- Transitive relation - Examples and non examples
- Antisymmetric relation
- Examples of Transitive and Antisymmetric Relation
- Antisymmetric - Graphical representation
- Antisymmetric - Matrix representation
- Number of Antisymmetric relations
- Condition for relation to be reflexive
- Few notations
- Condition for relation to be reflexive
- Condition for relation to be reflexive
- Condition for relation to be symmetric
- Condition for relation to be symmetric
- Condition for relation to be antisymmetric
- Equivalence relation
- Equivalence relation - Example 4
- Partition - Part 1
- Partition - Part 2
- Partition - Part 3
- Partition - Part 4
- Partition - Part 5
- Partition - Part 5
- Motivational Example - 1
- Motivational Example - 2
- Commonality in examples
- Motivational Example - 3
- Example - 4 Explanation
- Introduction to functions
- Defintion of a function - Part 1
- Defintion of a function - Part 2
- Defintion of a function - Part 3
- Relations vs Functions - Part 1
- Relations vs Functions - Part 2
- Introduction to One-One Function
- One-One Function - Example 1
- One-One Function - Example 2
- One-One Function - Example 3
- Proving a Function is One-One
- Examples and Non- examples of One-One function
- Cardinality condition in One-One function - Part 1
- Cardinality condition in One-One function - Part 2
- Introduction to Onto Function - Part 1
- Introduction to Onto Function - Part 2
- Definition of Onto Function
- Examples of Onto Function
- Cardinality condition in Onto function - Part 1
- Cardinality condition in Onto function - Part 2
- Introduction to Bijection
- Examples of Bijection
- Cardinality condition in Bijection - Part 1
- Cardinality condition in Bijection - Part 2
- Counting number of functions
- Number of functions
- Number of One-One functions - Part 1
- Number of One-One functions - Part 2
- Number of One-One functions - Part 3
- Number of Onto functions
- Number of Bijections
- Counting number of functions
- Motivation for Composition of functions - Part 1
- Motivation for Composition of functions - Part 2
- Definition of Composition of functions
- Why study Composition of functions
- Example of Composition of functions - Part 1
- Example of Composition of functions - Part 2
- Motivation for Inverse functions
- Inverse functions
- Examples of Inverse functions
- Application of inverse functions - Part 1
- Three stories
- Three stories - Connecting the dots
- Mathematical induction - An illustration
- Mathematical Induction - Its essence
- Mathematical Induction - The formal way
- MI - Sum of odd numbers
- MI - Sum of powers of 2
- MI - Inequality 1
- MI - Inequality 1 (solution)
- MI - To prove divisibility
- MI - To prove divisibility (solution)
- MI - Problem on satisfying inequalities
- MI - Problem on satisfying inequalities (solutions)
- MI - Inequality 2
- MI - Inequality 2 solution
- Mathematical Induction - Example 9
- Mathematical Induction - Example 10 solution
- Binomial Coeffecients - Proof by induction
- Checker board and Triomioes - A puzzle
- Checker board and triominoes - Solution
- Mathematical induction - An important note
- Mathematical Induction - A false proof
- A false proof - Solution
- Motivation for Pegionhole Principle
- Group of n people
- Set of n integgers
- 10 points on an equilateral triangle
- Pegionhole Principle - A result
- Consecutive integers
- Consecutive integers solution
- Matching initials
- Matching initials - Solution
- Numbers adding to 9
- Numbers adding to 9 - Solution
- Deck of cards
- Deck of cards - Solution
- Number of errors
- Number of errors - Solution
- Puzzle - Challenge for you
- Friendship - an interesting property
- Connectedness through Connecting people
- Traversing the bridges
- Three utilities problem
- Coloring the India map
- Defintion of a Graph
- Degree and degree sequence
- Relation between number of edges and degrees
- Relation between number of edges and degrees - Proof
- Hand shaking lemma - Corollary
- Problems based on Hand shaking lemma
- Havel Hakimi theorem - Part 1
- Havel Hakimi theorem - Part 2
- Havel Hakimi theorem - Part 3
- Havel Hakimi theorem - Part 4
- Havel Hakimi theorem - Part 5
- Regular graph and irregular graph
- Walk
- Trail
- Path and closed path
- Definitions revisited
- Examples of walk, trail and path
- Cycle and circuit
- Example of cycle and circuit
- Relation between walk and path
- Relation between walk and path - An induction proof
- Subgraph
- Spanning and induced subgraph
- Spanning and induced subgraph - A result
- Introduction to Tree
- Connected and Disconnected graphs
- Property of a cycle
- Edge condition for connectivity
- Connecting connectedness and path
- Connecting connectedness and path - An illustration
- Cut vertex
- Cut edge
- Illustration of cut vertices and cut edges
- NetworkX - Need of the hour
- Introduction to Python - Installation
- Introduction to Python - Basics
- Introduction to NetworkX
- Story so far - Using NetworkX
- Directed, weighted and multi graphs
- Illustration of Directed, weighted and multi graphs
- Graph representations - Introduction
- Adjacency matrix representation
- Incidence matrix representation
- Isomorphism - Introduction
- Isomorphic graphs - An illustration
- Isomorphic graphs - A challenge
- Non - isomorphic graphs
- Isomorphism - A question
- Complement of a Graph - Introduction
- Complement of a Graph - Illiustration
- Self complement
- Complement of a disconnected graph is connected
- Complement of a disconnected graph is connected - Solution
- Which is more? Connected graphs or disconnected graphs?
- Bipartite graphs
- Bipartite graphs - A puzzle
- Bipartite graphs - Converse part of the puzzle
- Definition of Eulerian Graph
- Illustration of eulerian graph
- Non- example of Eulerian graph
- Litmus test for an Eulerian graph
- Why even degree?
- Proof for even degree implies graph is eulerian
- A condition for Eulerian trail
- Why the name Eulerian
- Can you traverse all location?
- Defintion of Hamiltonian graphs
- Examples of Hamiltonian graphs
- Hamiltonian graph - A result
- A result on connectedness
- A result on Path
- Dirac's Theorem
- Dirac's theorem - A note
- Ore's Theorem
- Dirac's Theorem v/s Ore's Theorem
- Eulerian and Hamiltonian Are they related
- Importance of Hamiltonian graphs in Computer science
- Constructing non intersecting roads
- Definition of a Planar graph
- Examples of Planar graphs
- V - E + R = 2
- Illustration of V - E + R =2
- V - E + R = 2; Use induction
- Proof of V - E + R = 2
- Famous non-planar graphs
- Litmus test for planarity
- Planar graphs - Inequality 1
- 3 Utilities problem - Revisited
- Complete graph on 5 vertices is non-planar - Proof
- Prisoners and cells
- Prisoners example and Proper coloring
- Chromatic number of a graph
- Examples on Proper coloring
- Recalling the India map problem
- Recalling the India map problem - Solution
- NetworkX - Digraphs
- NetworkX - Adjacency matrix
- NetworkX- Random graphs
- NetworkX - Subgarph
- NetworkX - Isomorphic graphs Part 1
- NetworkX - Isomorphic graphs Part 2
- NetworkX - Isomorphic graphs: A game to play
- NetworkX - Graph complement
- NetworkX - Eulerian graphs
- NetworkX - Bipaprtite graphs
- NetworkX - Coloring
- Counting in a creative way
- Example 1 - Fun with words
- Words and the polynomial
- Words and the polynomial - Explained
- Example 2 - Picking five balls
- Picking five balls - Solution
- Picking five balls - Another version
- Defintion of Generating function
- Generating function examples - Part 1
- Generating function examples - Part 2
- Generating function examples - Part 3
- Binomial expansion - A generating function
- Binomial expansion - Explained
- Picking 7 balls - The naive way
- Picking 7 balls - The creative way
- Generating functions - Problem 1
- Generating functions - Problem 2
- Generating functions - Problem 3
- Why Generating function?
- Introduction to Advanced Counting
- Example 1 : Dogs and Cats
- Inclusion-Exclusion Formula
- Proof of Inclusion - Exlusion formula
- Example 2 : Integer solutions of an equation
- Example 3 : Words not containing some strings
- Example 4 : Arranging 3 x's, 3 y's and 3 z's
- Example 5 : Non-multiples of 2 or 3
- Example 6 : Integers not divisible by 5, 7 or 11
- A tip in solving problems
- Example 7 : A dog nor a cat
- Example 8 : Brownies, Muffins and Cookies
- Example 10 : Integer solutions of an equation
- Example 11 : Seating Arrangement - Part 1
- Example 11 : Seating Arrangement - Part 2
- Example 12 : Integer solutions of an equation
- Number of Onto Functions
- Formula for Number of Onto Functions
- Example 13 : Onto Functions
- Example 14 : No one in their own house
- Derangements
- Derangements of 4 numbers