Théorie des graphes

Un graphe avec trois sommets et trois arêtes.

Dans un sens restreint mais très répandu du terme[2]^,[3], un graphe est un couple G = (V, E) comprenant

• V un ensemble de sommets (aussi appelés nœuds, points ou vertex) ;
• E ⊆ {{x, y} | (x, y) ∈ V² ∧ x ≠ y} un ensemble d'arêtes (aussi appelées liens ou lignes), qui sont des paires de sommets (c.-à-d. qu'une arête est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un graphe simple non orienté.

Dans l'arête {x, y}, les sommets x et y sont appelés les extrémités ou les sommets extrêmes de l'arête. On dit que l'arête joint x et y et est incidente sur x et sur y. Un sommet peut exister dans un graphe sans arête incidente. Les arêtes multiples sont deux arêtes ou plus qui joignent les mêmes deux sommets ; elles ne peuvent pas exister dans un graphe simple non orienté.

Dans un sens plus général du terme autorisant les arêtes multiples[4]^,[5], un graphe est un triplet G = (V, E, ϕ) comprenant

• V un ensemble de sommets (aussi appelés nœuds, points ou vertex) ;
• E un ensemble d'arêtes (aussi appelés liens ou lignes) ;
• ϕ: E → {{x, y} | (x, y) ∈ V² ∧ x ≠ y} une fonction d'incidence associant à chaque arête une paire de sommets (c.-à-d. qu'une arête est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un multigraphe non orienté.

Une boucle est une arête qui joint un sommet à lui-même. Les graphes tels que définis dans les deux définitions précédentes ne peuvent pas avoir de boucles, car une boucle joignant un sommet x est l'arête (pour un graphe simple non orienté) ou est incidente sur (pour un multigraphe non orienté) {x, x} = {x} qui n'est pas dans {{x, y} | (x, y) ∈ V² ∧ x ≠ y}. Ainsi pour autoriser les boucles les définitions doivent être étendues. Pour les graphes simples non orientés, E ⊆ {{x, y} | (x, y) ∈ V² ∧ x ≠ y} doit devenir E ⊆ {{x, y} | (x, y) ∈ V²}. Pour les multigraphes non orientés, ϕ: E → {{x, y} | (x, y) ∈ V² ∧ x ≠ y} doit devenir ϕ: E → {{x, y} | (x, y) ∈ V²}. Pour lever toute ambiguïté, ces types d'objets peuvent être appelés précisément un graphe simple non orienté avec boucles et un multigraphe non orienté avec boucles respectivement.

V et E sont en général supposés finis, et de nombreux résultats cessent d'être vrais (ou ont des énoncés différents) pour des graphes infinis parce que certains arguments de preuve ne se transposent pas au cas infini. De plus, V est souvent supposé non vide, mais E peut être l'ensemble vide. L'ordre d'un graphe |V| est son nombre de sommets. La taille d'un graphe est |E|, son nombre d'arêtes. Le degré ou la valence d'un sommet est le nombre d'arêtes incidentes à ce sommet, où une boucle compte double.

Dans un graphe simple non orienté d'ordre n, le degré maximum d'un sommet est n − 1 et la taille maximale du graphe est n(n − 1)/2.

Les arêtes E d'un graphe non orienté G induisent une relation binaire symétrique ~ sur V appelée la relation d'adjacence de G. Spécifiquement, pour chaque arête {x, y}, ses sommets extrêmes x et y sont dits adjacents l'un l'autre, ce qui est noté x ~ y.

Un graphe orienté avec trois sommets et quatre arêtes.

Un graphe orienté est un graphe dans lequel les arêtes possèdent une orientation.

Dans un sens restreint mais très répandu du terme[6], un graphe orienté est un couple G = (V, A) (parfois G = (V, E)) comprenant

• V un ensemble de sommets (aussi appelés nœuds ou points) ;
• A ⊆ {(x, y) | (x, y) ∈ V² ∧ x ≠ y} un ensemble de flèches (aussi appelées arêtes orientées — parfois simplement arêtes avec l'ensemble correspondant nommé E au lieu de A —, liens orientés ou lignes orientées), qui sont des couples de sommets distincts (c.-à-d. une flèche est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un graphe simple orienté.

Dans la flèche (x, y) orientée de x vers y, x est appelé la queue de la flèche et y la tête de la flèche. La flèche (y, x) est appelée la flèche inverse de (x, y).

Dans un sens plus général du terme autorisant les flèches multiples[4]^,[5], un graphe orienté est un triplet G = (V, A, ϕ) (parfois G = (V, E, ϕ)) comprenant

• V un ensemble de sommets (aussi appelés nœuds ou points) ;
• A un ensemble de flèches (aussi appelées arêtes orientées — parfois simplement arêtes avec l'ensemble correspondant nommé E au lieu de A —, liens orientés ou lignes orientées);
• ϕ: A → {(x, y) | (x, y) ∈ V² ∧ x ≠ y} une fonction d'incidence associant à chaque flèche un couple de sommets distincts (c.-à-d. une flèche est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un multigraphe orienté.

Les graphes orientés tels que définis dans les deux définitions précédentes ne peuvent pas avoir de boucles, car une boucle joignant un sommet x est la flèche (pour un graphe simple orienté) ou est incidente sur (pour un multigraphe orienté) (x, x) qui n'est pas dans {(x, y) | (x, y) ∈ V² ∧ x ≠ y}. Ainsi pour autoriser les boucles les définitions doivent être étendues. Pour les graphes simples orientés, A ⊆ {(x, y) | (x, y) ∈ V² ∧ x ≠ y} doit devenir A ⊆ V². Pour les multigraphes orientés, ϕ: A → {(x, y) | (x, y) ∈ V² ∧ x ≠ y} doit devenir ϕ: A → V². Pour lever toute ambiguïté, ces types d'objets peuvent être appelés précisément un graphe simple orienté avec boucles et un multigraphe orienté avec boucles (ou un carquois) respectivement.

Un graphe simple orienté avec boucles est une relation homogène (une relation binaire entre un ensemble et lui-même). Un graphe simple orienté avec boucles G = (V, A) est dit symétrique si, pour chaque flèche de A, la flèche inverse correspondante appartient aussi à A.

Formellement un graphe est étiqueté : chaque sommet ou arête appartient à un ensemble, donc porte une étiquette. Typiquement, les graphes sont étiquetés par des nombres entiers, mais une étiquette peut en fait appartenir à n'importe quel ensemble : ensemble de couleurs, ensemble de mots, ensemble des réels. Les exemples ci-contre montrent des graphes étiquetés par des entiers et par des lettres. L'étiquetage d'un graphe peut être conçu de façon à donner des informations utiles pour des problèmes comme le routage : partant d'un sommet ${\displaystyle u}$, on veut arriver à un sommet ${\displaystyle v}$, c'est-à-dire que l'on souhaite acheminer une information de ${\displaystyle u}$ à ${\displaystyle v}$. Selon la façon dont les sommets sont étiquetés, les étiquettes que portent ${\displaystyle u}$ et ${\displaystyle v}$ peuvent nous permettre de trouver facilement un chemin. Par exemple, dans le graphe de Kautz (en) où la distance maximale entre deux sommets est ${\displaystyle D}$, imaginons que l'on soit à un sommet étiqueté ${\displaystyle (x_{1},x_{2},...,x_{D})}$ et que l'on souhaite aller à ${\displaystyle (y_{1},y_{2},...,y_{D})}$ : il suffit de décaler l'étiquette en introduisant la destination[R 1], ce qui donne le chemin

${\displaystyle (x_{1},x_{2},...,x_{D})\to (x_{2},...,x_{D},y_{1})\to (x_{3},...,x_{D},y_{1},y_{2})\to ...\to (x_{D},...,y_{D-2},y_{D-1})\to (y_{1},...,y_{D}).}$

Ce chemin se lit de la façon suivante : si on se trouve au sommet étiqueté ${\displaystyle (x_{1},x_{2},...,x_{D})}$ alors on va vers le voisin portant l'étiquette ${\displaystyle (x_{2},...,x_{D},y_{1})}$, et ainsi de suite.

On se retrouve cependant face à un problème : si on regarde plus haut l'illustration de la liste des arbres à 2, 3 et 4 sommets, beaucoup d'entre eux ont exactement la même structure mais un étiquetage différent (donné ici par des couleurs). Pour étudier uniquement la structure, il faut donc un outil permettant d'ignorer l'étiquetage, c'est-à-dire de donner une équivalence structurelle. Pour cela, on introduit la notion de morphisme. Un morphisme de graphes[R 2], ou homomorphisme de graphes, est une application entre deux graphes qui respecte la structure des graphes. Autrement dit l'image du graphe ${\displaystyle G}$ dans ${\displaystyle H}$ doit respecter les relations d'adjacences présentes dans ${\displaystyle G}$. Plus précisément, si ${\displaystyle G}$ et ${\displaystyle H}$ sont deux graphes, une application ${\displaystyle f:G\to H}$ est un morphisme de graphes si ${\displaystyle f=(f_{V},f_{E})}$ où ${\displaystyle f_{V}:V_{G}\to V_{H}}$ transforme les sommets de G en ceux de H, et ${\displaystyle f_{E}:E_{G}\to E_{H}}$ les arêtes de G en celles de H en respectant la contrainte suivante : s'il existe une arête ${\displaystyle e_{uv}\in E(G)}$ entre deux sommets de ${\displaystyle G}$ alors il doit y avoir une arête ${\displaystyle e_{f_{V}(u),f_{V}(v)}\in E(H)}$ entre les deux sommets correspondants de ${\displaystyle H}$. On dit de l'homomorphisme ${\displaystyle f}$ qu'il est une injection (respectivement surjection) si ses deux fonctions ${\displaystyle f_{V}}$ et ${\displaystyle f_{E}}$ sont injectives (respectivement surjectives); si elles sont à la fois injectives et surjectives, c'est-à-dire bijectives, alors ${\displaystyle f}$ est un isomorphisme de graphes. Si deux graphes sont isomorphes, alors ils ont la même structure : peu importe la façon dont ils sont dessinés ou étiquetés, il est possible de déplacer les sommets ou de changer les étiquettes pour que l'un soit la copie conforme de l'autre, ainsi qu'illustré ci-dessous. On désigne alors par graphe non étiqueté la classe d'équivalence d'un graphe pour la relation d'isomorphisme. Deux graphes isomorphes seront alors considérés comme égaux si on les considère en tant que graphes non étiquetés.

Graphe G	Graphe H	Isomorphisme entre G et H
		${\displaystyle f(a)=1}$ ${\displaystyle f(b)=6}$ ${\displaystyle f(c)=8}$ ${\displaystyle f(d)=3}$ ${\displaystyle f(g)=5}$ ${\displaystyle f(h)=2}$ ${\displaystyle f(i)=4}$ ${\displaystyle f(j)=7}$

Le mot graphe peut désigner, selon les contextes, un graphe étiqueté ou non étiqueté. Quand on parle du graphe du web, les étiquettes sont des URL et ont un sens. Le mot est utilisé pour désigner un graphe étiqueté. À l'opposé le graphe de Petersen est toujours considéré à isomorphisme près, donc non étiqueté, seules ses propriétés structurelles étant intéressantes.

• 
  L'hypercube ${\displaystyle Q_{3}}$ étiqueté sur l'alphabet ${\displaystyle \{0,1\}}$
• 
  Graphe étiqueté par des entiers
• 
  Graphe étiqueté par des lettres

Tout graphe ${\displaystyle G=(V,E)}$ peut être représenté par une matrice. Les relations entre arêtes et sommets, appelées les relations d'incidence, sont toutes représentées par la matrice d'incidence du graphe. Les relations d'adjacences (si deux sommets sont reliés par une arête ils sont adjacents) sont représentés par sa matrice d'adjacence. Elle est définie par

${\displaystyle a_{ij}=\left\{{\begin{array}{rl}1&{\mbox{si }}(v_{i},v_{j})\in E\\0&{\mbox{sinon.}}\end{array}}\right.}$

Graphe	Représentation par une matrice d'adjacence	Représentation par une matrice laplacienne (non normalisée)
	${\displaystyle {\begin{pmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}$	${\displaystyle {\begin{pmatrix}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{pmatrix}}}$

De nombreuses informations d'un graphe peuvent être représentées par une matrice. Par exemple, la matrice des degrés ${\displaystyle D}$ est une matrice diagonale où les éléments ${\displaystyle D_{ii}}$ correspondent au nombre de connexions du sommet ${\displaystyle i}$, c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne ${\displaystyle L=D-A}$ ; on obtient sa forme normalisée ${\displaystyle L'}$ par ${\displaystyle L'=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}}$, où ${\displaystyle I}$ dénote la matrice identité, ou on peut aussi l'obtenir directement par chacun de ses éléments :

${\displaystyle \ell _{i,j}:={\begin{cases}1&{\mbox{si}}\ i=j\ {\mbox{et}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{si}}\ i\neq j\ {\mbox{et}}\ v_{i}{\text{ est adjacent a }}v_{j}\\0&{\text{sinon}}.\end{cases}}}$

Ces représentations dépendent de la façon dont les sommets du graphe sont étiquetés. Imaginons que l'on garde la même structure que dans l'exemple ci-dessus et que l'on inverse les étiquettes 1 et 6 : on inverse alors les colonnes 1 et 6 de la matrice d'adjacence. Il existe en revanche des quantités qui ne dépendent pas de la façon dont on étiquette les sommets, tels que le degré minimal/maximal/moyen du graphe. Ces quantités sont des invariants du graphe : elles ne changent pas selon la numérotation. Tandis qu'une matrice d'adjacence ou laplacienne varie, son spectre, c'est-à-dire l'ensemble de ses valeurs propres ${\displaystyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$, est un invariant. L'étude du rapport entre les spectres et les propriétés d'un graphe est le sujet de la théorie spectrale des graphes[R 3] ; parmi les rapports intéressants, le spectre donne des renseignements sur le nombre chromatique, le nombre de composantes connexes et les cycles du graphe.

Décomposition arborescente à 6 sommets d'un graphe à 8 sommets. Chaque nœud de la décomposition contient au plus trois sommets du graphe original, et la profondeur de cette décomposition est donc 2.

Les graphes permettant de représenter de nombreuses situations, il existe de nombreux algorithmes (i.e. programmes) les utilisant. La complexité d'un algorithme consiste essentiellement à savoir, pour un problème donné, combien de temps est nécessaire pour le résoudre et quel est l'espace machine que cela va utiliser. Certaines représentations de graphes permettent d'obtenir de meilleures performances, c'est-à-dire que le problème est résolu plus rapidement ou en occupant moins d'espace. Dans certains cas, un problème NP-complet (classe la plus ardue) sur une représentation d'un graphe peut être résolu en temps polynomial (classe simple) avec une autre représentation; l'idée n'est pas qu'il suffit de regarder le graphe différemment pour résoudre le problème plus vite, mais que l'on « paye » pour le transformer et que l'on « économise » alors pour résoudre le problème. Une telle transformation est la décomposition arborescente proposée par les mathématiciens Robertson et Seymour dans leur série Graph Minors[R 4]. Intuitivement, une décomposition arborescente représente le graphe d'origine ${\displaystyle G}$ par un arbre, où chaque sommet correspond à un sous-ensemble des sommets de G, avec quelques contraintes. Formellement, pour un graphe donné ${\displaystyle G=(V,E)}$, sa décomposition arborescente est ${\displaystyle (f,T)}$ où ${\displaystyle T}$ est un arbre et ${\displaystyle f}$ une fonction associant à chaque sommet ${\displaystyle p\in T}$ un ensemble de sommets ${\displaystyle f(p)\subset V(G)}$. Trois contraintes doivent être satisfaites :

• ${\displaystyle \cup _{p\in V(T)}f(p)=V(G)}$. La décomposition n'oublie aucun sommet du graphe d'origine.
• ${\displaystyle \forall e_{uv}\in E(G),\exists p\in V(T)}$ tel que ${\displaystyle u\in f(p),v\in f(p)}$.
• ${\displaystyle \forall p,q,r\in V(T)}$ si ${\displaystyle q}$ est sur le chemin de ${\displaystyle p}$ à ${\displaystyle r}$ alors ${\displaystyle f(p)\cap f(r)\subseteq f(q)}$. Si l'on prend l'intersection des sommets abstraits par deux nœuds de l'arbre, alors cette intersection doit être contenue dans un sommet intermédiaire. Sur l'exemple ci-contre, l'intersection de {A,B,C} et {C,D,E} est {C} qui est bien contenue dans le sommet intermédiaire {C,B,E}.

La largeur arborescente ${\displaystyle tw(G)}$ d'une décomposition ${\displaystyle (f,T)}$ d'un graphe ${\displaystyle G}$ est ${\displaystyle \max _{p\in V(T)}|f(p)|-1}$, c'est-à-dire la taille du plus grand ensemble représenté par un sommet moins 1 ; on peut la voir comme l'abstraction maximale : pour un sommet de l'arbre, jusqu'à combien de sommets du graphe représente-t-on ? Construire la décomposition arborescente d'un graphe quelconque avec la plus petite largeur arborescente est un problème NP-dur[R 5]. Cependant, cela peut être fait rapidement pour certains graphes[R 6], ou approximée[R 7] pour d'autres tels les graphes planaires (i. e. pouvant être dessinés sans croiser deux arêtes).

Exemple d'un arbre, ayant 1 comme racine, {2,4,5,7} comme nœuds internes et {3,6,8,9,10,11,12} comme feuilles.

Robertson et Seymour développèrent également le concept de décomposition en branches. Pour la comprendre, il faut introduire davantage de vocabulaire sur un arbre. Dans les graphes, un arbre est dessiné "à l'envers" : on démarre de la racine en haut, et on descend jusqu'à atteindre les feuilles en bas ; tout sommet n'étant pas une feuille est appelé un 'nœud interne'. La décomposition en branches résulte en un arbre dans lequel tout nœud interne a exactement trois voisins (comme sur l'exemple ci-contre), et où chaque feuille représente une arête du graphe d'origine. La profondeur minimale de la décomposition d'un graphe ${\displaystyle G}$ est notée ${\displaystyle bw(G)}$, et on a la relation ${\displaystyle bw(G)\leq tw(G)+1\leq \left\lfloor {\frac {3\times bw(G)}{2}}\right\rfloor }$. De même que pour la décomposition arborescente, il est NP-dur de construire une décomposition en branches avec ${\displaystyle bw(G)}$ minimal pour un graphe quelconque ; dans ce cas, cette construction est réalisable pour un graphe planaire[R 8].

Ces représentations sont utilisées sur des problèmes NP-complets par des techniques de programmation dynamique, qui prennent généralement un temps exponentiel en ${\displaystyle bw(G)}$ ou ${\displaystyle tw(G)}$. Un tel problème est par exemple l'ensemble dominant : on veut savoir s'il y a un sous-ensemble ${\displaystyle D}$ de sommets de taille au plus ${\displaystyle k}$ tel qu'un sommet n'étant pas dans ${\displaystyle D}$ y soit relié par une arête. Si le graphe est planaire, cette technique permet de résoudre le problème[R 9] en temps ${\displaystyle O(2^{3\times \log _{4}(3l(H))}\times E|H|+n^{3})}$.

La façon dont le graphe est représenté en tant qu'objet mathématique a été exposée dans la section précédente. Dans l'aspect algorithmique de la théorie des graphes, on cherche à concevoir un processus efficace pour traiter un problème faisant intervenir un graphe. Les principaux critères d'efficacités d'un processus sont le temps nécessaire avant d'obtenir la réponse, et l'espace que le processus consomme dans son travail. La façon dont on représente le graphe influence la performance en temps et en espace : par exemple, si l'on veut connaître l'existence d'une arête entre deux sommets, la matrice d'adjacence permettra d'obtenir un résultat immédiatement, ce que l'on appelle en ${\displaystyle \theta (1)}$. En revanche, une opération de base telle que trouver le voisin d'un sommet est en ${\displaystyle O(n)}$ sur une matrice d'adjacence : dans le pire des cas, il faudra scanner la totalité de la colonne pour s'apercevoir qu'il n'y a pas de voisin. Une autre structure de données est la liste d'adjacence, consistant en un tableau dont l'entrée ${\displaystyle i}$ donne la liste des voisins du sommet ${\displaystyle i}$ : sur une telle structure, trouver un voisin se fait en ${\displaystyle \theta (1)}$ tandis que l'existence d'une arête est en ${\displaystyle O(n)}$. Ainsi, au niveau du temps, le choix de la structure dépend des opérations de base que l'on souhaite optimiser.

Un graphe étiqueté et sa représentation par liste d'adjacence ci-contre

Représentation par liste d'adjacence du graphe ci-contre:
0	adjacent à	0,1,2,3
1	adjacent à	0
2	adjacent à	0,3,4
3	adjacent à	0,2
4	adjacent à	2

De même, l'espace qu'une structure consomme dépend du type de graphe considéré : un raccourci abusif consiste à dire qu'une liste d'adjacences consomme moins d'espace qu'une matrice car celle-ci sera creuse, mais cela prend par exemple plus d'espace pour stocker un graphe aléatoire avec les listes qu'avec une matrice ; dans le cas général, une matrice utilise un espace ${\displaystyle \theta (n^{2})}$ et les listes utilisent ${\displaystyle \theta (m\log n)}$ donc si le graphe est dense alors ${\displaystyle m}$ peut être suffisamment grand pour qu'une matrice consomme moins d'espace, et si le graphe est peu dense alors les listes consommeront moins d'espace. Des modifications simples d'une structure de données peuvent permettre d'avoir un gain appréciable : par exemple, dans une représentation partiellement complémentée d'une liste, un bit spécial indique si la liste est celle des voisins présents ou manquants ; cette technique permet d'avoir des algorithmes linéaires sur le complément d'un graphe[Algo 1].

Tandis que ces structures sont locales, il existe aussi des structures de données distribuées. Le principe de ces structures est de concevoir un schéma d'étiquetage tel que, pour deux sommets ${\displaystyle x}$ et ${\displaystyle y}$, on puisse répondre à une question comme « quelle est la distance entre ${\displaystyle x}$ et ${\displaystyle y}$ » uniquement en utilisant les étiquettes de ces nœuds ; une telle utilisation des étiquettes a été vue en section « Étiquetage et morphismes » avec le graphe de Kautz où l'on peut déduire le chemin entre deux sommets uniquement grâce à leur étiquette, et la longueur de ce chemin nous donne la distance. Un étiquetage est efficace s'il permet de répondre à une question donnée uniquement en utilisant deux étiquettes, tout en minimisant le nombre maximum de bits d'une étiquette[Algo 2]. Outre la distance, une question type peut être de tester l'adjacence, c'est-à-dire de savoir si deux sommets sont voisins ; notons que cela se ramène également au cas particulier d'une distance 1. Le premier exemple d'étiquetage efficace pour tester l'adjacence fut proposé dans le cas des arbres, et chaque étiquette est constituée de deux parties de ${\displaystyle \log n}$ bits : la première partie identifie le sommet, et un nombre allant jusqu'à ${\displaystyle n}$ nécessite ${\displaystyle \log n}$ bits pour être codé, tandis que la seconde partie identifie le parent de ce sommet ; pour tester l'adjacence, on utilise le fait que deux sommets sont voisins dans un arbre si et seulement si l'un est le parent de l'autre[Algo 3].

L'efficacité d'un schéma d'étiquetage est lié à la taille des séparateurs du graphe.

Illustration d'un séparateur

Étant donné un graphe avec un ensemble de sommets ${\displaystyle V}$, ...

un séparateur est un ensemble de sommets ${\displaystyle S\subset V}$ tel que...

lorsqu'on le retire alors on sépare le graphe en deux composantes ${\displaystyle A_{1}}$ et ${\displaystyle A_{2}}$.

     

 

Si un graphe a des séparateurs de taille ${\displaystyle r(n)}$, alors on peut par exemple concevoir des étiquettes de ${\displaystyle O(r(n)\log ^{2}n)}$ bits pour la distance ; ceci permet directement d'en déduire l'étiquetage pour des graphes dont on connaît la taille des séparateurs, tels un graphe planaire où le séparateur est de taille ${\displaystyle r(n)={\sqrt {n}}}$[Algo 4]. Enfin, il ne faut pas considérer que la taille de l'étiquetage mais également le temps nécessaire, étant donnés deux étiquettes, pour effectuer le décodage répondant à la question (i.e. quelle est la distance ? sont-ils voisins ?).

De nombreux problèmes sur les graphes sont NP-complets, c'est-à-dire durs à résoudre. Cependant, cette dureté est inégale : certaines parties du problème peuvent être particulièrement dures, et en constituent ainsi le cœur, tandis que d'autres sont assez faciles à gérer. Ainsi, avant d'exécuter un algorithme sur un problème qui peut être dur, il est préférable de passer du temps à réduire ce problème pour ne plus avoir à considérer que son cœur.

• DOT est un outil en langage pour décrire des graphes de façon abstraite, ainsi qu'un outil en ligne de commande permettant d'exporter des graphes en images (JPEG, GIF, PNG) ou en dessin vectoriel SVG.
• Géomatique
• Sous-graphe
• Théorie topologique des graphes
• Graphe (type abstrait)
• RDF

• Notices d'autorité :

  • Bibliothèque nationale de France (données)
  • Bibliothèque du Congrès
  • Gemeinsame Normdatei
  • Bibliothèque nationale de la Diète
  • Bibliothèque nationale d’Israël
  • Bibliothèque nationale tchèque
• Notices dans des dictionnaires ou encyclopédies généralistes :

  • Encyclopædia Britannica
  • Encyclopædia Universalis
  • Hrvatska Enciklopedija
• (en) « Metanet », sur Scilab ATOMS (consulté le 18 janvier 2018) : boîte à outils Scilab pour les graphes et réseaux

• Portail de l'informatique théorique
• Portail de la sociologie