نظریه گرافها برای المپیاد کامپیوتر
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
Trees
Problems
Change Language (Farsi)
Source
Trees
¶
Introductory Properties
Definitions in this Section
Theorems and Lemmas Used in this Section
Lemma 2.1.1
Theorem 2.1.2
Theorem 2.1.3
Theorem 2.1.4
Theorem 2.1.5
Theorem 2.1.6
Rooting a Tree
Distance in Tree and Graph
What is Distance?
Diameter
Eccentricity
Theorem 2.2.1
Radius and Center
Theorem 2.2.2
Centroid
Theorem 2.2.3
Sum of Distances
Minimizing Graph Density
Maximizing Graph Density
Support Tree
Partitioning a Tree into Paths
Covering Tree Edges with Paths
Tree Embedding
Counting the Number of Trees
Counting with Degree Sequence
Hint
Solution
Prüfer Code
Hint
Solution
Correspondence to Functional Graph
Hint
Solution
Counting Arborescences
Hint
Solution
DFS
First Problem
Connected Components
DFS Tree
Maximal Path and DFS
Path of length
\(\delta\)
Path of length
\(\frac m n\)
Leaves and Height, Independent Set and Longest Path!
Non-articulation point
Tree Traversal
BFS
BFS Algorithm
BFS Tree
BFS Code
Conclusion
Algorithm for Finding Tree Diameter
Using DP
DFS Up/Down
A Simpler Algorithm
DFS Start/Finish Time
Checking Ancestor/Descendant Relationship in Linear Time
Solution
Finding the k-th Parent
Solution
Blood Cousins
Solution
Biconnecting with Minimum Number of Paths
Solution
Cut Vertex and Bridge Algorithms
Finding Bridges
Finding Cut Vertices
Idea Cultivation Workshop
Square Eraser
Solution
Edge Labeling
Solution
Leaves
Solution
Note
BFS Magic
Solution
Previous
Next