Eulerian and Hamiltonian Directed Hypergraphs

Guillaume Ducoffe 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : 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.
Type de document :
Rapport
[Research Report] RR-7893, INRIA. 2012, pp.55
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00674655
Contributeur : Guillaume Ducoffe <>
Soumis le : vendredi 13 avril 2012 - 08:04:45
Dernière modification le : jeudi 11 janvier 2018 - 16:02:51
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 21:42:39

Fichier

euler01032011.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00674655, version 3

Collections

Citation

Guillaume Ducoffe. Eulerian and Hamiltonian Directed Hypergraphs. [Research Report] RR-7893, INRIA. 2012, pp.55. 〈hal-00674655v3〉

Partager

Métriques

Consultations de la notice

339

Téléchargements de fichiers

174