نظریه گرافها برای المپیاد کامپیوتر
Basic definitions
Introduction and Modeling with Graphs
Types of Graphs
Graph Implementation
Walk, Trail, Path, Extremal
Subgraphs
Connectivity, Cut Edge, and Cut Vertex
Bipartite Graph
Trees
Basic Properties
Distance in Trees and Graphs
Counting the Number of Trees
DFS
BFS
گراف و نمایش ماتریسی آن
Directed Graphs
Undirected Graphs
Adjacency Matrix
Adjacency List
Edge List
Graph Representation
نمایش گراف
Depth-First Search (DFS)
الگوریتم جستجوی اول عمق (DFS)
Directed Graphs
الگوریتم جستجوی عمق اول (DFS)
Bipartite Graphs
Spanning Trees
Trees
الگوریتم جستجوی اول سطح (BFS)
ماتریس مجاورت
لیست مجاورت
لیست یالها
الگوریتم جستجوی اول سطح
BFS و DFS در یک گراف
تعاریف گراف
Representing a Graph Using an Edge List
گرافهای جهتدار
Introduction
Graph Representation
Graph Traversal
Important Algorithms
Algorithm for Finding the Diameter of a Tree
Checking Ancestor-Descendant Relationship in Linear Time
Finding the k-th Ancestor
Bi-connecting with Minimum Number of Paths
Vertex and Edge Cut Algorithms
Idea Cultivation Workshop
Directed graph
Definitions
Tournament
Directed Acyclic Graph (DAG)
Strongly Connected Components
Detecting Cycles in Directed Graphs
Games and Directed Graphs
Functional Graphs and Permutation Graphs
Proof technics in graph problems
Extremal Choices
Contraction
Graphs and Magic
Euler circuit 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
Matrix
Matrices and Operations on Them
Kirchhoff's Theorem
Incidence Matrix
Adjacency Matrix
Number of Walks of Length n
Deriving Recursive Functions Using Graphs and Matrices
Tree data structures
Binary Tree
Binary Search Tree (BST)
Heap
DSU
Segment Tree
Search (Search)
Insertion (Insertion)
Applications
NP and NP-complete problems
Definition of NP and NP-Completeness
Problem Definitions
Reducing the circuit-sat Problem to sat
NP-Complete Graph Problems
LCA
Problem Statement
An O(n + q*lg(n)) Solution Using Heavy-Light Decomposition
Tarjan's Offline Algorithm
The Relationship Between LCA and RMQ
A Linear Approach to LCA
Virtual Tree
Advanced tree algorithms
Minimum Spanning Tree
Guni
Centroid
Huffman Coding
Tree Hash
Heavy-Light Decomposition (HLD)
Connectivity
Cuts and Connectivity
k-Connected Graph
Minimum Cut and Maximum Flow
Matching
Introduction
Matchings in Bipartite Graphs
Minimax Theorems
Applications
Maximum Flow and Matching
Poset
Matchings in General Graphs
Extra topics
Drawing a Planar Graph on a Sphere
Euler's Theorem
Dual Graph
Degree Sequence
Coloring
Isomorphism
Random Walk
Ramsey Numbers
Independent Set and Clique
مکمل گراف
2-SAT
Some Special Matrices
Appendix
چگونه از این کتاب استفاده کنیم؟
آشنایی با الگوریتم ها و پیچیدگی
برگه تقلب (Cheat sheet)
Index
Directed graph
Problems
Change Language
Source
Directed graph
¶
Definitions
Definition 3.1.1 (Directed Graph)
درجه در گراف جهت دار
Degree in Directed Graphs
Cycles and Paths in Directed Graphs
Theorems and Lemmas Used in This Section
Theorem 3.1.2
Theorem 3.1.3
Theorem 3.1.4
A Few More Definitions
Tournament
Adjacency Matrix of a Tournament
Generating Random Tournament
Definition 3.2.1 (Tournament)
The King in Tournaments
Definition 3.2.2 (King)
Theorem 3.2.3
Definition 3.2.4 (Hamiltonian Path in a Directed Graph)
Theorem 3.2.5
Directed Acyclic Graph (DAG)
Definition 3.3.1 (DAG)
Theorem 3.3.2
Topological Sorting
Algorithm
Topological Sorting Algorithm
Algorithm Complexity
Strongly Connected Components
Basic Concepts
Definition 3.4.1 (Strongly Connected Vertex Pair)
Definition 3.4.2 (Strongly Connected Graph)
Definition 3.4.3 (Strongly Connected Component (SCC))
Lemma 3.4.4
Result 3.4.5
Definition 3.4.6 (Inverse Graph)
Definition 3.4.7 (Condensed Graph of Strongly Connected Components)
Theorem 3.4.8
Result 3.4.9
Finding Strongly Connected Components
Kosaraju's Algorithm
Algorithm Complexity
Lemma 3.4.10
Algorithm Implementation
Detecting Cycles in Directed Graphs
Introduction
Algorithm Complexity
Algorithm Implementation
Kahn's Algorithm (Kahn)
Algorithm Complexity
Algorithm Implementation
Games and Directed Graphs
Introduction
Examining an Example
Result
Token Movement Game on a Graph
Generalization
Solving the Game on a Graph
Some Useful Conclusions
Final Note
Functional Graphs and Permutation Graphs
Theorem 3.7.2
Theorem 3.7.3
Previous
Next