نظریه گرافها برای المپیاد کامپیوتر
Basic Definitions
Introduction to Graphs and Graph Modeling
Types of Graphs
Graph Implementation
Walks, Trails, Paths, Extremal
Subgraphs
Connectivity, Cut Edge, and Cut Vertex
Bipartite Graph
Trees
Introductory Properties
Distance in Tree and Graph
Counting the Number of Trees
DFS
BFS
Algorithm for Finding Tree Diameter
DFS Start/Finish Time
Cut Vertex and Bridge Algorithms
Idea Cultivation Workshop
Directed Graph
Definitions
Tournament
Directed Acyclic Graph
Strongly Connected Components
Detecting Cycles in a Directed Graph
Games and Directed Graphs
Functional Graphs and Permutation Graphs
Proof Techniques for Graph Problems
Extremal Choices
Contracting
Graph and Magic
Eulerian Tour and Hamiltonian Cycle
Introduction
Eulerian Tour in Directed and Undirected Graphs
De Bruijn sequence
Existence Theorems for Hamiltonian Cycles
Exponential Algorithms for Finding Hamiltonian Cycles and Paths
Shortest Path Algorithms
Bellman-Ford
Dijkstra
Floyd-Warshall
Matrices
Matrices and Operations on Them
Determinants of Matrices
Incidence Matrix
Adjacency Matrix
Number of Walks of Length n
Obtaining Recursive Functions Using Graphs and Matrices
Tree Data Structures
Binary Tree
Binary Search Tree (BST)
Heap
DSU
Segment Tree
Trie
NP and NP-complete Problems
NP and NP-complete Definitions
Proof of NP-Completeness of the SAT Problem
Graph NP-Complete Problems
Lca
Problem Description
O(n+q*lg(n)) Solution using Heavy-Light Decomposition
Tarjan's Offline Algorithm
Relationship between LCA and RMQ
LCA Linear Time Solution
Virtual Tree
Advanced Tree Algorithms
Minimum Spanning Tree
Sack
Centroid
Huffman Coding
Tree Hashing
Heavy-Light Decomposition (HLD)
Connectivity
Cuts and Connectivity
k-connected Graph
Max-Flow Min-Cut
Matching
Introduction
Matching in Bipartite Graphs
Min-Max Theorems
Applications
Maximum Flow and Matching
Poset
Matching in General Graphs
Special Topics
Planar Graph
Degree Sequence
Coloring
Identical Graphs
Random Walk
Ramsey Numbers
Independent Set and Clique
2-SAT
Several Special Matrices
Appendix
How to Use This Book?
Introduction to Algorithms and Complexity
Cheat Sheet
Index
Advanced Tree Algorithms
Problems
Change Language (Farsi)
Source
Advanced Tree Algorithms
¶
Minimum Spanning Tree
Problem Description
Algorithms
Kruskal
Prim
Sack
Application
Algorithm
Implementation
Centroid
Definition
Proof of Existence and Finding the Centroid
Centroid Decomposition
Centroid Tree
Huffman Coding
Character to 0,1 Correspondence
An Optimal Tree
Tree Hashing
Conversion to Equality of Two Rooted Trees
Solving the Equality Problem for Two Rooted Trees
Computing the Hash of a Rooted Tree
Heavy-Light Decomposition (HLD)
Definition
Decomposition Algorithm
Proof of Correctness
Algorithm Implementation
Previous
Next