نظریه گرافها برای المپیاد کامپیوتر
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
Matching
Problems
Change Language
Source
Matching
¶
Introduction
Code Example
Definition
Vertex and Edge Covers
Matchings in Bipartite Graphs
Algorithm
Hall's Theorem
Matching in k-Regular Bipartite Graphs
Generalization of Hall's Theorem
Minimax Theorems
Theorems Valid in Every Graph
Handshaking Lemma
Euler's Theorem
\(\beta \geq \alpha^{\prime}\)
Theorems Holding in Bipartite Graphs
\(\beta^{\prime} = \alpha\)
Applications
Decomposition of DAG into Paths
Partitioning a Directed Graph into Cycles
2k-Regular Graph and Decomposition into Cycles
Tournament Degree Sequence and Matching
Fixed Vertices in Bipartite Matching
Finding a Minimum Vertex Cover in a Bipartite Graph
Maximum Flow and Matching
Solving the Maximum Matching Problem in Bipartite Graphs
Maximum Weight Matching
Flow with Minimum Cost
Solution
Proof of Optimality
Complexity Analysis
Maximum Weight Matching Solution
Poset
Definition
The First Problem
Chain and Antichain
Maximum Chain = Minimum Partition into Antichains
Maximum Antichain = Minimum Partition into Chains
Augmenting-like Path
Algorithm
No Path is Completely Removed
Matchings in General Graphs
Tutte's Theorem
If edges
\(ad\)
and
\(bc\)
lie in distinct cycles
If Edges
\(ad\)
and
\(bc\)
Are in a Cycle
If We Don't Have a Pear?
The More Generalized Case of Matching or k-factor
A Flawed Idea
Correct Solution
Previous
Next