Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Hamiltonian decomposition
Résumé
In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs.
In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.
For a Hamiltonian decomposition to exist in an undirected graph, the graph must be connected and regular of even degree.
A directed graph with such a decomposition must be strongly connected and all vertices must have the same in-degree and out-degree as each other, but this degree does not need to be even.
Every complete graph with an odd number of vertices has a Hamiltonian decomposition. This result, which is a special case of the Oberwolfach problem of decomposing complete graphs into isomorphic 2-factors, was attributed to Walecki by Édouard Lucas in 1892.
Walecki's construction places of the vertices into a regular polygon, and covers the complete graph in this subset of vertices with Hamiltonian paths that zigzag across the polygon, with each path rotated from each other path by a multiple of .
The paths can then all be completed to Hamiltonian cycles by connecting their ends through the remaining vertex.
Expanding a vertex of a -regular graph into a clique of vertices, one for each endpoint of an edge at the replaced vertex, cannot change whether the graph has a Hamiltonian decomposition. The reverse of this expansion process, collapsing a clique to a single vertex, will transform any Hamiltonian decomposition in the larger graph into a Hamiltonian decomposition in the original graph. Conversely, Walecki's construction can be applied to the clique to expand any Hamiltonian decomposition of the smaller graph into a Hamiltonian decomposition of the expanded graph.
One kind of analogue of a complete graph, in the case of directed graphs, is a tournament.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.