نظریه گرافها برای المپیاد کامپیوتر
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
Trees
Problems
Change Language
Source
Trees
¶
Basic Properties
Related Definitions in This Section
Theorems and Lemmas Used in This Section
Lemma 2.1.1
Theorem 2.1.3
Theorem 2.1.4
Theorem 2.1.5
Rooting a Tree
Distance in Trees and Graphs
What is Distance?
Diameter
Eccentricity
Theorem 2.2.1
Radius and Center
Theorem 2.2.2
Centroid
Theorem 2.2.3
Sum of Distances
Maximizing Graph Density
Support Tree
Covering Tree Edges with Paths
Tree Embedding
Counting the Number of Trees
Counting with Degree Sequences
Hint
Solution
Proof Code
Guidance
Solution
Guidance
Solution
Counting Branches
Guidance
Solution
DFS
First Problem
Connected Components
DFS Tree
Maximal Path and DFS
Non-Cut Vertex
Tree Traversal
BFS
BFS Algorithm
گراف و نمایش ماتریسی آن
ماتریس همسایگی (Adjacency Matrix)
نمایش ماتریس وقوع (Incidence Matrix)
مزایا و معایب
درختها
ویژگیهای درختها
درخت پوشا
Properties of Trees
Spanning Tree
Directed Graphs
Adjacency List Representation
Matrix Representation
Graph Properties
Undirected Graphs
Adjacency List Representation
Edge List Representation
Connected Components
Adjacency Matrix
Adjacency List
Edge List
Graph Representation
Adjacency Matrix
Adjacency List
نمایش گراف
ماتریس مجاورت (Adjacency Matrix)
لیست مجاورت (Adjacency List)
جدول یالها (Edge List)
مقایسه پیچیدگی زمانی
Depth-First Search (DFS)
Example Code
Iterative Implementation Using a Stack
الگوریتم جستجوی اول عمق (DFS)
تحلیل پیچیدگی:
Directed Graphs
Representation of Directed Graphs
Applications of Directed Graphs
الگوریتم جستجوی عمق اول (DFS)
مراحل اجرای الگوریتم
ویژگیهای الگوریتم DFS
مقایسه با BFS
Bipartite Graphs
Properties of Bipartite Graphs
Complete Bipartite Graphs
Applications
Spanning Trees
Trees
Rooted Tree
Traversal Algorithms
Spanning Tree
الگوریتم جستجوی اول سطح (BFS)
الگوریتم جستجوی عمق اول (DFS)
ماتریس مجاورت
لیست مجاورت
لیست یالها
BFS Tree
الگوریتم جستجوی اول سطح
BFS و DFS در یک گراف
BFS (جستجوی سطحی)
DFS (جستجوی عمقی)
مقایسه BFS و DFS
تعاریف گراف
Representing a Graph Using an Edge List
Representation Using Adjacency Matrix
گرافهای جهتدار
Introduction
Types of Graphs
Graph Representation
Adjacency Matrix
Adjacency List
Graph Traversal
Breadth-First Search (BFS)
Depth-First Search (DFS)
Important Algorithms
Dijkstra's Algorithm
BFS Code
Conclusion
Algorithm for Finding the Diameter of a Tree
Using DP
dfs up/down
A Simpler Algorithm
Checking Ancestor-Descendant Relationship in Linear Time
Solution
Finding the k-th Ancestor
Solution
Bi-connecting with Minimum Number of Paths
Answer
Solution
Vertex and Edge Cut Algorithms
Finding Bridge Edges
Finding Articulation Points
Idea Cultivation Workshop
Square Eraser
Solution
Leaves Leaves Leaves
Solution
The Magic of BFS
Solution
Previous
Next