Graphiques et applications

De nombreux problèmes du monde réel peuvent être résolus à l'aide d'algorithmes graphiques. Les graphiques sont utiles pour modéliser et résoudre des problèmes du monde réel. Par exemple, le problème consistant à trouver le plus petit nombre de vols entre deux villes peut être modélisé à l'aide d'un graphique, où les sommets représentent les villes et les arêtes représentent les vols entre deux villes adjacentes, comme le montre la figure ci-dessous. Le problème de trouver le nombre minimal de vols de correspondance
entre deux villes se réduit à trouver le chemin le plus court entre deux sommets d'un graphe.

L'étude des problèmes liés aux graphes est connue sous le nom de théorie des graphes. La théorie des graphes a été fondée par Leonhard Euler en 1736, lorsqu'il a introduit la terminologie des graphes pour résoudre le célèbre problème des Sept ponts de Königsberg. La ville de Königsberg, en Prusse (aujourd'hui Kaliningrad, en Russie), était divisée par la rivière Pregel. Il y avait deux îles sur le fleuve. La ville et les îles étaient reliées par sept ponts, comme le montre la figure ci-dessous (a). La question est : peut-on se promener, traverser chaque pont exactement une fois et revenir au point de départ ? Euler a prouvé que ce n'était pas possible.

Pour établir une preuve, Euler a d'abord extrait le plan de la ville de Königsberg en éliminant toutes les rues, produisant ainsi le croquis présenté dans la figure ci-dessus (a). Ensuite, il a remplacé chaque masse terrestre par un point, appelé sommet ou nœud, et chaque pont par une ligne, appelée bord, comme le montre Figure ci-dessus (b). Cette structure avec des sommets et des arêtes s'appelle un graphe.

En regardant le graphique, nous demandons s'il existe un chemin partant de n'importe quel sommet, traversant toutes les arêtes exactement une fois et revenant au sommet de départ. Euler a prouvé que pour qu’un tel chemin existe, chaque sommet doit avoir un nombre pair d’arêtes. Par conséquent, le problème des Sept Ponts de Königsberg n’a pas de solution.

Les problèmes de graphiques sont souvent résolus à l'aide d'algorithmes. Les algorithmes graphiques ont de nombreuses applications dans divers domaines, tels que l'informatique, les mathématiques, la biologie, l'ingénierie, l'économie, la génétique et les sciences sociales.

Terminologies graphiques de base

Un graphe se compose de sommets et d'arêtes qui relient les sommets. Ce chapitre ne suppose pas que vous ayez des connaissances préalables en théorie des graphes ou en mathématiques discrètes. Nous utilisons des termes clairs et simples pour définir les graphiques.

Qu'est-ce qu'un graphique ? Un graphique est une structure mathématique qui représente les relations entre les entités du monde réel. Par exemple, le graphique de la figure ci-dessus représente les vols entre les villes, et le graphique de la figure ci-dessous (b) représente les ponts entre les masses terrestres.

Un graphe se compose d'un ensemble non vide de sommets (également appelés nœuds ou points) et d'un ensemble d'arêtes qui relient les sommets. Pour plus de commodité, nous définissons un graphe comme G = (V, E), où V représente un ensemble de sommets et E représente un ensemble d'arêtes. Par exemple, V et E pour le graphique de la figure ci-dessous sont les suivants :

V = {"Seattle", "San Francisco", "Los Angeles",
"Denver", "Kansas City", "Chicago", "Boston", "New York",
"Atlanta", "Miami", "Dallas", "Houston"};

E = {{"Seattle", "San Francisco"},{"Seattle", "Chicago"},
{"Seattle", "Denver"}, {"San Francisco", "Denver"},
...
};

Un graphique peut être orienté ou non. Dans un graphe orienté, chaque arête a une direction, ce qui indique que vous pouvez vous déplacer d'un sommet à l'autre en passant par l'arête. Vous pouvez modéliser les relations parent/enfant à l'aide d'un graphe orienté, où une arête du sommet A à B indique que A est un parent de B. La figure ci-dessous (a) montre un graphe orienté.

Dans un graphe non orienté, vous pouvez vous déplacer dans les deux sens entre les sommets. Le graphique de la figure ci-dessous n'est pas orienté.

Les bords peuvent être pondérés ou non. Par exemple, vous pouvez attribuer un poids à chaque bord du graphique de la figure ci-dessus pour indiquer le temps de vol entre les deux villes.

Deux sommets d'un graphe sont dits adjacents s'ils sont reliés par la même arête. De même, deux arêtes sont dites adjacentes si elles sont reliées au même sommet. Une arête dans un graphe qui joint deux sommets est dite incidente aux deux sommets. Le degré d'un sommet est le nombre d'arêtes qui lui sont incidents.

Deux sommets sont appelés voisins s'ils sont adjacents. De même, deux arêtes sont appelées voisines si elles sont adjacentes.

Une boucle est une arête qui relie un sommet à lui-même. Si deux sommets sont reliés par deux ou plusieurs arêtes, ces arêtes sont appelées arêtes parallèles. Un graphe simple est un graphe qui ne comporte ni boucles ni arêtes parallèles. Dans un graphe complet, toutes les deux paires de sommets sont connectées, comme le montre la figure ci-dessous (b).

Un graphe est connecté s'il existe un chemin entre deux sommets quelconques du graphe. Un sous-graphe d'un graphe G est un graphe dont l'ensemble des sommets est un sous-ensemble de celui de G et dont l'ensemble des arêtes est un sous-ensemble de celui de G. Par exemple, le graphe de la figure ci-dessus (c) est un sous-graphique du graphique de la figure ci-dessus (b).

Supposons que le graphique soit connecté et non orienté. Un cycle est un chemin fermé qui part d'un sommet et se termine au même sommet. Un graphe connecté est un arbre s'il ne comporte pas de cycles. Un arbre couvrant d'un graphe G est un sous-graphe connexe de G et le sous-graphe est un arbre qui contient tous les sommets de G.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!