Quiz # 1 Short Answers Prep

Introduction to Sets

• A set comprises well-defined and distinct objects, typically represented using curly brackets {}.
• Example: The set of vowels, A = {a, e, i, o, u}.

Types of Sets

• Empty Set (Null Set): Contains no elements and is denoted by ∅ or {}.
  • The set of odd numbers divisible by 2 is an empty set: ∅.
• Finite Set: Has a countable number of elements.
  • Example: {1, 2, 3, 4}
• Infinite Set: Has 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}, then A and B are equivalent.
• Subset: Set B is a subset of A (B ⊆ A) if all elements of B are also in A.
  • Example: If A = {1, 2, 3, 4} and B = {1, 2}, then B ⊆ A.
• Proper Subset: A subset (B ⊂ A) that is not equal to the original set.
  • Example: If B = {1, 2} and A = {1, 2, 3, 4}, then B is a proper subset of A.
• Universal Set (U): Contains all relevant elements under consideration.
  • Example: If A = {1, 2} and B = {2, 3}, the universal set U = {1, 2, 3}.
• Power Set: Set of all possible subsets, including the empty set and the set itself
  • A set with n elements has 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, includes all possible ordered pairs (a, b) where a is from A and b is from B.
  • If A = {1, 2} and B = {a, b}, then A × B = {(1, a), (1, b), (2, a), (2, b)}.

Cardinality of a Set

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

Union of Two Sets

• The union of two sets A and B contains all 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 of sets A and B contains only the elements common to 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 of a Set

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

Complement of a Set

• The complement of a set X, written as X' or U - X, includes all elements not in X but present in the universal set U
  • Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and X = {2, 4, 6, 8}, the complement X' = U - X = {1, 3, 5, 7, 9, 10}
  • All elements of the universal set U are taken, and the elements that are in X are removed.

Graph Theory Basics

• Graphs consist of nodes (vertices) and edges (connections).
• Nodes and vertices refer to the same components in a graph.
• Graphs can be undirected where edges have no direction
• Graphs can be directed where edges have a specific direction (→).

Graph Representation

• Graphs are represented as G = (V, E).
  • V represents the set of vertices (nodes).
  • E represents the set of edges (connections between nodes).

Degree of a Vertex

• The degree of a vertex is the number of edges connected to it.
  • If graph A→B→C, the degree of C = 1 and the degree of B = 2.

Path in a Graph

• A path is a sequence of edges connecting a sequence of vertices
• In Graph A → B → C: Start at A, move to B, and then go to C.

Cycle/Circuit in a Graph

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

Weighted Graph

• In weighted graphs, edges have numerical values to represent costs or distances.
  • Graph A → B (2) → C (3) represents the cost from A to B is 2, and the cost from B to C is 3.

Adjacency Matrix Representation

• Graphs have adjacency matrices representing connections between nodes.
• Rows and columns in an adjacency matrix correspond to nodes
• A value of 1 indicates a direct connection.
• A value of 0 indicates no direct connection.
• Weighted graphs store edge weights instead.
• Undirected graphs create symmetric matrices.

Eulerian Graphs

• An Eulerian graph has a path that visits every edge exactly once.
• An Eulerian Circuit starts and ends at the same vertex, and all vertices must have an even degree.
• An Eulerian Path doesn't necessarily end at the starting vertex and has exactly two vertices with an odd degree.
• A graph with all vertices having even degrees contains an Eulerian circuit.

Hamiltonian Graphs

• A Hamiltonian graph contains a Hamiltonian circuit (a path visiting every vertex exactly once and returning to the start).
• A Hamiltonian cycle exists if all vertices connect in a cycle, covering each vertex once.
  • In the cycle a → b → c → d → a is a Hamiltonian cycle.

Dijkstra's Algorithm

• Dijkstra’s Algorithm determines the shortest path between nodes, efficient with non-negative edge weights
• Google Maps uses Dijkstra's Algorithm for network routing and pathfinding

Important Points for Dijkstra

• Include previous distances when calculating A to E.
• Choose the smallest distance next for processing.
• Infinity "∞" represents no direct connection initially between nodes.

Cartesian Product Details

• The Cartesian product is a set formed from two or more given sets.
• Contains all ordered pairs of elements, where the first element of the pair is from the first set and the second is from the second set, and so on.
• Mathematical definition: A × B = {(a,b) | a ∈ A, b ∈ B}, meaning every element in A is paired with every element in B.
  • Example: If A = {1, 2} and B = {x, y}, then A × B = {(1,x), (1,y), (2,x), (2,y)}.

Key Notes on Cartesian Products

• Order matters for ordered pairs: (1, x) ≠ (x, 1).
• If A or B is an empty set (∅), then A × B is also empty (∅).
• A × B is generally not equal to B × A.
• Given cardinality of A = n and cardinality of B = m, the cardinality of A × B equals n * m.

Graphical Representation of Cartesian Products

• They cab be represented on a 2D coordinate plane
  • Elements of set A are on the x-axis.
  • Elements of set B are on the y-axis.
  • Ordered pairs (a, b) are plotted as points.
  • Example: Where A = {1, 2, 3}, Where B = {a, b}, plotting points (1, a), (1, b), (2, a), (2, b), (3, a), (3, b)

Relations Overview

• A relation is a subset of a Cartesian Product.
• Expresses relations between elements from one set to another.
• A relation R from A to B is a subset of A × B, denoted R ⊆ A × B.

Cardinality and Possible Relations

• Cardinality of A × B can be found by multiplying the number of elements in sets A and B.
• total number of possible relations is 2^n.
• Given cardinality of A = n and cardinality of B = m, cardinality of A × B is n * m.

Example of Relations

A = {1, 2, 3}, and B = {a, b}

• The relation R could be R = {(1,a), (3,b)}.

Matrix Representation of Relations

• A relation can be represented using a matrix with rows representing elements from set A and columns representing elements from set B.
• A 1 in the matrix indicates that relations exist, while a 0 means doesn’t.
• Using R = {(1, a), (3, b)}, based on Sets A, B
• Creates matrix 1 0; 0 0; 0 1

Properties of Relations

• Reflexive: Every element a in set A has the pair (a,a) in the relation R.
• Symmetric: If (a,b) exists in R, then (b,a) exists in R.
• Transitive: If (a,b) and (b,c) exist in R, then (a,c) exists in R.

Graph Theory Introduction

• Graph Theory analyzes relationships between objects and is used in computer science, networking, and other fields.

Reasons to Study Graph Theory

• Graph Theory helps model:
  • Real-world networking (Facebook, Instagram)
  • Routing problems (Google Maps)
  • Internet connections (Computer Networks)

Key Graph Terminologies

• Graph (G): Represents a set of vertices (V) and edges (E), written as G=(V,E).
• Vertex (Node) v: A point in the graph.
• Edge e: A connection between two vertices.
• Degree of a Vertex: The number of edges connected to it.
• Adjacent Vertices: Two 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, indicates connection instead.
  • Example: Social networks
• Directed Graph (Digraph): Edges have arrows showing direction.
  • Example: Twitter follow system.
• Weighted Graph: Edges have weights (numbers) representing costs, and distances.
  • Example: Google Maps routes.
• Connected Graph: Has a path to every other vertex.
• Example: Fully connected social network.
• Disconnected Graph: Vertices don't connect.
  • Example: Network with unconnected groups.
• Complete Graph: Every vertex is directly connected to every other vertex.
  • Example: A WhatsApp group where everyone messages everyone.

Graph Models Usage

• They illustrate real-world problems.
• Social Network Model: People are nodes, friendships are edges
• Web Graph Model: Websites are nodes, hyperlinks are directed edges
• Transportation Model: Cities are nodes, roads are weighted edges (distance/cost)

Representation of Graphs

• Adjacency Matrix: Stores graphs
  • 2D table or matrix relates vertices using rows and columns.
  • 1 means an edge exists, whereas a 0 means no edge.
  • Weighted graphs use numbers to represent matrix weights.

Social Network Model

• Each person is a vertex, and Friendships represent edges.
• Social Network Model can be undirected (Facebook friends) or directed (Twitter followers).

Web Graph Model

• Each website is a vertex, A hyperlink from one website to another represents a directed edge

Graph Connectivity Analysis

• Connected Graph: A graph where there is a path between every pair of vertices
  • Graphs that do not have paths between vertices are disconnected.
• Connected Graph: Every node is reachable from every other node.
• Disconnected Graph: At least one node is isolated or has no path to other nodes.
• Strongly Connected Graph (for Directed Graphs): There is a path between every pair of vertices in both directions.
• Weakly Connected Graph (for Directed Graphs): There is a path between nodes if direction is ignored.

Paths in Graphs Characteristics

• A path is a sequence of edges that connect a sequence of vertices.

Eulerian Graph Overview

• Eularian graphs have eularian circuits
• An Eulerian Path visits every edge exactly once and may not necessarily start and end at the same vertex.
• An Eulerian Circuit is an Eulerian Path that starts and ends at the same vertex.

Hamiltonian Graphs Synopsis

• A Hamiltonian Path visits every vertex exactly once, and edges can be repeated.
• A Hamiltonian Circuit is a Hamiltonian Path that starts and ends at the same vertex.
• A graph containing a Hamiltonian circuit is called a Hamilton graph.

Set Elements

• Comprises distinct objects called elements
• Sets use curly braces{}.
• Order is irrelevant, and remove all repetition.

Empty and Null Sets

• Empty or Null sets are devoid of all elements
• Example: A = {}.

Finite Sets

• Composed of a definite/limited number of elements.
  • Example A = {1,2,3,4}

Infinite Sets

• Includes unrestricted, innumerable elements. -Example A = {set of all whole numbers}.

Equal Sets Makeup

Equal sets containing the exact same members.

• Example: If A = {1,2,5} and B = {2,5,1}, then Set A = Set B.

Subsets and their Traits

• A set, ‘A,’ qualifies as a subset of B if each element in A also exists in B.
  • if A= {1,2}, if B= {1,2,3,4}, then A ⊆ B (is a subset of B)

Universal Set Overview

• Universal sets consists all elements from sets being scrutinized
  • Given A = {1,2} and B = {2,3}, the U = {1, 2,3}.

Cardinality Defined.

• Denotes the tally of elements within a set.
  • When A = {1, 2, 3, 4}, then the Cardinality: |A| = 4 Empty sets register zero:
• Cardinality |Ø| = 0.
• Countless for infinite sets (for example: natural numbers)

Power Set Description

• Power sets comprise a set including the entire subsets.
• There are 2 to the nth power subsets, from sets with an n number element
  • Using A = {1,2}; then P(A) = { {}, {1}, {2}, {1,2} }
• An example when (A= 2), power sets have 2 to to the power subsets; so 2 squared = 4 subsets.

Union Operations with Sets

• Given separate sets A and B, the combined Union operation of A and B yields a consolidated assembly.
  • Denoted with symbol; A ∪ B
  • Union equals {x: x ∈ A or x ∈ B}.

Set Intersections

• Given 2 sets, The intersection of A and B = elements both have in common
• Intersection denoted as A ∩ B
• Intersection A ∩ B = {x : x ∈ A and x ∈ B}

Differences between sets

• Subtract (or get the Difference b/w) A = {1,2,3,4,5,6,7} and B = {6,7} to get {1,2,3,4,5}".

Set Complements Explained. (U)

• Complements in sets X, are expressed as (U – X) or ‘X,’. Consisting components from set U. Which are set aside components element X
• When (U) = {1,2,3,4,5,6,7,8}, subtract (A ={1,2,5,6}), complement A yields {3,4,7,8}.