Graph Cycles and Algorithms

Eulerian Cycle

• A Eulerian cycle visits every edge of a graph exactly once and returns to the starting vertex
• A graph has an Eulerian cycle if and only if every vertex has an even degree (number of edges incident to it)
• Useful for problems involving traversal of all connections, like street cleaning or network routing

Hamiltonian Cycle

• A Hamiltonian cycle visits every vertex of a graph exactly once and returns to the starting vertex
• Determining whether a graph has a Hamiltonian cycle is an NP-complete problem
• Relevant in route optimization problems, such as the traveling salesman problem

Dijkstra's Algorithm

• An algorithm for finding the shortest paths between nodes in a graph
• It begins at the source node and iteratively explores the nearest nodes
• It maintains a set of visited nodes and a set of unvisited nodes, updating shortest path estimates as it proceeds
• Applicable to network routing, GPS navigation, and logistics optimization

Dominant Set

• A dominant set in a graph is a set of vertices such that every vertex not in the set is adjacent to at least one vertex in the set
• Finding a minimum dominant set is an NP-hard problem
• Useful in problems such as finding the smallest set of servers to cover a network

Graph Coloring

• Graph coloring assigns colors to the vertices of a graph such that no two adjacent vertices share the same color
• The chromatic number χ(G) of a graph G is the minimum number of colors needed to color it
• Used in scheduling, resource allocation, and map coloring

Chromatic Number

• The chromatic number is the minimum number of colors needed to color a graph
• Determining the chromatic number of a graph is an NP-hard problem
• Applications include register allocation in compilers and exam scheduling

Brook's Theorem

• Brook's Theorem states that for any connected graph G that is not a complete graph or an odd cycle, the chromatic number χ(G) is at most Δ(G), where Δ(G) is the maximum degree of the graph
• Provides an upper bound on the chromatic number of a graph

Vizing's Theorem

• Vizing's Theorem states that the edge chromatic number of a graph (the minimum number of colors needed to color the edges such that no two adjacent edges share the same color) is either Δ(G) or Δ(G) + 1, where Δ(G) is the maximum degree of the graph
• Helps in edge coloring problems, like scheduling tasks on processors

Recurrence Relation

• A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s)
• Used to model problems that can be broken down into smaller, self-similar subproblems

Asymptotic Notation

• Asymptotic notation describes the limiting behavior of a function as the argument tends towards infinity
• Common types include Big O notation (O), Big Omega notation (Ω), and Big Theta notation (Θ)
• Used to classify the efficiency of algorithms

Recurrence Relation Examples

• Tower of Hanoi: T(n) = 2T(n-1) + 1
• Sum of n natural numbers: T(n) = T(n-1) + n
• Binary search: T(n) = T(n/2) + O(1)
• Fibonacci: T(n) = T(n-1) + T(n-2)
• Linear Recurrence: T(n) = aT(n-1) + bT(n-2) + ...
• Merge Sort: T(n) = 2T(n/2) + O(n)
• Quick Sort: T(n) = T(k) + T(n-k-1) + O(n) (where k is the partition size)

Catalan Number

• The nth Catalan number is given by the formula C_n = (1/(n+1)) * (2n choose n)
• Appears in various counting problems, such as balanced parentheses, binary trees, and triangulations of polygons

Master's Theorem

• Master's Theorem provides a cookbook solution for recurrence relations of the form T(n) = aT(n/b) + f(n)
• Based on comparing f(n) to n^(log_b a)
• It has three cases that determine the asymptotic complexity of the recurrence

Minimum Number of Nodes in Trees

• Full binary tree of height h: 2^(h+1) - 1 nodes
• Complete binary tree of height h: at least 2^h - 1 and at most 2^(h+1) - 1 nodes

Minimum Height of Trees

• Full or complete binary tree with n nodes: height is approximately log_2(n+1) - 1
• A binary tree with n nodes has a minimum height of floor(log2(n))