Discrete Structures ~ Quiz Mcqs

Introduction to Sets

• A set is a collection of well-defined and distinct objects, typically represented using curly brackets { }.
• For example, a set of vowels is: A = {a, e, i, o, u}.

Types of Sets

• Empty Set (Null Set): A set containing no elements.
  • Denoted by ∅ or { }.
  • Example: The set of odd numbers divisible by 2 is ∅.
• Finite Set: A set with a countable number of elements.
  • Example: {1, 2, 3, 4}.
• Infinite Set: A set with an uncountable number of elements.
  • Example: The set of natural numbers {1, 2, 3, 4,...}.
• Equal Sets: Two sets are equal if they contain the exact same elements.
  • Example: A = {1, 2, 3} and B = {3, 2, 1} are equal, thus A = B.
• Equivalent Sets: Two sets are equivalent if they have the same number of elements.
  • Example: A = {a, b, c} and B = {x, y, z} are equivalent.

Subsets and Universal Sets

• Subset: Set B is a subset of set A (B ⊆ A) if all elements of B are also in A.
  • If A = {1, 2, 3, 4} and B = {1, 2}, then B ⊆ A.
• Proper Subset: A subset (B ⊂ A) is a subset not equal to the original set.
  • If A = {1, 2, 3, 4}, then B = {1, 2} is a proper subset of A.
• Universal Set (U): Includes all elements of other sets under consideration.
  • If A = {1, 2} and B = {2, 3}, then U = {1, 2, 3}.

Power Sets, Cartesian Products, and Cardinality

• Power Set: A set of all possible subsets, including the empty set and the set itself.
  • A set with n elements contains 2^ n subsets.
  • For A = {1, 2}, the power set P(A) = {∅, { }, {1}, {2}, {1, 2}}.
• Cartesian Product: The Cartesian product of two sets, A × B, is the set of all possible ordered pairs (a, b) where a comes from A and b comes from B.
  • If A = {1, 2} and B = {a, b}, then A × B = {(1, a), (1, b), (2, a), (2, b)}.
• Cardinality: Indicates the number of elements in a set.
  • For A = {9, 8, 7, 6}, the cardinality |A| = 4.
  • The empty set has a cardinality of 0: |{ }| = 0.

Union and Intersection of Sets

• Union of Two Sets: The union combines all the unique elements from both sets.
  • Formula: A ∪ B = {x | x ∈ A or x ∈ B}.
  • If A = {1,2,3,4} and B = {6,7}, then A ∪ B = {1,2,3,4,6,7}.
• Intersection of Two Sets: The intersection returns elements that exist in both sets.
  • Formula: A ∩ B = {x | x ∈ A and x ∈ B}.
  • If A = {1,2,3,6} and B = {6,7}, then A ∩ B = {6}.

Difference and Complement of Sets

• Difference of Two Sets: Denoted as A - B, it is the set of elements in A but not in B.
  • In other words, take all the elements of A and remove any elements that are also in B.
  • For A = {1, 2, 3, 4, 5, 6} and B = {4, 5, 6}, A - B = {1, 2, 3}.
• Complement of a Set: Denoted as X' or U - X, it contains all elements not in X but present in the universal set U.
  • It involves taking all elements of the universal set U and removing the elements that are in X.
  • For U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and X = {2, 4, 6, 8}, X' = U - X = {1, 3, 5, 7, 9, 10}.

Graph Basics

• A graph comprises nodes (vertices) and edges (connections).
• Nodes and vertices are effectively the same thing.
• Graphs are classifiable as either Undirected, where edges lack directional properties, or Directed, where edges possess a specific direction.

Graph Representation

• Graphs are represented via G = (V, E).
  • V = Set of vertices (nodes).
  • E = Set of edges (connections between nodes).
  • A -> B -> C represents a directed graph.
• The degree of a vertex corresponds to the number of edges connected to it.
  • Vertex C has a degree of 1 and B has a degree of 2 in the graph A -> B -> C.
• Path: A sequence of edges joins a sequence of vertices.
  • A -> B -> C signifies starting at A, moving to B, and finishing at C.

Cycles, Weighted Graphs, and Matrix Representation

• Cycle/Circuit: A path that begins and ends at the same node.
• Weighted Graph: A graph where the values of edges denote costs or distances.
  • For A -> B (2) -> C (3), moving from A to B incurs a cost of 2; from B to C is 3.
• Adjacency Matrix: Represents connections between nodes.
  • Each row & column corresponds to a node.
  • If there is direct connection, the value is "1".
  • If there is no direct connection, the value is "0".

Eulerian Graphs

• Eulerian Graph: Contains a path that visits every edge only once.
• Eulerian Circuit: Starts and ends at the same vertex; all vertices must have an even degree.
• Eulerian Path: Does not require ending at the starting vertex; exactly two vertices have an odd degree.
• A graph with even degrees at all vertices contains an Eulerian circuit.

Hamiltonian Graphs

• Hamiltonian Graph: Contains a Hamiltonian circuit, which visits every vertex just once and returns to the start.
• For a Hamiltonian cycle to exist, all vertices must feature in a cycle.

Dijkstra's Algorithm

• Dijkstra’s Algorithm is employed to determine the shortest path between nodes, working efficiently with non-negative edge weights.
• Applications can be found in Google Maps for network routing and pathfinding.
• ∞ means no direct connection initially.

Cartesian Product

• It involves forming a set with ordered pairs where the first element comes from the first set, and so on.
• Mathematically, it is represented as A × B = {(a, b) | a ∈ A, b ∈ B}, meaning every element in A is paired with every element in B.
• For the sets A = {1, 2} and B = {x, y}, the Cartesian product is A × B = {(1, x), (1, y), (2, x), (2, y)}.
• Key notes include considering order: "(1, x) ≠ (x, 1)"; If A or B is empty, then A × B is also empty (∅), and if the cardinality of A is n and that of B is m, cardinality of A × B = n × m.
• It can be represented graphically on a 2D coordinate plane using x and y-axis.

Relations

• A relation is a subset of a Cartesian Product, demonstrating how elements from one set relate to another.
• A relation R from A to B means R ⊆ A × B.
• If the count of elements in A is n and that of B is m, then the count of possible relations would be 2ⁿ.
• Matrix Representation: Rows represent elements from set A. Columns represent elements from set B. "1" means the relation exists, else "0".
• Consider sets A = {1, 2, 3}, B = {a, b}, and R = {(1, a), (3, b)}. A matrix could represent this:

 1   0
 0   0
 0   1

Properties of Relations

• Reflexive: For every element a in set A, the pair (a, a) is in the relation R.
• Symmetric: If (a, b) is in R, then (b, a) must also be in R.
• Transitive: If (a, b) and (b, c) are in R, then (a, c) is in R.

Graph Theory

• Graph theory is a branch of discrete mathematics that focuses on relationships in computer science, networking, biology, etc.
• Graph representations can be models for social networks, Google Maps, and computer networks.
• A graph consists of a set of vertices/nodes (V), and a set of edges (E).
• Vertex/Node: A point on the graph.
• Edge; Connects two vertices.
• Degree: the number of edges connected by it.
• Adjacent vertices: Two vertices connected by an edge.
• Path: A sequence of vertices connected by edges.
• Cycle: A path starts and ends at the same vertex.

Types of Graphs

• Undirected Graph: Edges have no direction; connection between A and B is mutual.
• Directed Graph (Digraph): Edges have direction.
• Weighted Graph: Edges have numbers indicating costs, distances, etc.
• Connected Graph: Path b vertex exists.
• Disconnected Graph: Lacks nodes or vertices, isolated.
• Complete graph: Vertices have to connect and every vertex will connect to one another.

Graph Models and Representations

• Social Network: People represented as nodes, friendships/follows represented as edges (either undirected or directed).
• Web Graph Model: Websites represented by vertices and have links for directed edges.
• Transportation Model: Cities represented as nodes and roads as the edges with distances or costs.
• Graphs can be stored as an adjacency matrix, which can be 2D (rows/columns represent vertices.) A value of "1" indicates an edge. For weighted graphs edges would have values (eg costs).

Graph Connectivity, Paths, and Special Graphs

• A graph is connected only if there is a distinct path to traverse to every vertex.
• Disconnected Graph: Where there's at least one node or path to other nodes.
• Strongly Connected: There is a path between every pair of vertices in both directions.
• Weakly Connected: A path between every node is ignored.
• A path is a graph is sequence of edges.
• Eulerian Graph which has an existence to every circuit.
  • Eulerian Path is a path to follow to visit every edge once but have no start and end point.
  • Eulerian Circuit (this means there is start and end with the same vertices).
• A Hamiltonian Path is a path to follow to visit every vertex, only once. Some edges, though, may repeat. It comes with start and end vertex.
  • A Hamiltonian circuit comes with a Hamiltonian Path, a start and end that also has the same vertex.
  • Finally a Graph that has a Hamiltonian circuit, called a Hamilton graph.