Vivien Vandaele : Orientation des graphes avec contrainte sur les degrés entrants : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
Ligne 97 : Ligne 97 :
 
== Annexe ==
 
== Annexe ==
 
[[Fichier:Rapport_IRL_Vivien_Vandaele.pdf]]
 
[[Fichier:Rapport_IRL_Vivien_Vandaele.pdf]]
 +
[[Fichier:Soutenance_IRL_Vivien_Vandaele.pdf]]

Version du 22 mai 2019 à 23:32

Cornues.png
Titre du projet Orientation des graphes avec contrainte sur les degrés entrants
Cadre IRL

Labo G-SCOP

Encadrants Zoltán Szigeti

Introduction

Durant ce module, j'ai travaillé sur un problème d'orientation de graphe avec uniquement deux degrés entrants, notés a et b. Pour ce problème d'orientation, nous pouvons formuler deux conditions nécessaires.
Soit s le nombre de sommets de degré entrant a et t le nombre de sommets de degré entrant b. Alors les conditions nécessaires sont les suivantes :

  • s+t=|V| avec |V| le nombre de sommets du graphe.
  • as+bt=|E| avec |E| le nombre d'arêtes du graphe.

Le but est de savoir si ces conditions nécessaires sont également suffisantes pour certaines familles de graphes.


Élément de prérequis

Définitions

  • On note G=(V,E) un graphe non orienté, avec V l’ensemble de ses sommets et E l’ensemble de ses arêtes.
  • L’orientation d’un graphe non orienté consiste à assigner une direction à chacune de ses arêtes, on obtient alors un graphe orienté.
  • Un graphe G=(U,V;E) est dit biparti si on peut partager son ensemble de sommets en deux sous-ensembles U et V tels que chaque arête ait une extrémité dans U et l’autre dans V.
  • Un graphe non orienté est connexe si \forall X \subsetneq V, d(X) >= 1 avec d(X) le nombre d’arêtes incidentes à un sommet appartenant à X et à un sommet n’appartenant pas à X.
  • Un graphe connexe est dit k-arête-connexe s’il est encore connexe après avoir supprimé k-1 arêtes quelconques.

Travail Réalisé

Cas des graphes bipartis k-réguliers connexes

Résolution du problème pour les graphes bipartis 3-réguliers connexes

Pour les graphes bipartis 3-réguliers connexes, nous avons démontré le théorème suivant.

Soit G=(V,E) un graphe non orienté biparti 3-régulier connexe, a et b deux entiers tels que 0 <= a, b <= 3, et s et t deux entiers tels que s+t=|V| et as+bt=|E|. Alors il existe une orientation de G telle que s sommets de G sont de degré entrant a et t sommets de G sont de degré entrant b.

Contre-exemple pour tout k > 3

On construit un graphe biparti k-régulier connexe possédant 2(k-1) sommets et dont chaque sommet est incident à une arête multiple de cardinalité k-1.
Le graphe construit est un contre-exemple car l'orientation n'est pas réalisable pour a = 0 et b=k-1.
L'idée principale est que deux sommets reliés par une arête multiple de cardinalité k-1 ne peuvent pas être tous les deux de degré entrant 0 ni tous les deux de degré entrant k-1.

  • Contre exemple pour k = 4
  • Contre exemple pour k = 5


Cas des graphes bipartis k-réguliers connexes simples

Pour les graphes bipartis k-réguliers connexes simples, nous pouvons simplement trouver un contre-exemple pour tout k > 3 en remplaçant les arêtes multiples des contre-exemples précédents par un graphe simple.

Contre exemple pour k = 4

Cas des graphes bipartis k-réguliers k-arêtes-connexes

Dans le graphe ci-dessous, l'orientation avec a=0 et b=3 n'est pas réalisable.

Contre exemple d'un graphe biparti 4-régulier 4-arête-connexe

Nous pouvons construire un contre-exemple pour tout k >= 6. La procédure de construction est bien évidemment détaillée dans le rapport, celle-ci diffère légérement lorsque k est pair ou impair.
Voici un exemple pour k=6 et k=7.

  • Contre exemple d'un graphe biparti 6-régulier 6-arête-connexe
  • Contre exemple d'un graphe biparti 7-régulier 7-arête-connexe

Notons que nous n'avons pas de contre-exemple pour les graphes bipartis 5-réguliers 5-arêtes-connexes.

Cas des graphes bipartis k-réguliers k-arêtes-connexes simples

Pour les graphes bipartis k-réguliers k-arêtes-connexes simples, nous pouvons simplement trouver un contre-exemple pour tout k > 3 et k pair en remplaçant les arêtes multiples des contre-exemples précédents par un graphe simple.

Graphes pouvant remplacer une arête multiple de cardinalité 2 et 3 respectivement.

Notons que cela ne fonctionne pas lorsque k est impair car le graphe produit ne serait pas k-arête-connexe.

Conclusion

En résumé, nous avons des contre-exemples pour les graphes suivants :

  • Les graphes bipartis k-réguliers connexes avec k >= 4.
  • Les graphes bipartis k-réguliers connexes simples avec k >= 4.
  • Les graphes bipartis k-réguliers k-arêtes-connexes lorsque k = 4 et k >= 6.
  • Les graphes bipartis k-réguliers k-arêtes-connexes simples avec k >= 4 et k pair.

De plus, nous avons aussi démontré que conditions nécessaires sont également suffisantes pour les graphes bipartis 3-réguliers connexes.


Références

[1] Joe Buhler, Steve Butler, Ron Graham, and Eric Tressler. Hypercube orien-tations with only two in-degrees. Journal of Combinatorial Theory, Series A, pages 1695 – 1702, 2011.

[2] S.L. Hakimi. On the degrees of the vertices of a directed graph. J. Franklin Inst. 279 (4), pages 290 – 308, 1965.

[3] M.D. Plummer and L. Lovász. Matching theory. North-Holland, 1985.


Annexe

Fichier:Rapport IRL Vivien Vandaele.pdf Fichier:Soutenance IRL Vivien Vandaele.pdf