SOME QUESTIONS IN FINALS

• Relation


  A set of ordered pairs
• Symmetric relation


  A relation where a is related to b implies b is related to a
• Antisymmetric relation


  A relation where a is related to b implies b is not related to a unless a = b
• Relation "has the same birthday as" on the set of all people

  • Reflexive, symmetric
• "Less than or equal to" relation on the set of all integers


  • Reflexive, antisymmetric, transitive
• Inclusion-exclusion principle


  Helps to calculate the size of the union of two overlapping sets
• Sum rule


  Used to find the total number of ways to perform one task if it can be broken down into several independent tasks
• 5 ways to choose a pen and 3 ways to choose a notebook

  • 15 ways to choose a pen and a notebook
• Graph


  A data structure consisting of nodes and edges
• Vertex


  A node in a graph
• Edge


  A line connecting two vertices
• Undirected graph


  A graph with edges that do not have any direction
• Degree of a vertex in an undirected graph

  The number of edges connected to the vertex
• Complete graph


  A graph where each vertex is connected to every other vertex
• Complete graph with 4 vertices


  • Has 6 edges
• Bipartite graph


  Its vertices can be divided into two sets such that no two vertices within the same set are adjacent