Admin CliCours
Densité, VC-dimension et étiquetages de 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) ∈ V 2 ,(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). Figure 1.1 – De gauche à droite : Un K4, un K3,2, un C5, un W4, un arbre (de hauteur 3), un P3, une étoile K1,6 et une chenille.
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)}. 19 Chapitre 1 Notions de théorie des graphes 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. Un sous-graphe H de G (ou l’ensemble de sommet V (H)) est porté si, pour tout choix d’un sommet u ∈ V (G), il existe un sommet u 0 ∈ V (H) tel que, pour tout v ∈ V (H), dG(u, v) = dG(u, u0 ) + dG(u 0 , v). Ce sommet u 0 est alors nommé une porte de u sur H. De par sa définition, il est facile de remarquer qu’une porte doit être unique. Les différentes notions de sous-graphes sont illustrées dans la figure 1.2. Remarquons que H est porté si et seulement si l’empreinte de tout sommet u /∈ V (H) sur H contient un unique élément. D’après cela, nous dirons qu’un graphe H (ou un ensemble V (H)) est k-porté si chaque sommet hors de H possède au plus k empreintes sur H (c.-à-d., ∀u /∈ V (H), |Υ(u, V (H))| ≤ k). En particulier, nous dirons que H est quasi-porté si |Υ(u, V (H))| ≤ 2 pour tout u /∈ V (H). Précisons que cette notion nous sera essentiellement utile dans la partie III.
Résumé |
