Connectivity in graphs - Graph and graph theory: history, classification,

Это окончание невероятной информации про теория графов.

...

tree

Connectivity in graphs

• The connectivity relation, connected components
• The edge-biconnectivity relation
• The vertex-biconnectivity relation
• Articulation point, equivalent definitions
• Bridge, equivalent definitions
• Graph of edge-biconnected components
• Block-cut tree (block–articulation-point graph)
• k-connectivity
• Menger's theorem
• Menger's theorem, alternative proof
• Vertex connectivity, edge connectivity, the relationship between them and the minimum vertex degree
• The offline dynamic connectivity problem
• The dynamic connectivity problem

Spanning trees

Constructing spanning trees

• Spanning trees: definitions, the safe-edge lemma
• Prim's algorithm
• Kruskal's algorithm
• Borůvka's algorithm
• Tarjan's theorem (a criterion for the minimality of a spanning tree)
• The two-Chinese algorithm (Chu–Liu/Edmonds)
• Minimum bottleneck spanning tree
• Spanning tree in a planar graph
• Maximum number of pairwise edge-disjoint spanning trees in a graph with n vertices

Properties of spanning trees

• Kirchhoff matrix
• Relationship between the Kirchhoff matrix and the incidence matrix
• Counting the number of spanning trees using the Kirchhoff matrix
• Number of labeled trees
• Prüfer codes

Graph traversals

• Tutte's theorem on the existence of a regular graph of a given size with a given girth

Eulerian graphs

• Euler cycle, Euler path, Eulerian graphs, Eulerianity of digraphs
• Covering the edges of a graph by paths
• Algorithm for constructing an Euler cycle
• Graphs that can be arbitrarily traced from a given vertex
• De Bruijn graphs
• Euler tour trees

Hamiltonian graphs

• Hamiltonian graphs
• Chvátal's theorem
• Dirac's theorem
• Ore's theorem
• Pósa's theorem
• Ghouila-Houri's theorem
• Algorithm for finding a Hamiltonian cycle under the conditions of the Dirac and Ore theorems
• Grinberg's theorem
• Tournaments
• The Rédei–Camion theorem

Graph embeddings

• Embedding a graph in the plane
• Euler's formula
• Non-planarity of K5K5 and K3,3K3,3
• Embedding a tree
• Embedding a graph with planar edge-biconnected components
• Embedding a graph with planar vertex-biconnected components
• The Pontryagin–Kuratowski theorem
• Wagner's theorem
• Genus, thickness, coarseness, crossing number
• Dual graph of a planar graph
• Fáry's theorem
• The gamma algorithm
• Cut in planar graphs

Graph colorings

• Graph coloring
• Bipartite graphs and 2-coloring
• Chromatic polynomial
• Zykov's formula
• Whitney's formula
• Brooks' theorem
• Chromatic number of a planar graph
• Upper and lower bounds on the chromatic number
• The four color problem
• Tutte polynomial
• Ramsey theory
• Edge coloring of a bipartite graph
• Turán's theorem on the extremal graph
• Heawood conjecture

Depth-first search

• Depth-first search, vertex colors
• The white-path lemma
• Using depth-first search to check connectivity
• Using depth-first search to find a cycle
• Using depth-first search for topological sorting
• Using depth-first search to find strongly connected components
• Using depth-first search to find articulation points
• Constructing vertex-biconnected components
• Using depth-first search to find bridges
• Constructing edge-biconnected components

Shortest paths in graphs

• Breadth-first search
• The Bellman–Ford algorithm
• Dijkstra's algorithm
• Floyd's algorithm
• Johnson's algorithm
• Levit's algorithm
• The A* algorithm
• The D* algorithm
• Heuristics for finding shortest paths

The matching problem

• Matchings: basic definitions, the theorem on maximum matching and augmenting chains
• The Ford–Fulkerson algorithm for finding a maximum matching
• Kuhn's algorithm for finding a maximum matching
• Hall's theorem
• The relationship between maximum matching and minimum vertex cover in bipartite graphs
• The relationship between vertex cover and independent set
• Edge kernel
• The Tutte matrix and its relation to the size of a maximum matching in a bipartite graph
• Tutte's theorem on the existence of a perfect matching
• Matchings in non-bipartite graphs. The blossom-shrinking algorithm
• The Edmonds–Gallai decomposition
• Barriers minimal by inclusion in a graph
• The intersection of all maximal-by-inclusion barriers
• The stable matching problem
• Perfect matching in a cubic graph
• Theorem on the existence of a perfect matching in a graph obtained from a regular one by removing edges

The maximum flow problem

• Definition of a network, a flow
• Cut, the lemma on the flow through a cut
• Residual network, augmenting path
• Addition and difference of flows
• The Ford–Fulkerson theorem
• The Ford–Fulkerson algorithm, implementation using depth-first search
• The Edmonds–Karp algorithm
• The flow scaling algorithm
• Blocking flow
• Outline of Dinic's algorithm
• Karzanov's theorems on the number of iterations of Dinic's algorithm in a network with integer capacities
• The Goldberg–Tarjan algorithm
• Algorithm for finding a blocking flow in an acyclic network
• The push-relabel method (preflow push)
• The "relabel-to-front" algorithm
• The decomposition theorem
• The decomposition barrier theorem
• Circulation of flow
• The Stoer–Wagner algorithm for finding a minimum cut
• Karger's algorithm for finding a minimum cut
• Examples of reduction to flow-finding problems

The minimum-cost flow problem

• Minimum-cost flow
• The Ford–Fulkerson theorem on minimum-cost flow
• Lemma on the equivalence of a flow's property of being minimum-cost and the absence of negative cycles in the residual network
• Finding a minimum-cost flow by the method of augmenting along minimum-cost paths
• Using Johnson potentials when finding a minimum-cost flow
• Reduction of the assignment problem to the minimum-cost flow problem
• The Hungarian algorithm for solving the assignment problem
• The minimum-mean-weight cycle canceling algorithm

Random graphs

• Introduction: definitions, presence of triangles, connectivity, diameter two
• The giant component theorem. Breadth-first search in a random graph
• Theorem on the existence of a threshold for monotone properties

Продолжение:

Часть 1 Graph and graph theory: history, classification, description, applications
Часть 2 Connectivity in graphs - Graph and graph theory: history, classification,