نظریه گرافها برای المپیاد کامپیوتر
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
Directed Graph
Problems
Change Language (Farsi)
Source
Directed Graph
¶
Definitions
Definition 3.1.1 (Directed Graph)
Degree in a Directed Graph
Cycles and Paths in a Directed Graph
Theorems and Lemmas Used in This Section
Theorem 3.1.2
Theorem 3.1.3
Theorem 3.1.4
A Few More Definitions
Tournament
Definition 3.2.1 (Tournament)
Kings in Tournaments
Definition 3.2.2 (King)
Theorem 3.2.3
Hamiltonian Paths in Tournaments
Definition 3.2.4 (Hamiltonian Path in a Directed Graph)
Theorem 3.2.5
Directed Acyclic Graph
Definition 3.3.1 (DAG)
An Important Property
Theorem 3.3.2
Topological Sort
Topological Sort Algorithm
Proof of Correctness
Algorithm Complexity
Algorithm Implementation
Strongly Connected Components
Basic Concepts
Definition 3.4.1 (Strongly Connected Pair of Vertices)
Definition 3.4.2 (Strongly Connected Graph)
Definition 3.4.3 (Strongly Connected Component, or SCC)
Lemma 3.4.4
Corollary 3.4.5
Definition 3.4.6 (Transpose Graph)
Acyclicity of the Strongly Connected Component Graph
Definition 3.4.7 (Condensed Graph of Strongly Connected Components)
Theorem 3.4.8
Corollary 3.4.9
Finding Strongly Connected Components
Kosaraju's Algorithm
Algorithm Complexity
Lemma 3.4.10
Algorithm Implementation
Detecting Cycles in a Directed Graph
Introduction
Cycle Detection Algorithm Using DFS
Algorithm Complexity
Algorithm Implementation
Kahn's Algorithm
Algorithm Complexity
Algorithm Implementation
Games and Directed Graphs
Introduction
Examining an Example
Result
Moving a Piece on a Graph Game
Generalization
Solving the Game on a Graph
Some Useful Conclusions
Final Word
Functional Graphs and Permutation Graphs
Definition 3.7.1 (Permutation Graph)
Theorem 3.7.2
Theorem 3.7.3
Previous
Next