نظریه گرافها برای المپیاد کامپیوتر
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
NP and NP-complete Problems
Problems
Change Language (Farsi)
Source
NP and NP-complete Problems
¶
NP and NP-complete Definitions
Decision Problems
Class P
Class NP
Verifier
Definition
Example
Polynomial Time Reduction
NP-hard and NP-complete Problems
P=NP
Proof of NP-Completeness of the SAT Problem
Definitions of Problems
Proof of NP-Completeness of Circuit-SAT
Reduction from Circuit-SAT to SAT
Graph NP-Complete Problems
Maximum Independent Set
Graph Clique and Minimum Vertex Cover
Chromatic Number
Hamiltonian Path
Hamiltonian Cycle
Longest Path and Cycle
Previous
Next