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 dethé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 desSept 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ésommetounœud, et chaque pont par une ligne, appeléebord, comme le montre la figure ci-dessus (b). Cette structure avec des sommets et des arêtes s'appelle ungraphe.

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. Le problème des Sept Ponts de Königsberg n’a donc 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 ungraphe orienté, chaque arête a une direction, ce qui indique que vous pouvez vous déplacer d'un sommet à l'autre via 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 ungraphe 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 ditsadjacentss'ils sont reliés par la même arête. De même, deux arêtes sont ditesadjacentessi elles sont connectées au même sommet. Une arête dans un graphe qui joint deux sommets est diteincidentaux deux sommets. Ledegréd'un sommet est le nombre d'arêtes qui lui sont accessoires.

Deux sommets sont appelésvoisinss'ils sont adjacents. De même, deux arêtes sont appeléesvoisinessi elles sont adjacentes.

Uneboucleest 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éesarêtes parallèles. Ungraphe simpleest un graphe qui ne comporte ni boucles ni arêtes parallèles. Dans ungraphe complet, toutes les deux paires de sommets sont connectées, comme le montre la figure ci-dessous (b).

Un graphe estconnectés'il existe un chemin entre deux sommets quelconques du graphe. Unsous-graphed'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-graphe du graphe dans la figure ci-dessus (b).

Supposons que le graphique soit connecté et non orienté. Uncycleest un chemin fermé qui part d'un sommet et se termine au même sommet. Un graphe connecté est unarbres'il n'a pas de cycles. Unarbre couvrantd'un graphe G est un sous-graphe connecté 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!