Eulerian and Hamiltonian Directed Hypergraphs
Résumé
Let $H=(\mathcal{V},\mathcal{E})$ be a directed hypergraph, sometimes called a dihypergraph. Each vertex $v\in{\mathcal{V}}$ is incident to some hyperarcs in $\mathcal{E}$. Conversely, each hyperarc $E\in{\mathcal{E}}$ is incident to some vertices in $\mathcal{V}$. $H$ is Eulerian if there is a circuit $C$ such that each hyperarc $E\in{\mathcal{E}}$ appears exactly once in $C$. Similarly, $H$ is Hamiltonian if there is a circuit $C^{'}$ such that every vertex $v\in{\mathcal{V}}$ appears exactly once in $C^{'}$. We show that both of the problems are NP-complete. Some necessary conditions for a dihypergraph to be Eulerian are presented. We exhibit some families of hypergraphs for which those are sufficient conditions. We also generalize a part of the properties of the Eulerian digraphs to the uniform and regular directed hypergraphs. Stronger generalizations of \textit{Eulerianicity} to dihypergraphs are also studied. Finally, we show that the de Bruijn and Kautz dihypergraphs are Eulerian and Hamiltonian in most cases. We also study some properties of their bipartite representation digraph.
Soit un hypergraphe orienté $H=(\mathcal{V},\mathcal{E})$, qu'on appelle aussi un dihypergraphe. Chaque sommet $v\in{\mathcal{V}}$ est relié à des hyperarcs dans $\mathcal{E}$. Réciproquement, chaque hyperarc $E\in{\mathcal{E}}$ est relié à des sommets dans $\mathcal{V}$. $H$ est Eulérien s'il existe un circuit $C$ tel que chaque hyperarc $E\in{\mathcal{E}}$ n'apparaisse qu'une et une seule fois dans $C$. De même $H$ est Hamiltonien s'il existe un circuit $C^{'}$ tel que chaque sommet $v\in{\mathcal{V}}$ n'apparaisse qu'une et une seule fois dans $C^{'}$. Nous montrons que ces deux problèmes sont NP-complets. Des conditions nécessaires pour qu'un hypergraphe orienté soit Eulérien sont présentées. Nous exhibons des familles d'hypergraphes pour lesquelles elles sont suffisantes. Nous généralisons aussi certaines propriétés des graphes orientés Eulériens aux hypergraphes orientés uniformes et réguliers. D'autres généralisations plus fortes de l'Eulerianicité aux dihypergraphes sont aussi étudiées. Enfin nous montrons que les hypergraphes de de Bruijn et de Kautz sont Eulériens et Hamiltoniens dans la plupart des cas. Nous éudions également certaines propriétés de leur représentation bipartie.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...