Notions de théorie des graphes

Les graphes sont un outil mathématique permettant de modéliser un grand nombre de problèmes. Ils consistent en un ensemble d’objets abstraits, que nous appelons des sommets (ou des nœuds), avec une relation sur ces objets, deux sommets pouvant être reliés ou non par une arête. L’étude de leurs propriétés structurelles ou métriques, de leurs représentations en mémoire, ou d’algorithmes permettant de résoudre les problèmes qu’ils modélisent mènent à autant de questions fondamentales et variées. Une partie des résultats de cette thèse sont initialement motivés par la construction de représentations (distribuées) de graphes. Cela nous a conduit à nous intéresser à des problèmes d’intérêt plus généraux tels que l’étude de bornes sur la densité de graphes, de la VC-dimension de familles d’ensembles, ou de propriétés métriques et structurelles.

Un schéma d’étiquetage est un procédé permettant de répartir la représentation d’un graphe sur ses sommets plutôt que d’avoir une représentation globale à laquelle chaque nœud doit avoir accès. Cette représentation distribuée doit permettre de répondre à une requête fixée à l’avance (adjacence, distance, routage, etc.) en n’utilisant que des informations locales, attribuées aux sommets sous la forme d’étiquettes binaires. Pour qu’une telle représentation soit pertinente, nous souhaitons généralement que les étiquettes attribuées soient courtes (c.-àd., poly logarithmique en la taille du graphe) et qu’elles puissent être décodées rapidement (c.-à-d., en temps constant en leur longueur). Sous ces conditions, KANNAN, NAOR et RUDICH [106] ont montré que tous les graphes ne peuvent pas être représentés de façon distribuée de manière efficace. Ainsi, une première étape lorsque nous nous intéressons à des schémas d’étiquetage consiste à trouver une famille suffisamment restreinte pour en faire un “bon candidat” à une représentation distribuée.

Densité et arboricité 

Les premiers schémas d’étiquetage considérés portaient sur des requêtes d’adjacence puisque c’est, en quelque sorte, la requête minimale permettant de reconstruire le graphe [38, 106, 120]. Il se trouve que la majorité des schémas d’adjacence utilisent la notion de densité (c.-à-d., le ratio maximal du nombre d’arêtes sur le nombre de sommets pris sur tous les sous-graphes d’un graphe) via le concept d’arboricité (c.-à-d., nombre de forêts nécessaires pour couvrir toutes les arêtes d’un graphe). En effet, NASH-WILLIAMS [121] a montré qu’un graphe est de faible arboricité si et seulement s’il est de faible densité. De plus, KANNAN, NAOR et RUDICH [106] ont remarqué qu’une famille de graphes (avec n sommets) dont les arêtes peuvent être couvertes par k forêts possède un schéma d’adjacence avec étiquettes de (k + 1) dlog ne bits. Ces deux résultats considérés de concert établissent le lien entre densité et schéma d’adjacence. Ainsi, trouver une borne supérieure sur la densité d’un graphe permet directement de déduire une borne supérieure sur la longueur des étiquettes attribuées par un schéma d’adjacence.

Une famille de graphes peu denses ayant fait l’objet de nombreux travaux est celle des sous-graphes induits d’hypercubes (avec n sommets). Un résultat du folklore majore la densité de ces derniers par O(log n). En 1994, HAUSSLER, LITTLESTONE et WARMUTH [100] ont fourni une amélioration notoire de ce résultat en utilisant un paramètre nommé VC-dimension (introduit par VAPNIK et CHERVONENKIS [148]). Ils ont montré que la VC-dimension est une borne supérieure pour la densité d’un sous-graphe d’hypercube. Or, la VC-dimension est toujours inférieure (ou égale) à log n, et des exemples dans lesquels l’écart est arbitrairement grand sont faciles à construire.

L’introduction du concept de VC-dimension (et l’utilisation qui en est faite dans [100]) était motivé par la théorie de l’apprentissage et des probabilités, mais son intérêt s’est avéré bien plus général, notamment en géométrie algorithmique [102, 128] ou en théorie des graphes [36, 41]. L’un des premiers résultats utilisant ce paramètre est dû à SAUER [139], donnant une borne sur la taille d’une famille d’ensembles en fonction de sa VC-dimension. Il a donné lieu à l’introduction de familles d’ensembles maximums et, de façon plus indirecte, aux familles d’ensembles amples [33, 21, 113]. En particulier, les familles amples induisent des sous-graphes isométriques d’hypercubes. Elles généralisent aussi les graphes médians qui sont définis par de forte propriétés métriques, et qui sont centraux en théorie métrique des graphes. Des extensions du paramètre de VCdimension ou du lemme de Sauer constituent donc des problèmes intéressants, et fréquemment étudiés [1, 41, 101, 123, 133].

Schémas de distance et de routage 

Des schémas permettant de répondre à d’autres types de requêtes que la simple adjacence ont aussi été considérés, notamment des schémas de distance ou de routage [12, 53, 85, 131]. Mais la question de l’existence d’un adressage compact des sommets d’un graphe dans le but de calculer des distances exactes est un peu plus ancien. GRAHAM et POLLAK [92] posaient ce problème sous la forme de l’existence d’un plongement isométrique d’un graphe quelconque dans un “cube écrasé” (“squashed cube”) de la plus petit dimension possible. Un premier résultat impactant sur les schémas de distance est donc la réponse de WINKLER [151] à ce problème puisqu’il montre que les sommets d’un graphe connexe à n sommets peuvent être étiquetés par des mots de longueur n − 1 sur l’alphabet {0, 1, ∗} de sorte que la distance entre deux sommets soit la distance de Hamming entre leurs étiquettes. Ce résultat montre que tout graphe connexe à n sommets admet un schéma de distance avec des étiquettes de taille O(n). Comme pour les schémas d’adjacence, pour espérer obtenir des schémas de distance (ou de routage) poly logarithmiques, il faut considérer des familles de graphes ayant des fortes propriétés métriques. En fait, pour tous les types de requêtes, les arbres (ou forêts) constituent la classe de graphes la plus étudiée de par leur structure simple et bien connue, et leur prépondérance dans de nombreux domaines ou problèmes. Le premier schéma de distance (ou routage) efficace pour cette famille est dû à PELEG [131]. Il montre que les arbres avec n sommets admettent un schéma de distance utilisant des étiquettes de O(log2 n) bits, ce qui est asymptotiquement optimal [13, 85]. Ce résultat est obtenu en remarquant qu’un arbre avec n sommets admet toujours au moins un sommet dont la suppression crée des composantes connexes d’au plus n/2 sommets chacune. Plus généralement, un ensemble de sommets dont la suppression crée des composantes connexes de petite taille est un outil classique pour obtenir des schémas de distance (ou routage), appelé séparateur équilibré. Par exemple, les graphes planaires sur n sommets admettent un séparateur équilibré de O(√n) sommets et un schéma d’adjacence utilisant des étiquettes de O(√n log n) bits (et une borne inférieure de Ω(√3 n)). Une autre façon d’obtenir des schémas de distance ou de routage utilise la notion de “hub” [2, 63] : l’étiquette de chaque sommet u est un ensemble de sommets (les “hubs” de u) associés à leur distance à u ; chaque paire de sommet doit alors avoir un “hub” en commun.

Il existe aussi des version approchées de schémas d’étiquetage de distance ou de routage dans lesquelles la réponse à la requête est une approximation. Le décodage peut alors fournir une distance avec erreur additive et/ou multiplicative, ou diriger sur un chemin plus ou moins proche du plus court. Un résultat particulièrement important du domaine est dû à THORUP et ZWICK [146]. Il concerne des représentations compactes de graphes quelconques (pondérés) permettant de répondre à des requêtes de distance approchées (erreur multiplicative) en temps constant. THORUP [144] s’intéresse plus particulièrement à ce type de représentation pour les graphes planaires.

Notions de théorie des graphes 

Préliminaires de théorie des graphes

Un graphe (simple) G consiste en deux ensembles : un ensemble V de sommets et une relation E ⊆ V × V sur ces sommets, appelée ensemble des arêtes de G = (V, E). Lorsque la relation E est symétrique (c.-à-d., (∀(u, v) ∈ V2 ,(u, v) ∈ E ⇔ (v, u) ∈ E), G est dit non-orienté. Quand E est irréflexive (c.-à-d., ∀u ∈ V,(u, u) ∈/ E), G est dit sans boucles. Un graphe sur un ensemble de sommets fini est dit fini, sinon il est dit infini.

Remarque 1. Les graphes que nous considèrerons dans ce manuscrit seront simples, non-orientés, sans boucles et, la plupart du temps, finis.

Les arêtes (u, v) d’un graphe G = (V, E) sont généralement notées uv, et u et v sont appelés les extrémités de uv. Un graphe avec un unique sommet et aucune arête est dit trivial. Lorsqu’une arête uv est dans E, u est dit adjacent à v, ou que v est un voisin de u. Deux sommets u et v adjacents seront parfois notés u ∼ v. De même, nous pourrons noter u ≠ v le fait qu’ils ne soient pas adjacents. Le nombre de voisins d’un sommet u est appelé le degré de u et noté deg(u).

Un sous-graphe H = (V (H), E(H)) d’un graphe G = (V (G), E(G)) est un graphe constitué d’un sous-ensemble de sommets de G et sur lequel est considéré un sous ensemble des arêtes de G (c.-à-d., V (H) ⊆ V (G) et E(H) ⊆ E(G) ∩ (V (H) × V (H))).

Graphes et notations usuels

Nous présentons maintenant quelques graphes particuliers simples et fréquemment considérés. Nous introduisons leurs notations usuelles, nous les réutiliserons souvent par la suite. Ces graphes sont illustrés dans la figure 1.1. Un graphe complet (ou clique) de taille k, noté Kk, est un graphe composé de k sommets deux-à-deux adjacents. Un graphe G = (V, E) dont l’ensemble des sommets peut être partitionné en deux parties A et B de sorte que chaque arête de G ait une extrémité dans A et l’autre dans B est dit biparti. Plus généralement, G est k-parti si V peut être partitionné en k parties V1, . . . , Vk de sorte que, pour tout i ∈ {1, . . . , k}, pour tout (u, v) ∈ Vk × Vk, uv /∈ E. Dans ce cas, si toutes les arêtes autorisées par la k partition {V1, . . . , Vk} sont dans G, ce dernier est dit k-parti complet et noté K|V1|,…,|Vk| . Un chemin de longueur k est un graphe, noté Pk, avec k sommets v1, . . . , vk et dont les arêtes sont v1v2, . . . , vk−1vk. Si ce chemin est “fermé” par une arête vkv1, alors le graphe est appelé un cycle de longueur k et noté Ck. Si, pour tout couple (u, v) ∈ V × V d’un graphe G = (V, E), il existe un chemin (appelé (u, v)-chemin) reliant u à v dans G, ce dernier est dit connexe. Un cycle de longueur k auquel est ajouté un sommet relié à tous les autres est appelé une k-roue, notée Wk. Un graphe n’admettant aucun cycle est appelé une forêt (dans le cas général), ou un arbre s’il est connexe. Les sommets de degré 1 d’un arbre T sont appelés des feuilles. Il est bien souvent utile, dans les arbres, de distinguer un sommet que nous appelons racine. Nous regardons alors l’arbre du point de vue de ce sommet distingué r : la profondeur prof(v) d’un sommet v ∈ V (T) correspond au nombre d’arêtes sur le chemin (unique) entre v et r ; une branche de T est un chemin entre la racine et une feuille ; le parent de v est l’unique voisin père(v) de v à profondeur prof(v) − 1 (r n’a pas de parent) ; un fils u de v est un voisin de v à profondeur prof(v) + 1 (les feuilles n’ont pas de fils) ; un ancêtre u de v est un sommet sur une branche contenant v tel que prof(u) < prof(v). La hauteur d’un arbre est la profondeur maximum sur ses sommets. Remarquons qu’un chemin est un arbre avec au plus deux feuilles. Une étoile est un arbre de hauteur inférieure ou égale à 1. Une chenille est un chemin avec des nœuds pendants (c.-à-d., des étoiles reliées par un chemin).

Sous-graphes, distances et intervalles

Soit G = (V, E) un graphe (fini, simple, non-orienté et sans boucle). La distance dG(u, v) entre deux sommets u et v de G correspond au nombre d’arêtes minimal d’un (u, v)-chemin de G. Le diamètre diam(G) de G est la distance maximale entre deux de ses sommets (c.-à-d., diam(G) := max{dG(u, v) : (u, v) ∈ V 2}). Pour un sous-graphe H de G, la projection métrique Pr(u, V (H)) (ou simplement Pr(u, H)) de u sur V (H) (ou, disons, sur H) correspond à l’ensemble {v ∈ V (H) : ∀v 0 ∈ V (H), dG(u, v0 ) ≥ dG(u, v)} des sommets de H à distance minimum de u. Pour un sous-ensemble S ⊆ V de sommet d’un graphe G = (V, E), la boule de rayon r autour de S dans G, notée Br(S, G), est l’ensemble {v ∈ V : dG(v, S) ≤ r}. Lorsque le graphe G est évident d’après le contexte, la boule est simplement notée Br(S). Aussi, si S est un singleton {s}, Br({s}) est plutôt notée Br(s). L’intervalle I(u, v) entre u est v consiste en l’ensemble des sommets sur des (u, v)-chemins :

IG(u, v) := {x ∈ V : dG(u, x) + dG(x, v) = dG(u, v)}.

En l’absence d’ambiguïté sur le graphe considéré, nous noterons souvent I(u, v) et d(u, v) au lieu de IG(u, v) et dG(u, v), respectivement. Une empreinte d’un sommet u /∈ V (H) sur V (H) est un sommet v ∈ V (H) tel que I(u, v) ∩ V (H) = {v}. Autrement formulé, une empreinte de u /∈ V (H) sur H est un sommet v de H tel qu’aucun plus court chemin entre u et v n’ait de sommet interne dans H. Nous dénotons par Υ(u, V (H)) (ou Υ(u, H)) l’ensemble des empreintes de u sur V (H). Nous pouvons remarquer que, pour tout sommet u, Pr(u, H) ⊆ Υ(u, H).

Un graphe H est appelé un sous-graphe induit de G (noté H ⊆ G), si toutes les arêtes de G ayant leurs deux extrémités dans V (H) sont prises dans E(H) (c.- à-d., E(H) = E(G) ∩ (V (H) × V (H))). Pour un sous-ensemble S ⊆ V (G), nous dénoterons parfois par G(S) le sous-graphe de G induit par S (c.-à-d., le sousgraphe induit de G dont l’ensemble des sommets est S). La plupart du temps, les sous-graphes que nous considèrerons seront (au moins) induits et donc, si le contexte est clair, nous ne ferons bien souvent pas de différence entre un ensemble S et le graphe G(S) qu’il induit.

Un sous-graphe H de G est dit isométrique si la distance dans H entre toute paire de sommets de V (H) est la même que celle dans G (c.-à-d., ∀u, v ∈ V (H), dH(u, v) = dG(u, v)). Un sous-graphe H de G (ou l’ensemble de sommet V (H)) est convexe s’il inclue l’intervalle entre toute paire de ses sommets (c.-à-d., ∀u, v ∈ V (H), IG(u, v) ⊆ V (H)).

Remarque 2. Un sous-graphe convexe de G est isométrique, et un sous-graphe isométrique de G est lui-même induit.

Table des matières

Introduction générale
1 Notions de théorie des graphes
1.1 Préliminaires de théorie des graphes
1.1.1 Graphes et notations usuels
1.1.2 Sous-graphes, distances et intervalles
1.1.3 Voisinage, densité et notions connexes
1.1.4 Morphismes et plongements de graphes
1.2 Produits cartésiens de graphes
1.2.1 Hypercube comme produit cartésien
1.2.2 Graphes de Hamming
1.2.3 Classes de parallélisme et plongement dans l’hypercube
1.2.4 Facteurs premiers et irréductibles, plongement canonique
1.3 Graphes définis par des familles d’ensembles
1.3.1 Hypercube comme graphe d’une famille d’ensembles
1.3.2 Demi-cubes et graphes de Johnson
2 Dimension de Vapnik-Chervonenkis et densité
2.1 VC-dimension et apprentissage
2.2 Définitions
2.2.1 Lemme de Sauer et classes de concepts maximums
2.2.2 Classes de concepts amples et lemme du sandwich
2.3 Densité des graphes de 1-inclusion
2.4 Preuves classiques du théorème 8
2.4.1 Preuve par induction
2.4.2 Preuve par décalage
2.4.3 Preuve par compression
2.5 Généralisations et extensions de VC-dimension
3 Schémas d’étiquetage
3.1 Introduction
3.2 Schémas d’adjacence
3.2.1 Arboricité et densité
3.2.2 Graphes universels
3.3 Schémas de distance
3.3.1 Distances dans les arbres
3.4 Schémas de routage
3.4.1 Routage dans les arbres
4 Graphes faiblement modulaires
4.1 Graphes faiblements modulaires
4.2 Graphes médians
4.2.1 Graphes médians et complexes cubiques CAT(0)
4.2.2 Problèmes de distances dans les graphes médians et les complexes cubiques CAT(0)
4.3 Graphes pontés
4.3.1 Graphes pontés et complexes systoliques
4.4 Courbure et théorème de Gauss-Bonnet
Conclusion générale

Lire le rapport complet