Please enable JavaScript.
Coggle requires JavaScript to display documents.
DM (Graph Theory, Discrete Mathematics, Sequences And Summations) - Coggle…
DM
Graph Theory
Graph
A graph G = (V, E) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges
Each edge has either one or two vertices associated with it, called its endpoints
An edge is said to connect its endpoints
Types
Infinite Graph
A graph with an infinite vertex set or an infinite number of edges is called an infinite graph
Finite Graph
A graph with a finite vertex set and a finite edge set is called a finite graph
Simple Graph
A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices is called a simple graph
Multigraph
Graphs that may have multiple edges connecting the same vertices
Multiplicity of edge
Pseudo Graph
Graphs with loops and multiple edges between same set of vertices.
Regular Graph
A graph where the degree of each vertex is same
K-Regular
If the degree of each vertex is K
All complete graphs are regular but not all regular graphs are complete
Number of edges
Number of edges of a K Regular graph with N vertices = (N*K)/2
For a K Regular graph, if K is odd, then the number of vertices of the graph must be even
2 Regular graphs consists of Disjoint union of cycles and Infinite Chains
A K-dimensional Hyper cube (Qk) is a K Regular graph
Directed Graph
A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E
Each directed edge is associated with an ordered pair of vertices
The directed edge associated with the ordered pair (u, v) is said to start at u and end at v
Types
Simple Directed Graph
Directed Multigraphs
Mixed
Both directed and undirected edges
Underlying Undirected Graph
The undirected graph that results from ignoring directions of edges is called the underlying undirected graph
Complete Graphs
A complete graph on n vertices, denoted by
Kn
, is a simple graph that contains exactly one edge between each pair of distinct vertices
Number of Cycles in a Complete Graph
Undirected and Labelled
vCc * (c-1)!/2
Undirected and Unlabelled
1
Directed and labelled
vCc * (c-1)!
Directed and unlabelled
(c-1)!
Non-Complete Graph
A simple graph for which there is at least one pair of distinct vertex not connected by an edge is called noncomplete
Bipartite Graph
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V
When this condition holds, we call the pair (V1 , V2 ) a bipartition of the vertex set V of G
Theorem
A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color
Complete Bipartite
Graphs
A complete bipartite graph Km,n is a graph that has its vertex
set partitioned into two subsets of m and n vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second
subset. Each vertex in set 1 is connected to every other vertex in set 2.
Every Tree is bipartite
Cycle Graphs with an even number of vertices are bipartite
A graph is bipartite if and only it does not contain an odd cycle
Every planar graph whose faces all have even length is bipartite
A graph is bipartite if and only it is 2 colorable
The spectrum of a graph is symmetric if and only if its a bipartite graph
Terminology
Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G
Such an edge e is called incident with the vertices u
and v and e is said to connect u and v
The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is called the
neighborhood
of v
If A is a subset of V, we denote ⋃ by N(A) the set of all vertices in G that are adjacent to at least one vertex in A
The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex.
The degree of the vertex v is denoted by deg(v).
Isolated Vertex
A vertex of degree zero is called isolated
Pendant Vertex
A vertex is pendant if and only if it has degree one
When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u
The vertex u is called the initial vertex of (u, v), and v is called
the terminal or end vertex of (u, v)
The initial vertex and terminal vertex of a loop are the same
In a graph with directed edges the in-degree of a vertex v, denoted by deg− (v), is the number of edges with v as their terminal vertex
The out-degree of v, denoted by deg+ (v), is the
number of edges with v as their initial vertex
Cycles
A cycle
Cn
, n ≥ 3, consists of n vertices v1 , v2 , ... , vn and edges {v1, v2 }, {v2 , v3 }, ... , {vn−1 , vn}, and {vn, v1 }
Wheel
We obtain a wheel Wn when we add an additional vertex to a cycle Cn , for n ≥ 3, and connect this new vertex to each of the n vertices in Cn, by new edges
n-Cube
An n-dimensional hypercube, or n-cube, denoted by Qn , is a graph that has vertices representing the 2n bit strings of length n
Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position
The number of vertices in a graph is it order
Theorems
The Handshaking Theorem
Let G = (V, E) be an undirected graph with m edges
2m = Sum(deg(v))
An undirected graph has an even number of vertices of odd degree
Sum(deg−(v)) = Sum(deg+ (v)) = |E|
Matching(Same as Edge Independent Set)
A matching M in a simple graph G = (V, E) is a subset of the set E of edges of the graph such that no two edges are incident with the same vertex
A vertex that is the endpoint of an edge of a matching M is said to be matched in M otherwise it is said to be unmatched
Maximum Matching
A maximum matching is a matching with the largest number of edges
Complete/Perfect Matching
We say that a matching M in a bipartite graph G = (V, E)
with bipartition (V1 , V2 ) is a complete matching from V1 to V2 if every vertex in V1 is the endpoint of an edge in the matching, or equivalently, if |M| = |V1|
Necessary and Sufficient Condition
The bipartite graph G = (V, E) with bipartition
(V1 , V2 ) has a complete matching from V1 to V2 if and only if |N(A)| ≥ |A| for all subsets A of V1.
Number of perfect matching on complete graph
If n is odd
0
If n is even
n!/((2^(n/2))*((n/2)!))
Maximal Matching
A matching M of graph ‘G’ is said to maximal if no other edges of ‘G’ can be added to M
Matched/Unmatched
if deg(V) = 1, then (V) is said to be matched
if deg(V) = 0, then (V) is not matched
Independent edge
New Graphs from Old
Subgraph
A subgraph of a graph G = (V, E) is a graph H = (W, F), where W ⊆ V and F ⊆ E. A sub-graph H of G is a proper subgraph of G if H ≠ G
Induced Subgraph
Let G = (V, E) be a simple graph. The subgraph induced by a subset W of the vertex set V is the graph (W, F), where the edge set F contains an edge in E if and only if both endpoints
of this edge are in W
Edge Removal
Edge Contraction
Vertex Removal
Graph Union
The union of two simple graphs G1 = (V1 , E1) and G2 = (V2 , E2 ) is the simple graph with vertex set V1 ∪ V2 and edge set E1 ∪ E2 . The union of G1 and G2 is denoted by G1 ∪ G2
Graph Representation
Adjacency List
Adjacency Matrices
Incidence Matrices
Isomorphism
The simple graphs G1 = (V1 , E1 ) and G2 = (V2, E2 ) are isomorphic if
Definition 1
If u, v are adjacent in G1, then f(u), f(v) will be adjacent in G2
There is a bijection f: V1(G1) -> V2(G2)
if (u, v) is an edge in G1, then (f(u), f(v)) is an edge in G2
Definition 2
Their number of components (vertices and edges) are same
Their edge connectivity is retained
Graph Invariant
A property preserved by isomorphism of graphs is called a graph invariant
Two simple graphs that are not isomorphic are called nonisomorphic
Properties
Degree sequences of G1 and G2 are same
Cycle Count
If the vertices {V1, V2, .. Vk} form a cycle of length K in G1, then the vertices {f(V1), f(V2),… f(Vk)} should form a cycle of length K in G2
Cycle count will be same
Number of vertices in a cycle should also match
Same number of vertices
Same number of edges
Same degrees
Isomorphism Using Adjacency Matrix
Ag = PAhPT
P = Permutation Matrix
Connectivity
Path/Circuit(Undirected)
Walk
A walk of length n from u to v in G is a sequence of n edges e1, ... , en of G for which there exists a sequence x0 = u, x1 , ... , xn−1 , xn = v of vertices such that ei has, for i = 1, ... , n, the endpoints xi−1 and and xi
When the graph is simple, we denote this path by its vertex sequence x0 , x1, ... , xn
Let n be a nonnegative integer and G an undirected graph
Also called
edge train, chain
Walk can repeat anything (edges or vertices)
A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a walk
Circuit/Closed Walk
A walk is a circuit if it begins and ends at the same vertex, that is, if u = v, and has length greater than zero
Circuit Rank
The Circuit rank of an undirected graph is defined as the minimum number of edges that must be removed from the graph to break all of its cycles, converting it into a tree or forest
The result is a spanning tree with |V| - 1 edges
Number of edges to remove = |E| - |V| + 1
The walk or circuit is said to pass through the vertices x1 , x2 , ... , xn−1 or traverse the edges e1 , e2, ... , en
Open Walk
A walk is an open walk if it does not begin and end at the same vertex, that is, if u = v, and has length greater than zero
Path
A path is an open walk in which no vertex appears more than once
Path/Circuit(Directed)
Path
When there are no multiple edges in the directed graph, this path is denoted by its vertex sequence x0 , x1, x2 , ... , xn
A path of length n from u to v in G is a sequence of edges e1 , e2 , ... , en of G such that e1 is associated with (x0 , x1 ), e2 is associated with (x1 , x2), and so on, with en associated with (xn−1 , xn), where x0 = u and xn = v
Circuit
A path of length greater than zero that begins and ends at the same vertex is called a circuit or cycle
A path or circuit is called simple if it does not contain the same
edge more than once
There may be more than one path that passes through a sequence of vertices, which will happen if and only if there are multiple edges between two successive vertices in the list
Connectedness in Undirected Graphs
An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph
An undirected graph that is not connected is called disconnected
we
disconnect
a graph when we remove vertices or edges, or both, to produce a disconnected subgraph
There is a simple path between every pair of distinct vertices of a connected undirected graph
Connected Component
A connected component of a graph G is a connected sub-
graph of G that is not a proper subgraph of another connected subgraph of G
Graph Cutting
Cut Vertices
Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph with more connected components or disconnects the graph. Such vertices are called cut vertices (or articulation points).
Properties
Maximum Cut Vertices
1.
If G is a nontrivial connected graph of order n, then G has at
most n − 2 cut vertices
This is the case of a chain graph where the terminal vertices are not cut vertices
2.
If T is a spanning tree of a nontrivial connected graph G, then T has at least as many cut vertices as G does
Tarjan's Algorithm for Articulation Points
Perform DFS on undirected graph
Cases
Root
Increment child counter for every unique DFS call
If number of children is greater than 1 then it is an articulation point
We don't call DFS on node visited already
Non-Root
If Node U is not root of DFS tree and it has a child V such that no vertex in subtree rooted with V has a back edge to on of the ancestors of U, then U is an articulation point
Calculate DISC, LOW values similar to Tarjan's SCC algorithm
We don't care about edge to parent because parent is gonna get removed for AP check
The parent node is not used while calculating the LOW value and only downstream edges will be used to calculate the LOW value
If for a node the number of children with LOW value greater then it is present then it is an articulation point
If there are no back edges to the an ancestor of the node then the condition will be satisfied
Cut Edges
An edge whose removal produces a graph with more connected components than in the original graph or disconnects the graph. is called a cut edge or bridge. Vertices are not changed.
Cut edge cannot be on cycle
Edge not on a cycle it is cut edge
Properties
A cut edge e ∈ G if and only if the edge 'e' is not a part of any cycle in G
The maximum number of cut edges possible is 'n-1'
Whenever cut edges exist, cut vertices also exist because at least one vertex of a cut edge is a cut vertex
If a cut vertex exists, then a cut edge may or may not exist
Tarjan's Algorithm for Bridges
Similar to algorithm for cut-vertex
Assign disc and low
If there is no back edge from a sub-graph to it's ancestor or parent (across the edge being checked) then the edge will be a bridge
The low value of the node across the edge should have a value greater than the low value of the node at the other end
Cut Vertex Set
Set of vertices whose removal creates more connected components or disconnects the graph
Removing more vertices from a cut vertex set may create one connected component, so it will not remain a cut vertex set
Vertex Connectivity Number(k)
Smallest sized cut vertex set
Cut Edge Set
Set of edges whose removal creates more connected components or disconnects the graph. Vertices are not changed.
We can always add new edges to a cut edge set and it will remain a cut vertex set
Removing all the edges from the vertex with minimum degree will create more components, so the edges will be cut edge set. So size of cut edge set will not be more than the min degree vertex
Edge Connectivity Number( λ)
Smallest sized cut edge set
Cardinality of Min-Cut Edge Set ≤ Min-Degree of the Graph
Non-Separable Graph
Connected graphs without cut vertices are called nonseparable graphs, and can be thought of as more connected than those with a cut vertex
Vertex Cut
A subset V ′ of the vertex set V of G = (V, E) is a vertex cut, or separating set, if G − V ′ is disconnected
Vertex Connectivity
We define the vertex connectivity of a noncomplete graph G, denoted by κ(G), as the minimum number of vertices in a vertex c
k-Connected
Connectedness in Directed Graphs
Strongly Connected
A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph
Weakly Connected
A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph
Strong Components of a Directed Graph
The subgraphs of a directed graph G that are strongly connected but not contained in larger strongly connected subgraphs
The maximal strongly connected subgraphs, are called the strongly connected components or strong components of G
Finding SCC
Tarjan's Algorithm
Edges
Tree Edge
Forward Edge
Cross Edge
If edge points to node not in stack, then its cross edge
Back Edge
If edge points to node in stack, then its back edge
Node Values
Discovery Time
Time at which node is discovered
Discovery time does not change
Low Value
Node with lowest discovery reachable from this node
Low value can change
Implementation
Instack variable
Normal
low[u] = min(low[u]. low[v])
Back Edge
low[u] = min(low[u]. disc[v])
During backtracking if low value = discovery time, then its head node of SCC
Once head is found we start popping till head is encountered
Edge backtracking does not involve popping
Properties
Finds all connected components
Time Complexity
O(V+E)
Counting paths between vertices
Let G be a graph with adjacency matrix A with respect to the ordering v1 , v2 , ... , vn of the vertices of the graph (with directed or undirected edges, with multiple edges and loops allowed).
The number of different paths of length r from vi to v j , where r is a positive integer, equals the (i, j)th entry of A^r
Euler Circuit/Cycle
An Euler circuit in a graph G is a simple circuit containing every edge of G only once.
A connected multigraph with at least two vertices has an Euler circuit if and only if
each of its vertices has even degree
Euler Graph
A graph which contains a Euler Cycle is called an Euler Graph
Euler Path
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree
Semi Euler Graph
An open walk which visit every edge of the graph exactly once
Hamilton Circuit
A simple circuit in a graph G that passes through every vertex exactly once except the starting vertex is called a Hamilton circuit
Diracs Theorem
Sufficient not necessary
If G is a simple graph with n vertices with n ≥ 3 such that the
degree of every vertex in G is at least n∕2, then G has a Hamilton circuit.
Ore's Theorem
If G is a simple graph with n vertices with n ≥ 3 such that
deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit
Apply even if Dirac's Theorem fails
Checking is NP-Complete
A complete graph with more than 2 vertices is Hamiltonian
Every cycle graph is Hamiltonian
Complete Undirected Graph has (N-1)!/2 Hamiltonian Cycles
Complete Directed Graph has (N-1) Hamiltonian Cycles
Bipartite Graphs of the form Kn,n or Kn+1,n or Kn,n+1 are Hamiltonian
Shortest Path
Travelling Salesman Problem
Floyd Warshall Algorithm
Properties
Shortest path calculated using via vertex v method
Good for dense graphs as there is no dependency on |E| inside the loops
All Pairs Shortest Path problem
Algorithm
Three Loops
Outer loop for intermediate vertex k
First inner loop for start vertex i
3 more items...
Initialize d[i,i] to 0
Initialize d[i,j] to c[i,j] for each edge
Time Complexity
O(|V|^3)
Manual Method
Create 2D Table with [i,i] = 0 and [i,j] = w[i,j]
Initial version of the table is D0
Calculate D1
D1 is calculated by freezing row 0 and row 1
For rows and columns of the frozen cells with infinity are frozen
For the remaining elements we apply the update for d[i,1] and d[1,j]
Similarly calculate D2 to Dn
Dijkstra’s Algorithm
Problems
Multiple paths with same weight, which one can be selected
Properties
Greedy Algorithm
Still ensures optimal solution
Single source shortest path
Works with only positive edge weights
Works on directed and undirected graphs
Relaxation
Strict
1 more item...
Non-Strict
1 more item...
Logic
Create two arrays for vertices
Distance d
1 more item...
Parent p
1 more item...
Create a priority queue Q and store all vertices in it
Create a set S to store vertices
Till Q is not empty
Get minimum distance vertex u from Q
Insert into S
For each vertex v adjacent to u
1 more item...
Set distance of Start vertex to 0
Time complexity
Initialization of weights for every vertex
O(V)
Loop over each vertex
O(V)
Find minimum cost unvisited vertex which is in a heap
1 more item...
Relax out-going Edges visited using adjacency list
2 more items...
Total Complexity
V + Vlog(V) + E(log(V)
1 more item...
Elog(V) is the dominant term
If adjacency matrix is used O(v^2)
Single Sink Shortest Path
Reverse all edges
Use sunk as source vertex
Apply Disjkastra
Bellman Ford Algorithm
Properties
Can handle negative weights
Cannot handle negative weight cycle
Single source shortest path
Logic
Relax Edges
Relax all edges |V| - 1 times
if d[v] > d[u] + c[u, v]
d[v] = d[u] + c[u, v]
Initialize source node with distance 0 and all other nodes as infinite
Order of edges does not matter
Time Complexity
|E| edges relaxed |V|-1 times
O(|V||E|)
Space complexity
V
Properties
Shortest path can change on adding a constant value to every edge as the number of edges in a path would determine the new weight along a path
Shortest path cannot change on multiplying each edge weight with a constant
Algorithm for DAG shortest path
Algorithm
Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex
Create a toplogical order of all vertices
Do following for every vertex u in topological order
Do following for every adjacent vertex v of u
2 more items...
Time Complexity
Time to initialize distance
O(V)
Each edge is visited only one (adjacency
list) under iteration over each vertex
O(E)
Total Complexity
O(V+E)
Topological sorting O(V+E)
Minimum Spanning Tree
Prim's Algorithm
Algorithm
Add any vertex to a set S
Select edge with lowest weight out of all edges incident on any vertex in S which does not form a cycle
Repeat till all vertices are covered
Properties
Greedy Algorithm
Similar to Dijkastra's Algorithm
Preferred for dense graph as O(V^2)
Time Complexity
The time complexity of Prim's algorithm depends on the data structures used for the graph and for ordering the edges by weight, which can be done using a priority queue
adjacency matrix, searching
O(|V|^2)
binary heap and adjacency list
O(|E| log| V|)
Fibonacci heap and adjacency list
O(|E| + |V| log|V|)
Kruskal's Algorithm
Algorithm
Repeat till all vertices are covered
Pick the least weight edge and add it to spanning tree if it does not form a cycle
Create Min Heap of edges
Properties
Greedy Algorithm
Preferred for sparse graphs
Time Complexity
Sorting of edges takes O(ELogE) time
After sorting, we iterate through all edges and apply find-union algorithm
The find and union operations can take atmost O(LogV) time
So overall complexity is O(ELogE + ELogV) time
The value of E can be at most O(V^2), so O(LogV) are O(LogE) same
Therefore, overall time complexity is O(ElogE) or O(ElogV)
Tips
Draw big graph on rough sheet
Carry pencil, rubber, multi color pens
Properties
If all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum
If each edge has a distinct weight then there will be only one, unique minimum spanning tree
If the weights are positive, then a minimum spanning tree is in fact a minimum-cost subgraph connecting all vertices, since subgraphs containing cycles necessarily have more total weight.
For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to an MST
This property can be used to find the minimum possible values of edge weight in cycles in numerical problems
For any cut C of the graph, if the weight of an edge e in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph
If the minimum cost edge e of a graph is unique, then this edge is included in any MST
If T is a tree of MST edges, then we can contract T into a single vertex while maintaining the invariant that the MST of the contracted graph plus T gives the MST for the graph before contraction
If the edge weights are unique then the MST generated by Kruskal and Prims will be same
If the edge weights are not unique then the MST generated by Prims and Kruskal will be different but the cost will be same
If the edge weights are unique and e is the heaviest edge of some cycle in G, then every MST of G excludes e
Problems
Unknown weights in an MST
Assume that we know a minimum spanning tree (MST) of G such that all edges of unknown weights belong to that MST. What are the maximal values of those unknown weights?
Unknown weights outside an MST
Assume that we know a minimum spanning tree (MST) of G such that all weights of edges of the MST are known. What are the minimal values of the unknown weights?
For every cycle the missing weight is greater that the largest weight
Repeatedly apply till all edges are covered
Planar Graph
A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges is the intersection of the lines or arcs representing them at a point other than their common endpoint)
Such a drawing is called a planar representation of the graph
Euler's Formula
Let G be a connected planar simple graph with e edges, v vertices and k components. Let r be the number of regions in a planar representation of G. Then r = e − v + (k + 1)
Corolorrary
If G is a connected planar simple graph with e edges and v vertices, where v ≥ 3, then e ≤ 3v − 6.
If G is a connected planar simple graph, then G has a vertex of degree not exceeding five
If a connected planar simple graph has e edges and v vertices with v ≥ 3 and no circuits of length three(no triangles), then
e ≤ 2v − 4
Homeomorphic Graphs
The graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are called homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions
K5 and K3,3 are minimum non-planar graphs
A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5
6 vertices with 9 edges in K3,3 graph
5 vertices with 10 edges in K5 graph
Every non-planar graph contains K5 or K3,3 as a subgraph
A graph is planar if and only if it does not contain a subdivision of K5 and K3,3 as a subgraph
Regions
Every planar graph divides the plane into connected areas called regions
Degree of Bounded Region
Number of edges enclosing the region
Sum of Degrees of Regions
In a planar graph with ‘n’ regions, Sum of degrees of regions is 2|E|
Special Cases
If degree of each region is K
1 more item...
If degree of each region is at least K (>=K)
1 more item...
if degree of each region is at most K (<=K)
1 more item...
This includes the region external to the graph as well
Examples
Bipartite K3,3 not planar
Complete Graph K5 is not-planar
Complete Graph K3 and K4 are planar
Dual
The dual of a planar graph is obtained by converting each face into a vertex and draw edges between vertices which share an edge in the original graph
If G is a connected planar graph with n vertices, f faces and m edges, then G* has f vertices, n faces and m edges
Dmin*F <= 2E
Graph Coloring
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color
The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of a graph G is denoted by χ(G). (Here χ is the Greek
letter chi.)
The chromatic number of a planar graph is no greater than 4
The chromatic number of Kn(Fully Connected) = n
The chromatic number of Km,n(Bipartite Graph) = 2
The chromatic number of Cycle Graph Cn= 2 if n is even and 3 if n is odd
The chromatic number of Wheel Graph Wn= 3 if n is even and 4 if n is odd
The chromatic number of Petersen Graph is 3
Technique
If we add a new color when its not possible to draw without existing number of colors we may end up using more than 4 colors to color a planar graph
Add new color before the requirement after above condition happens on the first iteration
Hamiltonian Path
An open walk in a graph G that passes through every vertex exactly once is called a Hamilton path
Semi-Hamiltonian Graph
Konigsberg Bridge Problem
Start from any node and come back to it after traversing every node exactly once
Criteria
No odd vertices
Exactly two odd vertices
Havel Hakimi Theorem
Sort the vertices in non-increasing order of degree
Remove the vertex with the highest degree
Subtract 1 from the vertices immediately next to it on the right as the count of the removed vertex
We should be able to arrive at a simplified situation where we easily predict if the degree sequence can be identified to be a simple undirected graph. Final state will be all 0s.
Explanation
Techniques
Highest degree vertex should not be more than (V-1)
Number of odd degree vertices should be even
Sort the list again
Number of graphs
Number of simple graphs with n vertices
Sum of degree of all vertices is n(n-1)
Edges = Sum of degree / 2 = n(n-1)/2
Considering we may keep or leave a vertex the number of possible graphs is 2^(n(n-1)/2)
If each vertex is connected to all other vertices, the degree of each vertex is n-1
Number of simple graphs with n vertices and e edges
Total number of edges is n(n-1)/2
We have to take e edges from this set
n(n-1)/2Ce
Clique
Clique Decision
Problem
A set C is a clique of the graph G iff C is a subset of V(G) and every pair of vertices in C is connected by an edge in G
Maximal Clique
A clique to now further vertices can be added to create a larger clique
Test
At least one vertex with minimal degree
Minimal degree = Number of Vertices - 1
Maximum Clique
The maximal clique with the largest number of vertices
Induced Subgraph
The graph formed by the vertices indicated by the clique and the corresponding edges in G
It is a complete graph
Problems
Count cliques
Covering
A covering graph is a subgraph which contains either all the vertices or all the edges corresponding to some other graph
Line/Edge Covering
Let G = (V, E) be a graph. A subset C(E) is called a line covering of G if every vertex of G is incident with at least one edge
Minimal Line Covering
A line covering C of a graph G is said to be minimal if no edge can be deleted from C
Minimum Line Covering
A minimal line covering with minimum number of edges is called a minimum line covering of ‘G’
Line Covering Number
The number of edges in a minimum line covering in ‘G’ is called the line covering number of ‘G’ (α1)
Line covering of ‘G’ does not exist if and only if ‘G’ has an isolated vertex
Vertex covering
A subset K of V is called a vertex covering of ‘G’, if every edge of ‘G’ is incident with or covered by a vertex in ‘K’
Minimal Vertex Covering
A vertex ‘K’ of graph ‘G’ is said to be minimal vertex covering if no vertex can be deleted from ‘K’
Minimum Vertex Covering
A minimal vertex covering of graph ‘G’ with minimum number of vertices is called the minimum vertex covering
Vertex covering number
The number of vertices in a minimum vertex covering of ‘G’ is called the vertex covering number of G
Independent Set
Independent Line Set
A subset L of E is called an independent line set of ‘G’ if no two edges in L are adjacent
Maximal Independent Line Set
An independent line set is said to be the maximal independent line set of a graph ‘G’ if no other edge of ‘G’ can be added to ‘L’
Maximum Independent Line Set
A maximum independent line set of ‘G’ with maximum number of edges is called a maximum independent line set of ‘G’
Line independent number/
Matching number
Number of edges in a maximum independent line set of G
Independent Vertex Set
Let ‘G’ = (V, E) be a graph. A subset of ‘V’ is called an independent set of ‘G’ if no two vertices in ‘S’ are adjacent
Maximal Independent Vertex Set
Let ‘G’ be a graph, then an independent vertex set of ‘G’ is said to be maximal if no other vertex of ‘G’ can be added to ‘S’
Maximum Independent Vertex Set
A maximal independent vertex set of ‘G’ with maximum number of vertices is called as the maximum independent vertex set
A vertex coloring is a partition of the vertex set into independent sets
Note:
By default independent set means independent vertex set
Complement of a Graph
Complement of a graph is obtained by removing the original edges of the graph and adding new edges between vertices which did not have an edge in the original graph
Number of edges in complement graph G with N vertices
= n(n-1)/2 - |E|
Tips
For complement problems try drawing them starting from the lowest possible vertex count
Self Complementary Graph
A self-complementary graph is a graph which is isomorphic to its complement
The simplest non-trivial self-complementary graphs are the
4-vertex path graph
and the 5-vertex cycle graph(Pentagon)
Binary Tree
Number of binary trees
Unlabeled nodes
2nCn/n+1
Labeled Nodes
n! * 2nCn/n+1
Directed Acyclic Graph(DAG)
Topological Sort
Algorithm 1
Implemented using DFS + Stack + Visited Array
Implementation
Start DFS from any node
Perform DFS starting from that node
Once all outgoing edges from a node are visited, perform backtracking and push it on stack
Select the next node from unvisited list if no other nodes are visit able from current nodes
The elements can be popped at the end of the process to show the topollogical sort
It is a linear ordering of vertices such that for every directed edge U->V vertex U comes before vertex V
Algorithm 2 Kahn's Algorithm
Uses BFS
A directed graph with no cycle is a directed acyclic graph
A DAG will always have a node with in-degree 0 and one node with out-degree 0
Discrete Mathematics
Propositional Logic
Truth Vaue
False
True
Logical Operators
Connectives
Disjunction
OR
Conjunction
AND
Exclusive Or
XOR
Implication/Conditional
Statements
q whenever p
p only if q
q if p
p is sufficient for q
q follows from p
q is necessary for p
p implies q
q without p is possible and can exist
p without q is impossible and cannot exist
if p then q
Antecedent,Hypothesis,Premise = p
Consequent,Conclusion= q
Conditional
Material Conditional
2 more items...
Indicative Conditional
Counterfactual Conditional
Statement Problems
P->Q
If Q is false we can infer that P if False as T->F is not allowed
P->Q can be written in any form
Identify P and Q
Cases
4 more items...
Implication and its contrapositive are equivalent
p -> q
~p V q
~(~q) V ~p
1 more item...
Converse and Inverse are equivalent
Converse
q -> p =
~q V p
Inverse
~p -> ~q = p V ~q
~q V p
Bi-Conditional
Statements
q is necessary and sufficient for p
p and q are necessary and sufficient for each other
p is necessary and sufficient for q
p and q can not exist without ech other
q if and only if p
Either p and q both exist or none of them exist
p if and only if q
p and q are equivalent
(if p then q) and (if q then p)
~p and ~q are equivalent
XNOR
(p A q) V (~p A ~q)
(p->q) A (q->p)
Negation
Replacement Rules
When
If
Either p or q
p or q
Whenever
If
Neither p nor q
not p and not q
But
And
p unless q
~q -> p
p will definitely happen if q doesn't => p will definitely happen if !q happens.
Example
I will go golfing tomorrow unless it rains
p = I will go golfing tomorrow
q = It rains
!q = It does not rain
!q -> p
1 more item...
Can be interpreted as p
if not
q
Main point here is
not q
not q
true suffices that p be true, and will generate a true output if p is true
not q
true with
false p
is a failing condition
Remaining combinations are not specified and remain true
p if (not q)
(not q) -> p
1 more item...
p unless q, in which case either p or not p
These are the accepted cases
Unaccepted case is not q and not p
Logically equivalent to
p or q
p unless q
~q -> p
1 more item...
unless is negation, so p unless q means p is always true except when q is true
Or
Disjunction
p is necessary but not sufficient for q
(q -> p) and ~(p->q)
sufficient -> necessary
Sufficient condition comes on the left
Necessary condition comes on the right
And
Conjunction
Precedence
Or
Implication
And
BiConditional
Not
Laws
Commutative
A op B = B op A
Conjunction
a A b = b A a
Disjunction
a V b = b V a
BiConditional
a <-> b = b <-> a
Associative
(a op b) op c = a op (b op c)
Conjunction
(a A b) A c = a A (b A c)
Disjunction
(a V b) V c = a V (b V c)
BiConditional
(a <-> b) <-> c = a <-> (b <-> c)
Distributive Property
:star:
Distribution of conjunction over conjunction
Distribution of conjunction over disjunction
Distribution of disjunction over conjunction
Distribution of disjunction over disjunction
Distribution of implication
Distribution of implication over equivalence
Distribution of disjunction over equivalence
Double distribution
Absorptive Law
Conjunction
A + (A.B) = A
Disjunction
A(A + B) = A
Complement Law
a A ~a = 0
a V ~a = 1
Annulment/Domination Law
a A 0 = 0
a V 1 = 1
Identity Law
a V 0 = a
a A 1 = a
Idempotent Law
a V a = a
a A a = a
Double Negation Law
~(~a) = a
de Morgan´s Theorem
~(a V b) = ~a A ~b
~(a A b) = ~a V ~b
Negation Law
p V ~p = T
p A ~p = F
Truth Table
Atomic Propositions
Propositions
A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both
propositional variables (or sentential variables)
Compound Propositions
Normal Forms
Conjunctive normal form
Conjunction of disjunctions
Techniques
a+bc = (a+b)(b+c)
a->b = ~a+b
Principal Conjunctive Normal Form
Disjunctive normal form
Disjunction of Conjunctions
Principal Disjunctive form
Contains all variables in each AND term
Multiply with (xVx') for missing x
Types of Propositions
Contradiction
Propositional Statement that is always False
Example: a A ~a
Contingency
Propositional statement that is not a Tautology or a Contradiction
Example: a V b
Tautology
Propositional Statement
that is always True
Example: a V ~a
Satisfiable
Propositional Statement
that is always True or True and False
Unsatisfiable
Valid
An argument is valid if and only if it is necessary that if all of the premises are true, then the conclusion is true
Invalid
At least one F
Valid is always satisfiable
Falsifiable
Propositional Statement
that is always False or True and False
Unfalsifiable
Satisfiable but not valid
Not all True, at least one True
Tautology = Valid = Unfalsifiable
Contradiction = Unsatisfiable
Invalid = Falsifiable
Statement Conversions
Inverse
p -> q to ~p -> ~q
Invert
Contrapositive
Inverse + Contrapositive
Converse
p -> q to q -> p
Change location
Rules
Performing any two results in the third
Since double converse and inverse return to original state, and contrapositive definition it self is this rule, this rule holds true.
Logical Equivalence
p->q = ~q-.>~p
pAq =~(q->~p)
(p->q)A(p->r) = p->(qAr)
(p->r)A(q->r) = (p^q)->r
p->q = ~p V q
pVq = ~p->q
p<->q = (p A q) V (~p A ~q)
p<->q = (p->q) A (q->p)
Predicate Logic
Predicate logic have the following features to express propositions
Variables
x, y, z, etc. (the subject of a sentence), can be substituted with an element from a domain
Predicates
P, M, etc. (the predicate of a sentence)
Domain
The collection of values that a variable can take
Quantifiers
Quantifiers provide a notation that allows us to quantify (count) how many objects in the universe
of discourse satisfy the given predicate
Types
Existential Quantifier ∃ - There exists an element
Meaning changes when the domain changes
Empty domain always leads to false
At least one quantifier
Same as disjunction
And
is used inside predicate
Universal Quantifier ∀ - For all elements
Same as conjunction
Implication
is used inside predicate
De Morgan’s Law for Quantifiers
¬∀xP(x) ≡ ∃x¬P(x)
¬∃xP(x) ≡ ∀x¬P(x)
Precedence
∀ and ∃ have more precedence than all logical operators
Binding Variable
Variables which are involved with quatifiers
Variables without qualifiers are called Free Variables
Quantification of two variables
∀ x ∀ y P(x, y)
∀ y ∀ x P(x, y)
∀ x ∃ y P(x, y)
∃ x ∀ y P(x, y)
∃ x ∃ y P(x, y)
∃ y ∃ x P(x, y) q
Nested Quantifiers
Two Quantifiers are nested if one is within the scope of the other
Everything within the scope of s quantifier can be thought of as a propositional function.
Order
The order of nested quantifiers matters if the quantifiers are of different type
The order of quantifiers does not matter if the quantifiers are of different type
Negate
Invert each quantifier and the predicate
Statement to predicate logic Conversion
Examples
Example 1
All lions are fierece
∀ x (P(x) -> Q(x))
Some lions do not drink coffee
∃ x (P(x) A ~R(x))
Some fierce creatures do not drink coffee
∃ x (Q(x) A ~R(x))
P(x) : x is lion
Q(x) : x is fierce
R(x) : x does not drink coffee
Propositional Resolution
¬β v γ is known
α v γ can be known
α v β is known
Clause
A clause is an expression formed from a finite collection of literals (atoms or their negations)
φ1 ∨ ... ∨ φn → {φ1, ... , φn}
φ1 ∧ ... ∧ φn → {φ1}, ... ,{φn}
A literal is an atomic formula (atom) or its negation
Explanation
Suppose we have the clause {p, q}. In other words, we know that p is true or q is true
Suppose we also have the clause {¬q, r}. In other words, we know that q is false or r is true
One clause contains q, and the other contains ¬q
If q is false, then by the first clause p must be true
If q is true, then, by the second clause, r must be true
Since q must be either true or false, then it must be the case that either p is true or r is true
So we should be able to derive the clause {p, r}
Rule of Inference
Logical form consisting of a function which takes premises, analyzes their syntax and returns a conclusion
Argument
A sequence of statements, premises, that end with a conclusion
Validity
A deductive argument is said to be valid if and only if it takes a form that makes it impossible for the premises to be true and the conclusion nevertheless to be false
Fallacy
An incorrect reasoning or mistake which leads to invalid arguments
Rules
~q,p->q = ~p
modus tollens
p -> q,q->r = p -> r
Hypothetical Syllogism
p,p->q = q
modus ponens
pvq, ~p = q
Disjunctive Syllogism
p = p v q
Addition
p A q = p
Simplification
p v q. ~p v r = q v r
Resolution
p, q = p A q
Conjunction
Set Theory
Set
A set is an unordered collection of distinct objects
Elements
The members of the set are called the elements of the set
contain
A set is said to contain its elements
We write a ∈ A to denote that a is an element of the set A
The notation a ∉ A denotes that a is not an element of the set A
Notation
Roster method
Listing elements of the set between curly braces
It is common for sets to be denoted using uppercase letters
Lowercase letters are usually used to denote elements of sets
Set Builder Method
Characterize all those elements in the set by stating the property or properties they must have to be members
{x ∣ x has property P}
Examples
Intervals
[a, b] = {x | a ≤ x ≤ b}
[a, b) = {x | a ≤ x < b}
(a, b) = {x | a < x < b}
(a, b] = {x | a < x ≤ b}
Venn Diagrams
Two sets are equal if and only if they have the same elements
Special Sets
Empty Set
Empty set is subset of every set
Cardinality is 0
Empty set is subset of itself
Empty set is a member of every power set
ϕ = {}
Singleton Set
Size of a set
Cardinality
If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S
The cardinality of S is denoted by |S|.
Power Set
The power set of S is the set of all subsets of the set S
Power Set of ∅
P(∅)={∅}
P(P(∅))={∅,{∅}}
P(P(P(∅)))={∅,{∅},{∅,{∅}}}
Cartesian Product
The ordered n-tuple (a1, a2, ... , an ) is the ordered collection that has a1 as its first element, a2 as its second element, ... , and an as its nth element
The Cartesian product of the sets A 1 , A2, ... , An, denoted by A1 × A2 × ⋯ × An , is the set of ordered n-tuples (a1, a2 , ... , an ), where ai belongs to Ai for i = 1, 2, ... , n
A1 × A2 × ⋯ × An = {(a1, a2, ... , an ) ∣ ai ∈ Ai for i = 1, 2, ... , n}
Using Set Notation with Quantifiers
Sometimes we restrict the domain of a quantified statement explicitly by making use of a particular notation
∀x ∈ S(P(x)) denotes the universal quantification of P(x) over all
elements in the set S
∀x ∈ S(P(x)) is shorthand for ∀x(x ∈ S → P(x))
Existential quantification of P(x)
∃x ∈ S(P(x)) is shorthand for ∃x(x ∈ S ∧ P(x))
Truth Set and Quantifiers
Given a predicate P, and a domain D, we define the truth set of P to be the set of elements x in D for which P(x) is true. The truth set of P(x) is denoted by {x ∈ D ∣ P(x)}
∀xP(x) is true over the domain U if and only if the truth set of P is the set U
∃xP(x) is true over the domain U if and only if the truth set of P is nonempty.
Set Operations
Union
Intersection
Difference
A - B or A\B
A ∩ B'
Symmetric Difference
A △ B
(A – B) ∪ (B – A)
Complement
Universal Set
Identities
Commutative laws
A ∪ B = B ∪ A
A ∩ B = B ∩ A
Complementation law
~(~A) = A
Associative laws
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C
Idempotent laws
A ∪ A = A
A ∩ A = A
Distributive laws
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Domination laws
A ∪ U = U
A ∩∅=∅
De Morgan’s laws
~(A ∩ B) = ~A ∪ ~B
~(A ∪ B) = ~A ∩ ~B
Identity Laws
A ∩ U = A
A ∪∅= A
Absorption laws
A ∪ (A ∩ B) = A
A ∩ (A ∪ B) = A
Complement laws
A ∪ ~A = U
A ∩ ~A =∅
Proving Set Identities
Subset method
Membership table
Apply existing identities
A - (B ∪ C) = (A - B) ∩ (A - C)
A - (B ∩ C) = (A - B) ∪ (A - C)
(A-B)-C = (A-C)-(B-C)
A ∩ (B - C) = (A ∩ B) - C
~(A ∪ (B - A)) = A ∪ ~B
Generalized Unions and Intersections
Operation Comparison
Simplify expression using canonical form of set difference and de morgons law
Multiset
A multiset (short for multiple-membership set) is an unordered collection of elements where an element can occur as a member more than once
Notation
The notation {m1 ⋅ a1 , m2 ⋅ a2, ... , mr ⋅ ar } denotes
the multiset with element a1 occurring m1 times, element a2 occurring m2 times, and so on
The numbers mi, i = 1, 2, ... , r, are called the multiplicities of the elements ai , i = 1, 2, ... ,r
We can use the same notation for a multiset as we do for a set, but each element is listed the number of times it occurs.
The cardinality of a multiset is defined to be the sum of the multiplicities of its elements
Operations
Union
The union of the multisets P and Q is the multiset in which the
multiplicity of an element is the maximum of its multiplicities in P and Q
Intersection
The intersection of multisets P and Q is the multiset in which the multiplicity of an element is the minimum of its multiplicities
in P and Q
Difference
The difference of P and Q is the multiset in which the multiplicity of an element is the multiplicity of the element in P less its multiplicity in Q unless this difference is negative,
in which case the multiplicity is 0
Sum
The sum of P and Q is the multiset in which the multiplic-
ity of an element is the sum of multiplicities in P and Q
Countability
Countable Set
A set is called countable when its elements can be counted
A countable set can be finite or infinite
Power set of countably infinite set is uncountable
Cardinality
Cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets
Cardinality is defined in terms of bijective functions
Two sets have the same cardinality if, and only if, there is a one-to-one correspondence (bijection) between the elements of the two sets
It is possible for a proper subset of an infinite set to have the same cardinality as the original set—something that cannot happen with proper subsets of finite sets
Permutations on Subset
Let A be a set of N elements
We take a subset out of it B
We create a permutation of the N-elements
We can apply the permutation to the subset B
Example
Let A = {1,2,3,4}
Let the permutation be {3,4,1,2}
Let B = {3, 4}
Permutation of B will be {1, 2}
Functions
Definition
Let A and B be nonempty sets
A function f from A to B is an assignment of exactly one
element of B to each element of A. We write f (a) = b if b is the unique element of B assigned
by the function f to the element a of A. If f is a function from A to B, we write f : A → B
Functions are sometimes also called mappings or transformations
Relation
A function f : A → B can also be defined in terms of a relation from A to B
A relation from A to B that contains one, and only one, ordered pair (a, b) for every element a ∈ A, defines a function f from A to B
This function is defined by the assignment f (a) = b, where (a, b) is the unique ordered pair in the relation that has a as its first element
Specification
Sometimes we explicitly state the assignments,
Often we give a formula, such as f (x) = x + 1, to define a function
Domain/Codomain
If f is a function from A to B, we say that A is the domain of f
Image/Pre-Image
If f (a) = b, we say that b is the image of a and a is a preimage of b
Range/Pre-Image
The range, or image, of f is the set of all images of elements of A
Range maybe a subset of codomain
Equality
Two functions are equal when they have the same domain, have the same codomain, and map each element of their common domain to the same element in their common codomain
if we change either the domain the codomain of a function, then we obtain a different function
If we change the mapping elements, then we also obtain a different function
Types of functions
One-To-One
A function f is said to be one-to-one, or an injection, if and only if
f(a) = f (b) implies that a = b for all a and b in the domain of f. A function is said to be injective if it is one-to-one
Number of on-to-one functions(m->n) is nPm
Increasing
A function f whose domain and codomain are subsets of the set of real numbers is called increasing if f (x) ≤ f (y), and strictly increasing if f (x) < f (y), whenever x < y and x and y are in the domain of f
Decreasing
f is called decreasing if f (x) ≥ f (y), and strictly decreasing
if f (x) > f (y), whenever x < y and x and y are in the domain of f
Onto
A function f from A to B is called onto, or a surjection, if and only if for every element b ∈ B there is an element a ∈ A with f (a) = b. A function f is called surjective if it is onto
Number of Onto Functions
n^m - [nC1*(n-1)^m - nC2*(n-2)^m + nC3*(n-3)^m ... nCn*(n-n)^m]
Bijective
The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective
Inverse Functions
Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that f (a) = b. The inverse function of f is denoted by f −1. Hence, f −1 (b) = a when f (a) = b
A one-to-one correspondence is called invertible because we can define an inverse of this function
A function is not invertible if it is not a one-to-one correspondence, because the inverse of such a function does not exist
Composition of Functions
Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions f and g, denoted for all a ∈ A by f ◦g, is the function
from A to C defined by ( f◦g)(a) = f (g(a))
Graphs of Functions
Let f be a function from the set A to the set B. The graph of the function f is the set of ordered pairs {(a, b) ∣ a ∈ A and f (a) = b}
Partial/Total Function
A partial function f from a set A to a set B is an assignment to each element a in a subset of A, called the domain of definition of f , of a unique element b in B
The sets A and B are called the domain and codomain of f , respectively
We say that f is undefined for elements in A that are not in the domain of definition of f
When the domain of definition of f equals A, we say that f is a total function
Number of Functions
(Size of Codomain) ^ (Size of Domain)
Domain
Domain for Binary Function
For n variables = 2^n
If domain has more than one variable, the size of domain is the product of the number of possible values of each value
Domain for Ternary Function
For n variables = 3^n
Relation
Binary Relation
Let A and B be sets. A binary relation from A to B is a subset of A× B
When (a, b) belongs to R, a is said to be related to b by R.
We use the notation a R b to denote that (a, b) ∈ R and a ̸R b to denote that (a, b) ∉ R
A relation on a set A is a relation from A to A
Properties of Relations
Reflexive
A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A
Number of Reflexive Relations
Total number of tuples = n^2
Number of Tuples needed for reflexive relation = n
Remaining tuples are optional
2^(n^2-n) = 2^(n(n-1))
Non-Reflexive
If for any a ∈ A,, (a, a) does not belong to a relation then it is non-reflexive
Definition is based on the set on which relation is defined and needs to satisfy for every element of set
Symmetric
A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A
Number of Symmetric Relations
Two sets
Upper Triangle Matrix
2^(n(n-1)/2)
Main Diagonal
2^n
2^(n(n+1)/2)
Definition is based on the tuples in relation and not on the content of the set on which relation is defined
Anti-Symmetric
A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric.
If a single case violates the condition then it is not anti-symmetric
Number of anti-symmetric relations
Two Sets
Upper Triangle Matrix
Three Choices
(x,y)
(y,x)
-
3^(n(n-1)/2)
Diagonal Elements
2^n
2^n*3^(n(n-1)/2)
Definition is based on the tuples in relation and not on the content of the set on which relation is defined
Maximum Cardinality
n(n+1)/2
Transitive
A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A
Any relation whose graph contains both types of arrows (single-sided and doublesided) will be neither symmetric nor antisymmetric.
Any relation on a set A that is both anti-symmetric and symmetric then has its graph consisting of only loops (i.e. is of the form R={(a,a) | a∈S⊆A} for some S⊆A
Asymmetric
Anti-Symmetric + Not Reflexive
3^(n(n-1)/2)
Irreflexive
A relation is irreflexive if no (a, a) belongs to the relation
Number of Irreflexive relation
2^(n^2-n) = 2^(n(n-1))
Same reasoning as reflexive but no (a, a) included in the relation
Number of relations which are neither reflexive nor irreflexive = 2^(n*n) - 2^(n*(n-1)+1)
Summary of number of relations of type
Combining Relations
Because relations from A to B are subsets of A × B, two relations from A to B can be combined in any way two sets can be combined
Composite Relation
Let R be a relation from a set A to a set B and S a relation from B to a set C
The composite of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S
We denote the composite of R and S by S ◦ R
Powers of Relation
The powers Rn , n = 1, 2, 3, ... , are defined recursively by
R1 = R
Rn+1 = Rn ◦ R.
The relation R on a set A is transitive if and only if Rn ⊆ R for n = 1, 2, 3, ...
Set Combinations
R1 ∩ R2
R1 − R2
R1 ∪ R2
R2 − R1
n-ary relation
Let A1, A2, ... , An be sets. An n-ary relation on these sets is a subset of A1 × A2 × ⋯ × AnThe sets A1 , A2 , ... , An are called the domains of the relation, and n is called its degree
Operations
Selection Operator
Let R be an n-ary relation and C a condition that elements in R may satisfy. Then the selection operator sC maps the n-ary relation R to the n-ary relation of all n-tuples from R that satisfy the condition C.
Projection
The projection Pi1 i2 ,...,im where i1 < i2 < ⋯ < im ,m-tuple (ai1 , ai2 , ... , aim ), where m ≤ n
In other words, the projection Pi1 ,i2 ,...,im deletes n − m of the components of an n-tuple, leaving the i1 th, i2 th, ... , and im th components
Join
Let R be a relation of degree m and S a relation of degree n
The join Jp (R, S), where p ≤ m and p ≤ n
Jp is a relation of degree m + n − p that consists of all
(m + n − p)-tuples (a1, a2, ... , am−p , c1 , c2, ... , cp , b1 , b2, ... , bn−p)
m-tuple (a1 , a2, ... , am−p , c1 , c2, ... , cp ) belongs to R and the n-tuple (c1, c2 , ... , cp, b1, b2, ... , bn−pbelongs to S
Matrix Representation
A relation between finite sets can be represented using a zero–one matrix
Suppose that R is a relation from A = {a1 , a2, ... , am } to B = {b1, b2 , ... , bn }
The relation R can be represented by the matrix MR = [mij ]
mij =
1 if (ai , bj) ∈ R
0 if (ai , bj) ∉ R
Relation on a set
The matrix of a relation on a set, which is a square matrix
It can be used to determine whether
the relation has certain properties
Reflexive
R is reflexive if all the elements on the
main diagonal of MR are equal to 1
Symmetric
R is symmetric if and only if mji = 1 whenever
mij = 1
This also means mji = 0 whenever mij = 0
Anti-Symmetric
the matrix of an antisymmetric relation has the property that if mij = 1 with i ≠ j, then mji = 0. Or, in other words, either m ij = 0 or mji = 0 when i ≠ j
Composite
R is a relation from A to B and S is a relation from B to C
A, B, and C have m, n, and p elements
Let the zero–one matrices for S ◦ R, R, and S be MS ◦ R = [tij], MR = [rij], and MS = [sij ], respectively
The ordered pair (ai, cj ) belongs to S ◦ R if and only if there is an element bk such that (ai , bk ) belongs to R and (bk , cj ) belongs to S
It follows that tij = 1 if and only if rik = skj = 1 for some k
Digraph Representation
The relation R on a set A is represented by the directed graph that has the elements of A as its vertices and the ordered pairs (a, b), where (a, b) ∈ R, as edges
This assignment sets up a one-to-one correspondence between the relations on a set A and the directed graphs with A as their
set of vertices
Thus, every statement about relations corresponds to a statement about directed graphs, and vice versa
Directed graphs give a visual display of information about relations.
Properties
Reflexive
A relation is reflexive if and only if there is a loop at every vertex of the directed graph
Symmetric
A relation is symmetric if and only if for every edge between distinct vertices in its digraph there is an edge in the opposite direction, so that (y, x) is in the relation whenever (x, y) is in the relation
Anti-Symmetric
A relation is antisymmetric if and only if there are never two
edges in opposite directions between distinct vertices
Transitive
a relation is transitive if and only if whenever there is an edge from a vertex x to a vertex y and an edge from a vertex y to a
vertex z, there is an edge from x to z
Closures
If R is a relation on a set A, it may or may not have some property P, such as reflexivity, symmetry, or transitivity
When R does not enjoy property P, we would like to find the smallest relation S on A with property P that contains R
If R is a relation on a set A, then the closure of R with respect to P, if it exists, is the relation S on A with property P that contains R and is a subset of every subset of A × A containing R with property P
Types
Symmetric
R = R∪R−1
Transitive
Path
A path from a to b in the directed graph G is a sequence of edges (x0, x1 ), (x1 , x2), (x2, x3 ), ... , (xn−1 , xn ) in G, where n is a nonnegative integer, and x0 = a and xn = b, that is, a sequence of edges where the terminal vertex of an edge is the same as the initial vertex in the next edge in the path
This path is denoted by x0 , x1, x2 , ... , xn−1 , xn and has length n
We view the empty set of edges as a path of length zero from a to a
A path of length n ≥ 1 that begins and ends at the same vertex is called a circuit or cycle
Moreover, an edge in a directed graph can occur more than once in a path
A path in a directed graph can pass through a vertex more than once
There is a path from a to b in R if there is a sequence of elements a, x1 , x2, ... , xn−1,with (a, x1 ) ∈ R, (x1 , x2) ∈ R, ... , and (xn−1 , b) ∈ R
Let R be a relation on a set A. There is a path of length n, where n is a positive integer, from a to b if and only if (a, b) ∈ Rn
Connectivity Relation
Let R be a relation on a set A. The connectivity relation R∗ consists of the pairs (a, b) such that there is a path of length at least one from a to b in R
R∗ = R ∪ R2 ∪ R3 ∪ ⋯ ∪ Rn
Let MR be the zero–one matrix of the relation R on a set with n elements. Then the zero–one matrix of the transitive closure R∗ is
MR∗ = MR ∨ MR[2] V MR[3] V .... V MR[n]
The transitive closure of a relation R equals the connectivity relation R∗
While finding transitive closure adding a tuple might require more tuples to be added, so checking again after adding each tuple till not further tuples need to be added
Reflexive
R = R∪Δ
Diagonal relation Δ = {(a, a) ∣ a ∈ A}
Equivalence Relation
A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive
Two elements a and b that are related by an equivalence relation are called equivalent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation
Equivalence Class
Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a
The equivalence class of a with respect
to R is denoted by [a]R
When only one relation is under consideration, we can delete the
subscript R and write [a] for this equivalence class
If R is an equivalence relation on a set A, the equivalence class of the element a is [a]R = {s ∣ (a, s) ∈ R}
Representative
Any element of a class can be used as a representative of this class
There is nothing special about the particular
element chosen as the representative of the class
If b ∈ [a]R , then b is called a representative of this equivalence class
Partition of a set
A partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union
An equivalence relation partitions a set
Let R be equivalence relation on a set A
The union of the equivalence classes of R is all of A, because
an element a of A is in its own equivalence class, namely, [a]R
⋃ [a]R = A
a ∈ A
[a]R ∩ [b]R = ∅ when [a]R ≠ [b]R
These two observations show that the equivalence classes form a partition of A, because they split A into disjoint subsets.
These statements for elements
a and b of A are equivalent:
aRb
[a] = [b]
[a] ∩ [b] ≠ ∅
Partition to relation
Cross product each partition with itself
Number of equivalence relations
= Number of ways to partition a set
n'th
Bell Number
Partial Ordering
A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive
Poset
A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R)
Members of S are called elements of the poset
Comparable
The elements a and b of a poset (S, ) are called comparable if either a b or b a. When a and b are elements of S such that neither a b nor b a, a and b are called incomparable
Total Order
If (S, ) is a poset and every two elements of S are comparable, S is called a totally ordered or linearly ordered set, and is called a total order or a linear order.
A totally ordered set is also called a chain
Well Ordered Set
(S, ) is a well-ordered set if it is a poset such that is a total ordering and every nonempty subset of S has a least element.
Principle of Well
Ordered Induction
Suppose that S is a well ordered set.
Then P(x) is true
for all x ∈ S, if
Inductive Step
For every y ∈ S, if P(x) is true for all x ∈ S with x ≺ y, then P(y) is True
Poset Bounds
Least Upper Bound
It is one of the lower bound elements which is greater than all
the other upper bound elements
All the upper bounds should be related
If any two upper bounds are not related then there is no LUB
Lower Bound
These are the elements that are less than than or equal
to all the elements in a subset A of poset S
Contains the minimal elements in S
Upper Bound
These are the elements that are greater than or equal
to all the elements in a subset A of poset S
Includes the maximal elements in S
Greatest Lower Bound
It is one of the upper bound elements which is less than all
the other upper bound elements
All the lower bounds should be related
If any two lower bounds are not related then there is no GLB
Technique
Common ancestor
Color flow
Maximal/Minimal
Maximal
x is maximal if there is no xRy for all y in S except x
No element on top of it, similar to local maxima
There can be multiple maximal elements
Minimal
x is minimal if there is no yRx for all y in S except x
No element below it, similar to local minima
There can be multiple minimal elements
Minimum
x is minimum if xRy is true for all y in S except x
All elements are above it
Similar to global minima
Maximum
x is maximum if yRx is true for all y in S except x
All elements are below it
Similar to global maxima
Lattices
Lattice
A partially ordered set in which every pair of elements has both a least upper bound and greatest lower bound is called a lattice
Join Semi Lattice ∨
A partially ordered set in which every pair of elements has a least upper bound is called a join semi-lattice
Meet Semi Lattice ^
A partially ordered set in which every pair of elements has a greatest lower bound is called a meet semi-lattice
Bounded Lattice
Universal Lower Bound = 0
Every finite lattice is bounded lattice
Universal Upper Bound = 1
Complement
a ^ b = 0
a ∨ b = 1
There can be more than one complement
Complement may not exist
Complemented Lattice
Every element has a complement
All complement lattice are bounded
Distributive Lattice
For every three elements a, b, c
a ^ (b ∨ c) = (a ^ b) ∨ (a ^ b)
a ∨ (b ^ c) = (a ∨ b) ^ (a ∨ b)
Properties
M3-N5 theorem
6 more items...
2 more items...
Every sublattice of a distributive lattice is itself a distributive lattice
If a lattice is distributive, its covering relation forms a median graph
Every distributive lattice is also modular
Distributive lattice many not be bounded
Boolean Lattice
Complemented and Distributive Lattice
The complementation map is one-to-one
Every element has exactly one complement
Module Lattice
a ≤ b implies a ∨ (x ∧ b) = (a ∨ x) ∧ b for every x
Unbounded Lattice
Hasse Diagram
Represent elements of the set with dots
Reflexive and Transitive edges are not drawn for brevity
Start with smallest element as per the nature of the relation
And edge between two dots means they they are directly related
While adding a new element start with the superior element and the subordinate elements down the chain will automatically comply. There can be multiple superiors to compare against.
The diagram has the element on the LHS of the relative below the element on the RHS
Chain
A sequence of nodes connected by alternate edges from the bottom to the top
Horizontal Line
Total Order
Number of Equivalence Relations
Problem Types
Comparing pair of numbers
Notation to use
Draw lines with slope denoting the relation needed <, <= or > or >=
For transitive properties draw lines as per the property to prove/disprove
Empty Relation
Empty relation is Irreflexive, Symmetric, Anti Symmetric, Asymmetric, Transitive
Number of Relations
Total tuples = n^2
Total Relations = 2^(n^2)
Combinatorial Theory
Product Rule
Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1*n2 ways to do the procedure
Applied when events are simultaneous or consecutive and all events occur
Sum Rule
If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same as any of the set of n2 ways, then there are n1 + n2 ways to do the task.
Used when events are mutually exclusive, i.e only one can occur
Subtractation Rule
If a task can be done in either n1 ways or n2 ways, then the
number of ways to do the task is n1 + n2 minus the number of ways to do the task that are common to the two different ways
Called principle of inclusion–exclusion
Division Rule
There are n∕d ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w
Tree Diagram
Pigeonhole Principle
If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects
A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one
Generalized
If N objects are placed into k boxes, then there is at least one box containing at least ⌈N∕k⌉ objects
When to use?
Key statements
Number of items to be selected till K objects with the same attribute are selected
Number of items to be selected till K objects are from the same group
Number of groups are given
Number of groups = Number of Boxes
Total number of objects across all the categories does not matter
Every sequence of n^2 + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing
P&C
Permutations
P(n, r) = n(n − 1)(n − 2) ⋯ (n − r + 1)
If n and r are integers with 0 ≤ r ≤ n, then P(n, r) = n!/(n-r)!
Circular Permutation
Shifted versions of permutation are same
Clockwise and anticlockwise can be same if permutation can be viewed opposite directions(front-back)
Formula
CW and AW different
nPr/r
CW+AW Same
nPr/2r
Derangements
Number of derangements = floor(n!/e)
Derangements = Permutations where no object is in it original position
Combinations
C(n, r) = n!/r!(n-r)!
Combination with Replacement
C(n+r-1, r)
Examples
X1+X2+X3+...+Xn = r
Think of r positions on a line along with n-1 positions to hold n-1 selections
n-1 positions can be selected on the line with no collision
The number of elements between the lines represent the values of Xi
Number of ways to select C(r+n-1, n-1)
Number of ways of distributing r similar things among n different things
Given n objects, we want to select r objects with replacement
Inclusion/Exclusion
Inclusion
C(n-p, r-p)
Exclusion
C(n-p,r)
Binomial Theorem
(x + y)^n = Sum(C(n, r)x^n-ry^r
Sum(P(n, r)) = 1
Sum((-1)^rP(n, r)) = 0
Sum2^kP(n, k) = 3^n
Pascals Identity
P(n+1, k) = P(n, k-1) + P(n, k)
Vandermonde's Identity
P(m+n, r) = Sum(P(m, r - k)*P(n, k)
P(2n, n) = Sum[k=0-n](n, k)^2
P(n+1, r+1) = Sum[j=r-n](Pj, r)
Generalized
Permutations with Repetition
The number of r-permutations of a set of n objects with repetition allowed is n^r
Combinations with Repetition
There are C(n + r − 1, r) = C(n + r − 1, n − 1) r-combinations from a set with n elements when repetition of elements is allowed
Permutations with repetations
The number of different permutations of n objects, where there are n1 indistinguishable objects of type 1, n2 indistinguishable objects of type 2, ... , and nk indistinguishable objects of type k, is
n! / n1!n2!n3!...nk!
Distribute Objects
Distinguishable Objects Distinguishable Boxes
The number of ways to distribute n distinguishable objects into k distinguishable boxes so that ni objects are placed into box i, i = 1, 2, ... , k, equals n! / n1!n2!n3!...nk!
InDistinguishable Objects Distinguishable Boxes
C(O + B − 1, O) = C(O + B − 1, B − 1)
O objects in B boxes
Distinguishable Objects InDistinguishable Boxes
Sum[j=1-k]S(n, j) = Sum[j=1-k]1/j!Sum[i=0-(j-1)]((-1)^iP(j, i)(j-1)^n
InDistinguishable Objects InDistinguishable Boxes
Distributing n indistinguishable objects into k indistinguishable boxes is the same as writing n as a sum of at most k positive integers in non-increasing order.
There is no simple closed formula for this number
Generating Permutations
Lexicographic Order
In this ordering, the permutation a1 a2 ⋯ an precedes the
permutation of b1 b2 ⋯ bn , if for some k, with 1 ≤ k ≤ n, a1 = b1, a2 = b2, ... , ak−1 = bk−1 , and ak < bk
Find next permutationin Lexicographic Order
Find increasing subsequence from reverse order
Generating Combinations
Generating the Next Larger Bit String
Generating the Next r-Combination in Lexicographic Order
Groups
Types
Semi-Group
Is Algebraic Structure
Associativity
(x*y)*z = x*(y*z)
Sub-Semigroup
(S, *) is a semigroup
T is a subset of S
T is closed on *
(T, *) is the sub-semi group
Monoid
Is a Semi Group
Has Identity Element
a*e = a
Sub-Monoid
(M, *) is a monoid
N is a subset of M
N is closed on M
Identity element is present in N
(N, *) is the sub-monoid
Groups
Properties
Is a Monoid
Has Inverse element
Finite Group
Finite number of elements
Order of group = Number of elements in the group
Closure property may be violated while creating finite group
Examples
{-1, 1}, *
{1,
ω
,
ω
^2}, *
{1, -1, i, -i}, *
Modulo
Addition Modulo
{0, 1, 2, 3}, +4
Multiplication Module
{1, 2, 3, 4}, X5
Order of
an element
Smallest n such that a^n = e
Order of identity element is 1
Order of an element is not defined for infinite set except identity element
Order of element
The order of every element of a finite group is finite
The Order of an element of a group is the same as that of its inverse a-1.
If a is an element of order n and p is prime to n, then ap is also of order n
Order of any integral power of an element b cannot exceed the order of b
If the element a of a group G is order n, then ak=e if and only if n is a divisor of k
The order of the elements a and x-1ax is the same where a, x are any two elements of a group
If a and b are elements of a group then the order of ab is same as order of ba
Cyclic Group
An element of a group can generate other members of the group using different powers, known as generator element
Group with at least one generator element is called a cyclic group
Cayley Table
Tricks to fill Cayley Table
if p*q = e then p is the inverse of q and q*p = e
if group is of order prime^2 then it is abelian and x*y = y*x
Permutations
Use the property that every column, row is unique
Because the cancellation property holds for groups, no row or column of a Cayley table may contain the same element twice
Cayley table is a latin square
Sub-Group
Types
Improper/Trivial
G itself
Only identity element
Proper
Any sub-group other than the trivial sub-group
N <= Z <= Q <= R <= C
Q = Rational Numbers
R = Real Numbers(Rational + Irrational)
Z = Integers
C = Complex Numbers
N = Natural Numbers
Properties
The identity of H is the same as that of G
The inverse of any element is the same in H and G
Lagrange’s Theorem
If H is a subgroup of finite group G then the order of subgroup H divides the order of group G
Subgroup will have all the properties of a group
A subgroup H of the group G is a normal subgroup if g -1 H g = H for all g ∈ G
If H < K and K < G, then H < G (subgroup transitivity)
if H and K are subgroups of a group G then H ∩ K is also a subgroup
Union
if H and K are subgroups of a group G then H ∪ K may or may not be a subgroup
if H and K are subgroups of a group G where H ⊆ K then H ∪ K is a subgroup
Coset
Let H be a subgroup of a group G. If g ∈ G, the right coset of H generated by g is, Hg = { hg, h ∈ H }; and similarly, the left coset of H generated by g is gH = { gh, h ∈ H }
Properties
Inverse
(XY)^-1 = Y^-1X^-1
Abelian/Commutative Group
Is a group
Is commutative
The number of non-isomorphic abelian groups of order n is the product of the number of the partitions(Bell Number) of the power of the prime factors of n
A group whose order is the square of a prime is abelian
Properties
Every subgroup of an abelian group is abelian
Algebraic Structure
Closure
The output of operation on two elements of a set belongs to the same set
Notation
Assume operation if variable are written together like a = g-1bg is a = g-1*b*g
Sequences And Summations
Recurrence Relation
A recurrence relation for the sequence {an } is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1 , ... , an−1 , for all integers n with n ≥ n0 , where n0 is a nonnegative integer
A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation
A recurrence relation is said to recursively define a sequence
The initial conditions for a recursively defined sequence specify the terms that precede the first term where the recurrence relation takes effect
Subtitution
Forward Substitution
Found successive terms beginning with the initial condition and ending with an
Backward Substitution
Begin with an and iterate to express it in terms of falling terms of the sequence until we find it in terms of a1
Closed Form
Express an in terms of n only and not other ai
Iteration
Repeatedly use the recurrence relation
When we use iteration, we essentially guess a formula for the terms of the sequence
Linear Recurrence Relation
A Recurrence Relations is called linear if its degree is one
General Form
ar = C1*ar-1 + C2*ar-2 + ... + Ck*ar-k + f(r)
C1, C2, ... Ck are real numbers and Ck != 0
Types
Homogeneous
f(r) = 0
Solve polynomial equation
Unique roots
Solve for C1, C2 ... using the initial conditions
Solution is of form ar = C1*S1^r + C2*S2^r + C3*S3^r + ....
Repeated Roots
Solution is of form ar = C1*S1^r + C1*r*S1^r + C3*n^2*S1^r + ....
Non-Homogeneous
f(r) != 0
Split into homogeneous and particular solution
Ignore f(r) to determine homogeneous solution but don't use initial conditions to solve the unknowns yet
Particular Solution
Guess the particular solution as it is of them form of the f(r) most of the time
The particular solution does not use initial conditions for solving the unknowns
The particular solution is a function of r
The unknowns in the homogeneous solution are resolved after combining with the particular solution
Generating Function
A generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of number an that is indexed by the natural numbers
Usage
Using Generating Functions to Solve Recurrence Relations
Proving Identities via Generating Functions
Generating functions transform problems about
sequences into problems about functions
This is great because we’ve got piles of mathematical machinery for manipulating functions. Thanks to generating functions, we can apply all that machinery to problems about sequences.
The generating function for the sequence a0, a1 , ... , ak, ... of real numbers is the infinite series G(x) = a0 + a1 x + ⋯ + ak x^k + ⋯
Types
Ordinary Generating Function
Exponential Generating Function
Poisson Generating Function
Fibonacci Generating Function
<1,1,1,..> = 1/(1-x)
<1,2,3,...> = 1/(1-x)^2
<0,1,2,...> = x/(1-x)^2
<1,4,9,...> = (1+x)/(1-x)^3
<0,1,4,9,...> = x(1+x)/(1-x)^3
Binomial Generating Function
(1+x)^k
<kC0,kC1,...,kCk,0,0,0,...>
Operations
Scaling
Addition
Right Shifting
Derivative
Products
Rules to find generating function
n can be add by derivative and multiplying with x
n^2 can be added in a similar way
Product with constant can be obtained by multiplying the generator with 5
Sequence
A sequence is a function from a subset of the set of integers (usually either the set {0, 1, 2,…} or the set {1, 2, 3,…}) to a set S
We use the notation an to denote the image of the integer n.
We call an a term of the sequence
We use the notation {an} to describe the sequence
Special Integer Sequences
Practice
Ideas
Divide successive terms to determine multiplier and then refine