infoarena

Se poate răspunde în complexitate polinomială dacă un graf este hamiltonian (fără a determina ciclul) ?

problema e np completa
mathworld.wolfram.com/HamiltonianGraph.html

Bondy–Chvátal theorem

The best vertex degree characterization of Hamiltonian graphs was given in 1972 by the Bondy–Chvátal theorem which generalizes earlier results by G. A. Dirac (1952) and Øystein Ore. In fact, both Dirac's and Ore's theorems are less powerful than what can be derived from Pósa's theorem (1962). Dirac and Ore's theorems basically state that a graph is Hamiltonian if it has enough edges. First we have to define the closure of a graph.
Given a graph G with n vertices, the closure cl(G) is uniquely constructed from G by successively adding for all nonadjacent pairs of vertices u and v with degree(v) + degree(u) ≥ n[clarification needed] the new edge uv.
Bondy–Chvátal theorem
A graph is Hamiltonian if and only if its closure is Hamiltonian.
As complete graphs are Hamiltonian, all graphs whose closure is complete are Hamiltonian, which is the content of the following earlier theorems by Dirac and Ore.
Dirac (1952)
A simple graph with n vertices (n ≥ 3) is Hamiltonian if each vertex has degree n/2 or greater.[1]
Ore (1960)
A graph with n vertices (n ≥ 3) is Hamiltonian if, for each pair of non-adjacent vertices, the sum of their degrees is n or greater (see Ore's theorem).
The following theorems can be regarded as directed versions:
Ghouila-Houiri (1960)
A strongly connected simple directed graph with n vertices is Hamiltonian if some vertex has a full degree smaller than n.
Meyniel (1973)
A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of some two distinct non-adjacent vertices is smaller than 2n − 1.
The number of vertices must be doubled because each undirected edge corresponds to two directed arcs and thus the degree of a vertex in the directed graph is twice the degree in the undirected graph.


Mai mult de atat nu cred ca gasesti.