Quiz # 1 Fill In The Blanks Prep

Introduction to Sets

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

Types of Sets

• Empty Set (Null Set): Contains no elements and is denoted by ∅ or {}.
  • Example: The set of odd numbers divisible by 2 is ∅.
• Finite Set: Contains a countable number of elements.
  • Example: {1, 2, 3, 4}
• Infinite Set: Contains 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 same elements.
  • Example: If A = {1, 2, 3} and B = {3, 2, 1}, then A = B.
• Equivalent Sets: Two sets are equivalent if they have the same number of elements.
  • Example: If A = {a, b, c} and B = {x, y, z}.

Subset and Proper Subset

• A set B is a subset of A (B ⊆ A) if all elements of B exist in A.
  • Example: If A = {1, 2, 3, 4} and B = {1, 2}, then B ⊆ A.
• A proper subset (B ⊂ A) is a subset that isn't equivalent to the original set
  • Example: B = {1, 2} is a proper subset of A = {1, 2, 3, 4}.

Universal Set (U)

• Consists of all elements of other sets within the current discussion.
  • Example: Given A={1,2} and B={2,3}, the universal set U = {1, 2,3}.

Power Set

• A set of all possible subsets, including the empty set and the set itself.
• Formula: If a set has n elements, its power set contains 2ⁿ subsets.
  • Example: For A = {1, 2}, the power set P(A) = {∅, {1}, {2}, {1, 2}}.

Cartesian Product

• The Cartesian product of two sets, A × B, includes all possible ordered pairs (a, b) where a is from A and b is from B.
  • Example: If A = {1, 2} and B = {a, b}, then A × B = {(1, a), (1, b), (2, a), (2, b)}.

Cardinality of a Set

• Refers to the number of elements in a set.
  • Example: If A = {9, 8, 7, 6}, then |A| = 4.
• The empty set (∅) has a cardinality of 0: |{ }| = 0.

Union of Two Sets

• Includes all unique elements from both sets.
• The formula for the union of two sets A and B is: A ∪ B = {x ∣ x ∈ A or x ∈ B}.
  • Example: If A = {1,2,3,4} and B = {6,7}, then A∪B={1,2,3,4,6,7}.

Intersection of Two Sets

• Includes only the common elements.
• The formula for the intersection of two sets A and B is: A ∩ B= {x ∣ x ∈ A and x ∈ B}.
  • Example: If A = {1,2,3,6} and B = {6,7}, then 𝐴∩𝐵={6}.

Difference of a Set

• Given two sets A and B, written as A - B, is the set of elements that are in A but not in B.
  • Example: if A = {1, 2, 3, 4, 5, 6}, B = {4, 5, 6} then A - B = {1, 2, 3}
• All elements of A are taken and any that are also in B are removed.

Complement of a Set

• Given a set X, written as X' or U - X, is the set of all elements not in X but present in the universal set (U).
  • Example: If U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and X = {2, 4, 6, 8}, then X' = U - X = {1, 3, 5, 7, 9, 10}.
• Take all elements of the universal set U and remove the elements that are in X.

Graph Basics

• A graph consists of nodes (vertices) and edges (connections between them).
• Nodes and vertices are equivalent.
• Graphs can be undirected or directed.
  • Undirected graphs have edges with no direction.
  • Directed graphs have edges that have a specific direction (→).

Graph Representation

• A graph is represented as G = (V, E).
• V = Set of vertices (nodes).
• E = Set of edges (connections between nodes).
• Example graph: A→B→C, is a directed graph.

Degree of a Vertex

• The degree of a vertex is the number of edges connected to that vertex.
• For the directed graph A→B→C:
  • Degree of C = 1
  • Degree of B = 2

Path in a Graph

• A path is a sequence of edges that connects a sequence of vertices.
  • Example: A → B → C, start at A, move to B, and then go to C.

Cycle/Circuit in a Graph

• A cycle (circuit) is a path that starts and ends at the same node.
  • A cycle returns to A after visiting B and C.

Weighted Graph

• Edges have numerical values that represent costs or distances (weights).
  • Example: A → B (2) →B → C (3), the cost from A to B is 2, and from B to C is 3.

Adjacency Matrix Representation

• Represents connections between nodes.
• Each row and column correspond to a node, and a value of 1 indicates a direct connection, while 0 indicates no direct connection.
• Weighted graphs use edge weight values instead of 1 in the adjacency matrix.
• If a graph is undirected, the matrix is symmetric.

Eulerian Graphs

• An Eulerian graph has a path that visits every edge exactly once.
• Conditions for an Eulerian Graph:
  • Eulerian Circuit: Starts and ends at the same vertex, all vertices must have an even degree.
  • Eulerian Path: Does not necessarily end at the starting vertex, exactly two vertices have an odd degree.
• Example: A → B→C ↑ ↓ ↓ D←E←F contains an Eulerian circuit if all vertices have even degrees.

Hamiltonian Graphs

• A Hamiltonian graph contains a Hamiltonian circuit, which is a path that visits every vertex exactly once and returns to the starting vertex.
• Conditions for a Hamiltonian Graph:
  • A Hamiltonian cycle exists if all vertices are connected in a cycle, covering each vertex exactly once.
• Example: The cycle a → b → c → d → a is a Hamiltonian cycle.

Dijkstra's Algorithm

• Used to find the shortest path between nodes in a graph, efficiently handling non-negative edge weights.
• Commonly used in network routing and pathfinding problems like those in Google Maps.
  • When calculating distances (e.g., A to E), previous distances must be included.
  • The smallest distance should be chosen next for processing.
  • "∞" signifies no direct connection, such as A to E and F initially.

Cartesian Product

• A set formed from two or more given sets that contains all ordered pairs of elements.
• The first element of each pair comes from the first set, the second from the second set, and so on.
• Mathematical Definition: A×B={(a,b)∣a∈A,b∈B}, meaning for every element in A, it is paired with every element in B.
  • Example: If A = {1, 2} and B = {x, y}, the Cartesian product A×B={(1,x),(1,y),(2,x),(2,y)}.
• Important Notes:
  • Order matters: (1, x) ≠ (x, 1).
  • If either A or B is empty, then A×B is also empty (∅).
  • A×B is not equal to B×A.
  • If the cardinality of A is n and the cardinality of B is m, the cardinality of A × B is n×m.

Graphical Representation of Cartesian Product

• Can be represented on a 2D coordinate plane by placing elements of A on the x-axis and elements of B on the y-axis, then plotting ordered pairs (a, b) as points.
  • Example: For A = {1, 2, 3} and B = {a, b}, the points plotted would be (1, a), (1, b), (2, a), (2, b), (3, a), (3, b).

Relations

• A relation is a subset of a Cartesian Product, showing how elements from one set are related to elements from another set.
• A relation R from A to B is a subset of A×B, meaning R⊆A×B.
• Then the total number of possible relations will be 2ⁿ, where n equals the cardinality AxB found by multiplying the number of elements in the sets.
• Example: For sets A = {1, 2, 3} and B = {a, b}, the relation R could be R={(1,a),(3,b)}.

Matrix Representation of a Relation

• Used to represent relations where:

  • Rows represent elements from set A.
  • Columns represent elements from set B.
  • A 1 in the matrix means the relation exists, and a 0 means it doesn’t.
  • Example: Given A = {1, 2, 3}, B = {a, b}, and R = {(1, a), (3, b)}, the matrix is:

  	a	b
  1	1	0
  2	0	0
  3	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 both (a, b) and (b, c) are in R, then (a, c) is in R.

Graph Theory

• A branch of discrete mathematics used to study relationships between objects.
• Used in computer science, networking, biology, transportation, and social networks.
• Common applications include:
  • Social Networks: Modeling connections on platforms like Facebook and Instagram as graphs.
  • Google Maps and GPS: Representing routes and locations as graphs.
  • Computer Networks: Modeling devices connected through the internet.

Graph Terminologies

• Graph G consists of:
  • Set of vertices (nodes) -> Represent as V
  • Set of edges(connections between nodes) -> Represent as E
  • G = (V, E)
• Basic terms:
  • Vertex (node) v: A point in the graph
  • Edge e: A connection between two vertices
  • Degree of a vertext: Number of edges connected to it
  • Adjacent vertices: Tow vertices connected by an edge
  • Path: A sequence of vertices connected by edges
  • Cycle: A path that starts and ends at the same vertex

Types of Graphs

• Undirected Graph: Edges have no direction (A, B) means A is connected to B, social network connections
• Directed Graph (Digraph): Edges have arrows showing direction (A -> B) means A follows B but not vice versa, for example a Twitter follow system
• Weighted Graph: Edges have weight(numbers) representing cost, distances and so on for example google maps
• Connected Graph: Every vertex has a path to every other vertex, a fully connected social network.
• Disconnected Graph: Some vertices are isolated, a network with unconnected groups.
• Complete Graph: Every vertex is connected to every other vertex, in a whatsapp group every message everyone.

Graph Models

• Graph models are used to represent real-world problems using graphs.
  • Social Network Model has people as nodes, friendships as edges
  • Web Graph Model has websites as nodes, hyperlinks as directed edges
  • Transportation Model has cities as nodes, roads as weighted edges(distance/cost)

Graph Representations

• Graphs can be stored as an Adjacency Matrix:
  • 2D table (matrix) where rows and columns represent vertices
  • If an edge exists between Vertices use 1 in the marix if not use 0
  • For weighted graphs, numbers in the matrix represent the weights

Graph Connectivity

• If there's a path between every pair of vertices, a graph is considered connected. Otherwise, it's disconnected.
• Types of graph connectivity:
  • Connected Graph: Each node can be reached from every other node.
  • Disconnected Graph: At least one node is isolated or has no way to connect to other nodes.
  • Strongly Connected Graph: In directed graphs, there's a two-way path between each pair of vertices.
  • Weakly Connected Graph: Occurs in directed graphs when there is a path between nodes if directionality is ignored.

Paths in Graphs

• In a graph, a path consists of a series of edges that link a sequence of vertices.

Eulerian Graph

• A graph with a eularian circuit.
  • What is an Eulerian Path? Is a path that visits every edge exactly once. It may or may not start and end at the same vertex.
  • What is an Eulerian Circuit? Is an Eulerian Path that starts and ends at the same vertex.

Hamiltonian Graph

• What is a Hamiltonian Path? Is a path that visits every vertex exactly once(edges may repeat).
• What is a Hamiltonian Circuit? Is a Hamiltonian Path that starts the ends at the same vertex
• A Graph that has Hamiltonian circuit is called a Hamilton graph.

What is a Set

• a collection of distinct objects (called elements).
  • Notation:
  • A set is written as: A = {1, 2, 3, 4, 5}
  • Elements are written inside curly braces {}
  • Order doesn’t matter, and repetition is not allowed.

Types of Sets

- Empty Set or Null set: It has no element present in it.Example: A = {} is a null set.

• Finite Set: It has a limited number of elements.Example: A = {1,2,3,4}
• Infinite Set: It has an infinite number of elements.Example: A = {set of all whole numbers}
• Equal Set: Two sets which have the same members.Example: A = {1,2,5} and B={2,5,1}: Set A = Set B
• Subsets: A set ‘A’ is said to be a subset of B if each element of A is also an element of B.Example: A={1,2}, B={1,2,3,4}, then A ⊆ B
• Universal Set: A set which consists of all other under discussion.Example: A={1,2}, B+{2,3}, The universal set here will be, U = {1,2,3}

Subsets

• A subset is a set where all elements exist in another set
• Example; If A = {1, 2, 3} and B = {1, 2}, then B is a subset of A, written as B ⊆ A. -Proper Subset: A subset that is not equal to the original set. B ⊂ A means B is a proper subset of A.
• Every set is a subset of itself, and then empty set is a subset of all sets

Cardinality

• Refers to the number of elements in a set
• Example: If A = {1, 2, 3, 4}, then |A| = 4.
• Empty set cardinality: |Ø| = 0.
• Infinite set: Cannot be counted (like the set of natural numbers)

Power Set

• The Power Set of a set is the set of all its subsets, including the empty set and itself Formula: If a set has n elements, its power set has 2^n sbuset Example: If A = {1, 2 }, then P(A) = { {},{1}, {2}, {1, 2}}
• Because |A| = 2, the power set has 2^2 = 4 subsets

Set of Operations

• Union of Sets
  • If two sets A and B are given, then the Union of A and B is qual to the set that contains all the elements present in set A and set B this operation can be represented as
    • A U B = {X: X E A or X E B}
  • Where x is the elements present in both sets A and B
• Intersection of set -If two sets A and B are given, then theintersection of A and B is the subset of universal set U which consists of element common to both A and B it is denotated by the symbol *n" this operation is represented by;
• A n B = {x : x E A and x E B}
• Where x is the common element of both sets A and B -Difference of Sets
  • If there are two sets A and B, then the difference of two sets and B is equal to the set which consist of elements present in A but not in B. It is represetned by A-B Example: If A = {1,2,3,4,5,6,7}and B{6,7} are two sets
  • and the difference of set AAand set BB is given by:
  • AA - BB ={1,2,3,4,5}
  • We can also say, that the difference of set and set B is qual to the intersection of set AAwith set B, Hence,
• Compliment of Set
• The compliment if set xx if denoted by xx ' such that it contains all the elemenets of the universal set apart from those present on A - X’ = {a : a ∈ U and a ∉ A} ( a e U and a ! E A)