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\'{e} $H=(\mathcal{V},\mathcal{E})$, qu'on appelle aussi un dihypergraphe. Chaque sommet $v\in{\mathcal{V}}$ est reli\'{e} \'{a} des hyperarcs dans $\mathcal{E}$. R\'{e}ciproquement, chaque hyperarc $E\in{\mathcal{E}}$ est reli\'{e} \'{a} des sommets dans $\mathcal{V}$. $H$ est Eul\'{e}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\^{e}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\'{e}mes sont NP-complets. Des conditions n\'{e}cessaires pour qu'un hypergraphe orient\'{e} soit Eul\'{e}rien sont pr\'{e}sent\'{e}es. Nous exhibons des familles d'hypergraphes pour lesquelles elles sont suffisantes. Nous g\'{e}n\'{e}ralisons aussi certaines propri\'{e}t\'{e}s des graphes orient\'{e}s Eul\'{e}riens aux hypergraphes orient\'{e}s uniformes et r\'{e}guliers. D'autres g\'{e}n\'{e}ralisations plus fortes de l'\textit{Eulerianicit\'{e}} aux dihypergraphes sont aussi \'{e}tudi\'{e}es. Enfin nous montrons que les hypergraphes de de Bruijn et de Kautz sont Eul\'{e}riens et Hamiltoniens dans la plupart des cas. Nous \'{e}tudions \'{e}galement certaines propri\'{e}t\'{e}s de leur repr\'{e}sentation bipartie.
Origine : Fichiers produits par l'(les) auteur(s)