PATAUT: Sommet-connexité dans les graphes

De Ensiwiki
Aller à : navigation, rechercher

Texte gras

Sommet-connexité dans les graphes

Labo G-Scop
Equipe Optimisation Combinatoire
Encadrants zoltan.szigeti@g-scop.inpg.fr

Etudiant

Guillaume PATAUT, filière MMIS


Introduction et Objectif

Mes travaux de ce module d'IRL s'inscrivent autour de la notion de connexité de la théorie des graphes, et plus particulièrement, la notion de 2-sommet-connexité. À partir des graphes orientés et non-orientés, le but de mes recherches a été de trouver une caractérisation constructive des graphes orientés 2-sommet-connexes.

Élément de prérequis

Définitions générales

Un graphe G=(V,E) non orienté est caractérisé par un ensemble de sommets V, et un ensemble d'arêtes E qui sont des liaisons entre les sommets. Par exemple, le réseau de tram de Grenoble peut être représenté par un graphe non orienté où les stations seraient les sommets et les rails entre les stations représenteraient les arêtes. La figure qui suit est un autre exemple de graphe non orienté.

Graphe non orienté à 4 sommets

Un graphe D=(V,A) orienté est caractérisé par un ensemble de sommets V, et un ensemble d'arcs A qui ne représentent, en quelque sorte, qu'une simple orientation des arêtes. Par exemple, le réseau électrique de GEG ou d'EDF peut être représenté par un graphe orienté puisque l'électricité ne va que dans le sens de l'usine de fabrication vers les consommateurs. La figure qui suit reprend le même exemple que précédemment mais en orientant les arêtes pour qu'elles deviennent des arcs.

Graphe orienté à 4 sommets

Connexité

Un graphe G=(V,E) non orienté est k-arête-connexe si et seulement si \forall X \subsetneq V, d(X) \ge k, où  d(X) représente le nombre d'arêtes entre  X et  V \backslash X .

Graphe non orienté 2-arête-connexe

Un graphe D=(V,A) orienté est k-arc-connexe si et seulement si \forall X \subsetneq V, d^{+}(X) \ge k, où  d^{+}(X) représente le nombre d'arcs sortants de l'ensemble  X .

Graphe orienté 2-arc-connexe

Un graphe D=(V,A) orienté est k-sommet-connexe si et seulement si le graphe reste fortement connexe, c'est-à-dire 1-arc-connexe, quand on lui ôte k-1 sommets.

Graphe orienté complet à 3 sommets qui est 2-sommet-connexe

Théorème de Lovasz [1]

Soit G un graphe non orienté. G est 2k-arête-connexe si et seulement si on peut le construire à partir d'un sommet et des 2 opérations :

- Ajout d'une arête entre 2 sommets existants (ces 2 sommets peuvent être identiques)

- Pincement de k arêtes

Pincement de 2 arêtes

Ce théorème nous donne un caractérisation constructive des graphes non orientés 2k-arête-connexes.

Théorème de Mader [2]

Soit D un graphe orienté. D est k-arc-connexe si et seulement si on peut le construire à partir d'un sommet et des 2 opérations :

- Ajout d'une arc entre 2 sommets existants (ces 2 sommets peuvent être identiques)

- Pincement de k arcs

Pincement de 2 arcs

Ce théorème nous donne, quant à lui, une caractérisation constructive des graphes orientés 2-arc-connexes.

Travail Réalisé

À partir de ces résultats et ceux d'autres chercheurs, nous avons voulu trouver une caractérisation constructive des graphes orientés 2-sommet-connexes dans le même type que les caractérisations constructives précédentes.

Conjecture

Nous avons donc émis la conjecture suivante :

Soit D un graphe orienté. D est 2-sommet-connexe si et seulement si on peut le construire à partir du graphe complet à 3 sommets, noté K_{3}^{2}, et des 2 opérations :

- Ajout d'un arc entre 2 sommets existants (ces 2 sommets peuvent être identiques)

- Pincement de 2 arcs uv et xyD' \backslash (\{uv\} \cup \{xy\}) reste fortement connexe.

Théorème

Le but a été ensuite de prouver cette conjecture. Après plusieurs tentatives qui ont échouées, nous avons tentés de démontrer cette conjecture pour un certain type de graphe orienté.

Soit D un graphe orienté. D est un (2,2)-graphe si pour chaque sommet, le nombre d'arcs entrant vaut 2 et le nombre d'arcs sortants vaut 2.

Exemple de (2,2)-graphe

Le théorème que nous avons émis dit que notre conjecture est vraie pour les (2,2)-graphes.

Soit D un (2,2)-graphe. D est 2-sommet-connexe si et seulement si on peut le construire à partir du graphe complet à 3 sommets, noté K_{3}^{2}, et du pincement de 2 arcs uv et xyD' \backslash (\{uv\} \cup \{xy\}) reste fortement connexe.

Idée générale de la démonstration

Pour démontrer ce théorème, on va partir du graphe D et on va prouver qu'on peut se réduire au graphe orienté complet à 3 sommets par l'opération inverse du pincement, appelée splitting-off complet.

Pour un pincement de 2 arcs donné, il existe 2 splitting-off complets possibles.

Premier splitting-off complet possible
Second splitting-off complet possible

Lemme 1

Un splitting-off complet sonné sur un sommet s ne conserve pas la propriété de 2-sommet-connexité si et seulement si il existe un des 2 obstacles suivants :

Obstacle de type 1
Obstacle de type 2

Ici, le splitting-off donné sur le sommet s est celui avec lequel on obtiendra les arcs xy et uv (ou wv).

Lemme 2

Il n'existe aucun splitting-off complet sur un sommet s qui conserve la propriété de 2-sommet-connexité si et seulement si il existe une des 2 configurations suivantes :

Configuration entrante
Configuration sortante

Les 2 configurations sont quasiment identiques, seule l'orientation des arcs est inversées. Les indices des ensembles et des sommets correspondent au type des obstacles. Ainsi, Z_1 et w_1 sont liés à un obstacle de type 1, Z_2 et w_2 sont liés à un obstacle de type 2 et Z_3 représente le reste des sommets qui ne sont pas dans Z_1 \cup Z_2.

Lemme 3

S'il existe une configuration en un sommet s, alors on peut réaliser un splitting-off complet sur le sommet w_2 qui conserve la propriété de 2-sommet-connexité.

Conclusion

Ce cours d'IRL m'a permis de m'ouvrir sur le monde de la recherche avec toute sa complexité et ses frustrations lorsqu'on ne trouve pas de résultats. Cependant, elle m'a aussi permis de penser d'une autre façon et m'a donné la capacité de parler d'un sujet spécialisé dans un domaine à des personnes qui ne le sont pas.

De plus, durant ces semaines, nous avons pu avec mon encadrant émettre une conjecture et prouver cette conjecture dans un cas particulier, ce qui reste un résultat probant et une avancée, toutefois légère, dans le domaine de la théorie des graphes.

Pour finir, nous pouvons aussi reprendre le travail effectué et essayer de l'étendre en tentant de prouver que la conjecture est vraie pour les (k,k)-graphes (qui sont définis de la même manière que les (2,2)-graphes) ou en montrant un contre-exemple.

Références

[1] L. Lovasz. Combinatorial Problems and Exercises. North-Holland, 1979.

[2] W. Mader. Konstruktion aller n-fach kantenzusammenhängenden digraphen. Europ. Journal of Combinatorics, 3 :63–67, 1982.

Documents additionnels

Fichier:Rapport IRL Guillaume Pataut.pdf

Fichier:Soutenance IRL Guillaume Pataut.pdf