Graphe orienté donné. Graphique orienté. Graphes bouclés, graphes mixtes, graphes vides, multigraphes, graphes ordinaires, graphes complets

Graphique dirigé(brièvement digraphe) est un (multi)graphe dont les arêtes ont une direction. Les arêtes dirigées sont également appelées arcs, et dans certaines sources et juste les bords. Un graphe dans lequel aucune arête n'est assignée à une direction est appelé un graphe non orienté, ou non digraphe.

Concepts de base

Formellement, le digraphe ré = (V , E) (\displaystyle D=(V,E)) se compose de plusieurs V (\displaystyle V), dont les éléments sont appelés pics, et ensembles E (\displaystyle E) paires ordonnées de sommets u , v ∈ V (\displaystyle u,v\in V).

Arc (u , v) (\displaystyle (u,v)) accessoire pics tu (\displaystyle u) et v (\ displaystyle v). En même temps, ils disent que tu (\displaystyle u) - pic initial arc, et v (\ displaystyle v) - pic terminal.

Connectivité

itinéraire dans un digraphe est appelé une séquence alternée de sommets et arcs, gentil v 0 ( v 0 , v 1 ) v 1 ( v 1 , v 2 ) v 2 . . . v n (\displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(les sommets peuvent être répétés). Longueur de l'itinéraire- le nombre d'arcs qu'il contient.

Chemin il y a itinéraire dans un digraphe sans arcs répétitifs, moyen facile- pas de sommets répétés. S'il existe un chemin d'un sommet à un autre, alors le deuxième sommet réalisable Depuis le premier.

Circuit il y a un fermé chemin.

Pour demi-parcours la restriction sur la direction des arcs est supprimée, le à mi-chemin et semi-contour.

digramme fortement connecté, ou simplement fort, si tous ses sommets sont mutuels réalisable; unidirectionnel connecté, ou simplement unilatéral si pour deux sommets au moins l'un est accessible depuis l'autre ; vaguement connecté, ou simplement faible, si on ignore la direction des arcs, on obtient un (multi)graphe connexe ;

Maximum fort le sous-graphe s'appelle composant fort; composant unilatéral et composant faible sont définis de manière similaire.

condensation digramme D (\displaystyle D) appelé digraphe dont les sommets sont des composantes fortes D (\displaystyle D), et l'arc dans D ⋆ (\displaystyle D^(\star )) indique la présence d'au moins un arc entre les sommets inclus dans les composantes correspondantes.

Définitions supplémentaires

Graphe acyclique dirigé ou hamac est un digraphe sans contour.

Un graphe orienté obtenu à partir d'un graphe donné en inversant la direction des arêtes est appelé inverse.

Image et propriétés de tous les digraphes à trois nœuds

Légende: DE- faible, SE- unilatéral, SS- fort, H- est un graphe orienté, g- est un hamac (acyclique), J- est un tournoi

vide, N, G	N, G		SE	CC	CC	complet, CC
0 arc	1arc	2 arcs	3 arcs	4 arcs	5 arcs	6 arcs
		SE, N, G	CC, N, T	CC
		C, N, G	SE, N, G, T	SE
		C, N, G	SE

Dans les chapitres précédents, nous avons présenté quelques-uns des principaux résultats de la théorie des graphes non orientés. Cependant, les graphes non orientés ne suffisent pas à décrire certaines situations. Par exemple, lors de la représentation d'une carte de circulation avec un graphique dont les bords correspondent à des rues, une orientation doit être affectée aux bords pour indiquer la direction de déplacement autorisée. Un autre exemple est un programme informatique modélisé par un graphe dont les arêtes représentent le flux de contrôle d'un ensemble d'instructions à un autre. Dans cette représentation du programme, les bords doivent également être orientés pour indiquer la direction du flux de contrôle. Un autre exemple de système physique qui nécessite un graphe orienté pour être représenté est un circuit électrique. Les applications des graphes orientés et des algorithmes associés sont discutées au Chap. 11-15.

Ce chapitre présente les principaux résultats de la théorie des graphes orientés. Des questions liées à l'existence de chaînes d'Euler orientées et de cycles hamiltoniens sont discutées. Les arbres orientés et leur connexion avec les chaînes d'Euler orientées sont également considérés.

5.1. Définitions et concepts de base

Commençons par introduire quelques définitions et concepts de base liés aux graphes orientés.

Un graphe orienté est constitué de deux ensembles : un ensemble fini V, dont les éléments sont appelés sommets, et un ensemble fini E, dont les éléments sont appelés arêtes ou arcs. Chaque arc est associé à une paire ordonnée de sommets.

Les symboles sont utilisés pour désigner les sommets et les symboles sont utilisés pour désigner les arcs. Si , alors sont appelés sommets d'extrémité, et - sommet initial, - sommet d'extrémité . Tous les arcs qui ont la même paire de sommets de début et de fin sont appelés parallèles. Un arc est appelé une boucle si le sommet incident est à la fois son sommet de début et son sommet de fin.

Dans une représentation graphique d'un graphe orienté, les sommets sont représentés par des points ou des cercles, et les arêtes (arcs) sont représentées par des segments.

lignes reliant des points ou des cercles représentant leurs extrémités. De plus, les arcs se voient attribuer une orientation, indiquée par une flèche pointant du sommet de départ au sommet de fin.

Par exemple, si tel que Leur), un graphe orienté peut être représenté par la fig. 5.1. Dans ce graphique - arcs parallèles, et - boucle.

Riz. 5.1. Graphique orienté.

Un arc est dit incident à ses sommets terminaux. Les sommets sont dits adjacents s'ils sont terminaux pour un arc. Si les arcs ont un sommet terminal commun, alors ils sont dits adjacents.

Un arc est dit sortant de son sommet initial et entrant dans son sommet final. Un sommet est dit isolé s'il n'a pas d'arc incident.

Le degré d'un sommet est le nombre d'arcs qui lui sont incidents. Le degré d'entrée d'un sommet est le nombre d'arcs entrant dans V] et le degré de sortie est le nombre d'arcs sortants. Les symboles et b" indiquent le degré extérieur et le degré d'entrée minimum du graphe orienté. De même, les symboles indiquent le degré extérieur et le degré d'entrée maximum, respectivement.

Les ensembles de n'importe quel sommet sont définis comme suit : . Par exemple, dans le graphique de la Fig. 5.1.

Notez que la boucle augmente les demi-degrés d'entrée et de sortie de ce sommet. L'assertion suivante est une conséquence du fait que chaque arc augmente de 1 la somme des demi-degrés de l'entrée et de la sortie d'un graphe orienté.

Théorème 5.1. Dans un graphe orienté avec des arcs

Somme des degrés entrants = Somme des degrés sortants = m.

Les sous-graphes et les sous-graphes générés d'un graphe orienté sont définis de la même manière que dans le cas des graphes non orientés (Sec. 1.2).

Un graphe non orienté résultant de la suppression de l'orientation des arcs d'un graphe orienté G est appelé le graphe non orienté sous-jacent G et est noté .

Un chemin orienté d'un graphe orienté est une séquence finie de sommets

Qu'est-ce qu'un arc du graphe G. Un tel itinéraire est généralement appelé un itinéraire orienté, et le sommet initial est le sommet final de l'itinéraire, et tous les autres sommets sont internes. Les sommets de début et de fin d'un chemin orienté sont appelés ses sommets de fin. Notez que les arcs, et donc les sommets, peuvent apparaître plus d'une fois dans un chemin orienté.

Une route orientée est dite ouverte si ses sommets d'extrémité sont différents, sinon elle est dite fermée.

Un chemin orienté est dit chemin orienté si tous ses arcs sont distincts. Un chemin orienté est ouvert si ses extrémités sont distinctes, sinon il est fermé.

Un chemin orienté ouvert est appelé chemin orienté si tous ses sommets sont distincts.

Une chaîne orientée fermée est appelée cycle ou contour orienté si ses sommets, à l'exception des sommets terminaux, sont différents.

Un graphe orienté est dit acyclique ou sans contours s'il n'a pas de contours. Par exemple, le graphe orienté de la figure 1 est acyclique. 5.2.

Riz. 5.2. Graphe orienté acyclique.

Riz. 5.3. Un graphe orienté fortement connexe.

Une séquence de sommets dans un graphe orienté G est appelée un chemin dans G s'il s'agit d'un chemin dans le graphe non orienté sous-jacent. Par exemple, la séquence dans le graphe de la Fig. 5.2 est un itinéraire, mais non orienté.

La chaîne, le chemin et le cycle d'un graphe orienté sont définis de la même manière.

Un graphe orienté est dit connexe si le graphe non orienté sous-jacent est connexe.

Un sous-graphe d'un graphe orienté G est appelé une composante du graphe G s'il est une composante du graphe

Les sommets d'un graphe orienté G sont dits fortement connectés s'il existe des chemins orientés depuis et vers G. Si est fortement connecté à alors, évidemment, est fortement connecté à . Chaque sommet est fortement connecté à lui-même.

Si un sommet est fortement connecté à un sommet, alors, comme il est facile de le voir, le sommet est fortement connecté au sommet, donc dans ce cas on dit simplement que les sommets sont fortement connectés.

Un graphe orienté est dit fortement connexe si tous ses sommets sont fortement connexe. Par exemple, le graphique de la Fig. 5.3.

Le sous-graphe maximal fortement connexe d'un graphe orienté G est appelé une composante fortement connexe de G. Si un graphe orienté est fortement connexe, alors il a une seule composante fortement connexe, à savoir lui-même.

Prenons un graphe orienté. Il est facile de voir que chacun de ses sommets appartient à exactement une composante fortement connexe du graphe G. Par conséquent, les ensembles de sommets des composantes fortement connexes forment une partition de l'ensemble de sommets Y du graphe

Riz. 5.4. Graphique et sa condensation.

Par exemple, le graphe orienté de la Fig. 5.4, a a trois composants fortement connectés avec des ensembles de sommets et formant une partition de l'ensemble de sommets d'un graphe orienté.

Fait intéressant, un graphe orienté peut contenir des arcs qui ne sont inclus dans aucun composant fortement connecté du graphe. Par exemple, aucun composant fortement connecté n'inclut d'arcs dans le graphique de la Fig. 5.4, un.

Ainsi, bien que la propriété "fortement connectée" implique le découpage de l'ensemble des sommets du graphe, elle peut ne pas générer le découpage de l'ensemble des arcs.

L'union, l'intersection, la somme mod 2 et les autres opérations sur les graphes orientés sont définies exactement de la même manière que dans le cas des graphes non orientés (Sec. 1.5).

Le graphe résultant de la contraction de tous les arcs de composantes fortement connexes d'un graphe orienté G est appelé le graphe condensé de G. La condensation du graphe représenté sur la fig. 5.4, a, est illustré à la fig. 5.4b.

Les sommets du graphe correspondent à des composantes fortement connexes du graphe G et sont appelées images condensées des composantes.

Le rang et le numéro cyclomatique d'un graphe orienté sont les mêmes que ceux du graphe non orienté correspondant. Cela signifie que si un graphe orienté G a des arcs, des sommets et des composants, alors le rang et le numéro cyclomatique du graphe G sont donnés par

Nous définissons maintenant des graphes orientés minimalement connectés et étudions certaines de leurs propriétés.

Un graphe orienté G est dit minimalement connexe s'il est fortement connexe, et la suppression de tout arc le prive de sa propriété fortement connexe.

Riz. 5.5. Graphe orienté minimalement connecté.

Minimalement connecté est, par exemple, le graphique illustré à la Fig. 5.5.

De toute évidence, les graphes minimalement connectés ne peuvent pas avoir d'arcs et de boucles parallèles.

On sait qu'un graphe non orienté est minimalement connexe si et seulement si c'est un arbre (Ex. 2.13). D'après le théorème 2.5, un arbre a au moins deux sommets de degré 1. Par conséquent, les graphes non orientés minimalement connectés ont au moins deux sommets de degré 1.

Établissons un résultat similaire pour les graphes orientés. Le degré de tout sommet d'un graphe orienté fortement connecté doit être d'au moins 2, puisque chaque sommet doit avoir des arcs sortants et entrants. Dans le théorème suivant, nous prouvons qu'un graphe orienté minimalement connexe a au moins deux sommets de degré 2.

Dans la première leçon, introduisant le concept de graphe, nous avons pris comme exemple la compétition d'équipes sportives. Nous. connecté deux équipes, disons A et C, avec le bord AC dans le cas où ces équipes jouaient déjà l'une contre l'autre. Cependant, un tel graphique ne répond pas à une question très importante : qui a exactement gagné la partie ?
Cette lacune peut facilement être éliminée. Si l'équipe A a gagné contre C, nous conviendrons de mettre une flèche sur l'arête AC, dirigée de A vers C. Supposons que nous connaissions les résultats de toutes les parties déjà jouées, et ajoutons au graphique fig. 1 flèches correspondantes ; Soit ce résultat dans le graphique représenté sur la Fig. 58.

Figure 58.

Ce graphique montre que l'équipe A a battu C, l'équipe F a perdu contre A et l'équipe B a remporté tous les matchs contre C, E, F, etc.

Bord le graphique s'appelle orienté, si un sommet est considéré le début de la côte, et l'autre - fin.
Un graphe dont toutes les arêtes sont orientées est appelé orientationcompter.
Le même sommet d'un graphe orienté peut servir de début pour certaines arêtes et de fin pour d'autres. En conséquence, deux degrés du sommet sont distingués: degré de sortie et degré d'entrée.
Diplôme de sortie le sommet A d'un graphe orienté est le nombre d'arêtes partant de A (notation : d+(A)).
Le degré d'entrée d'un sommet A d'un graphe orienté est le nombre d'entrées dans MAIS bords (symbole : d-(A)).
Et si une partie se terminait par un match nul ? Nous pouvons refléter les résultats d'égalité sur le graphique en laissant les arêtes correspondantes non dirigées. Ce faisant, nous obtenons ce que l'on appelle nmcomte de shanny, qui a à la fois des arêtes dirigées et non dirigées.
Un chemin dans un graphe orienté G de A1 à An est une suite d'arêtes orientées<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, de sorte que la fin de chaque arête précédente coïncide avec le début de la suivante et qu'aucune arête ne se produise plus d'une fois.

Riz. 59
Si dans un graphe orienté G il existe un chemin depuis MAISà B, puis retour de Àà MAIS peut-être pas (Fig. 59).
S'il existe un chemin orienté de A vers B, on dit que B est atteindremaman de
Dans la colonne G de la figure 38 B est réalisable
depuis A, A n'est pas accessible depuis B.
la manière facile Un graphe orienté est un chemin dans lequel aucun sommet n'est contenu plus d'une fois. chemin fermé dans un graphe orienté est appelé un cycle orienté.
long chemin est le nombre d'arêtes dans ce chemin.
Distance de A à B dans un graphe orienté est la longueur du chemin le plus court de A à B. S'il n'y a pas de chemin de A à B, alors la distance de A à B est appelée infinie et notée ?. La distance de A à B sera notée S (AB). Pour le graphique de la Figure 38
S (AB) \u003d 1, S (CB) - 2, S (BC) \u003d ?.
Problème 9.1.
Dans une station balnéaire, après la mise en place d'une circulation à sens unique, il s'est avéré que le nombre de rues par lesquelles on peut entrer à chaque carrefour est égal au nombre de rues par lesquelles on peut en sortir. Prouver qu'il est possible de proposer un itinéraire de patrouille qui commence et se termine au même endroit et passe par chaque section de rue exactement une fois.
La solution.
Construisons un digraphe G qui définit le mouvement dans la ville.
Le digraphe s'appelle lié, s'il est possible de passer de n'importe lequel de ses sommets à n'importe quel autre le long d'arcs sans tenir compte de leur orientation. Le digraphe connexe est appelé Euler, s'il a un cycle d'Euler.
Théorème 12. Un digraphe connexe est Euler si et seulement si pour chacun de ses sommetsvégalitéré- (v) = ré+ (v) .
Le théorème se démontre exactement de la même manière que le théorème du problème 4.2.
Il résulte des conditions du problème que pour les sommets du graphe construit G, l'égalité d-(v) = d+(v) est satisfaite. Par conséquent, le graphe d'Euler G et le cycle d'Euler détermineront l'itinéraire de patrouille souhaité.
Problème 9.2.
Un nombre fini de points sont marqués sur le plan. Certaines paires de points sont les débuts et les fins de vecteurs, et le nombre de vecteurs entrant dans un point est égal au nombre de vecteurs qui en sortent. Trouver la somme des vecteurs.
La solution.
Les points du plan forment avec les vecteurs un digraphe G. Le cycle d'un digraphe dont tous les sommets sont différents est appelé contour.
Théorème 13. Digraphe connexegEuler si et seulement sigest l'union des contours qui deux à deux n'ont pas d'arêtes communes.
Preuve. Nécessité Soit G un digraphe d'Euler. Considérons son sommet quelconque u1. Laissons le sommet u1 le long d'un arc (u1, u2), ce qui est possible puisque le digraphe G est connexe. Puisque d-(u2) = d+(u2), il est possible de laisser le sommet u2 le long de l'arc (u2, u3) . Le digraphe G a un nombre fini de sommets, donc nous nous retrouvons à un sommet w où nous étions auparavant. La partie de la chaîne qui commence et se termine en w est le chemin C1. Supprimer les arcs du contour C1 du digraphe G . Dans le digraphe résultant G1 (éventuellement déconnecté), les degrés d'entrée et de sortie des sommets appartenant à C ont diminué de un, les degrés d'entrée et de sortie des sommets restants n'ont pas changé. Donc, pour tout sommet v du digraphe C1, l'égalité d-(v) = d+(v) sera vérifiée. Ainsi, dans le digraphe G1, on peut distinguer le contour C 2 etc.
La suffisance est prouvée en combinant les contours dans un cycle d'Euler (voir la preuve du théorème dans le problème 4.2).
Le théorème a été prouvé. Peut-être que le digraphe G définissant les vecteurs dans notre problème n'est pas connexe. En appliquant le théorème prouvé à chaque partie connexe du digraphe, on obtient une partition de vecteurs en contours. La somme des vecteurs appartenant à un contour est égale à zéro. Par conséquent, la somme de tous les vecteurs est égale à zéro.

Avant de commencer à étudier directement les algorithmes, vous devez avoir des connaissances de base sur les graphiques eux-mêmes, pour comprendre comment ils sont représentés dans un ordinateur. Ici, tous les aspects de la théorie des graphes ne seront pas décrits en détail (ce n'est pas obligatoire), mais seulement ceux dont l'ignorance compliquera considérablement l'assimilation de ce domaine de la programmation.

Quelques exemples donneront une idée un peu superficielle du graphe. Ainsi, un graphique typique est un plan de métro ou un autre itinéraire. En particulier, un programmeur est familier avec un réseau informatique, qui est aussi un graphe. La chose commune ici est la présence de points reliés par des lignes. Ainsi, dans un réseau informatique, les points sont des serveurs distincts et les lignes sont différents types de signaux électriques. Dans le métro, le premier ce sont les stations, le second ce sont les tunnels posés entre elles. En théorie des graphes, les points sont appelés pics (noeuds), et les lignes travers de porc (arcs). De cette façon, graphique est une collection de sommets reliés par des arêtes.

Les mathématiques opèrent non pas avec le contenu des choses, mais avec leur structure, en l'abstrayant de tout ce qui est donné comme un tout. En utilisant uniquement cette technique, nous pouvons conclure sur certains objets comme sur les graphes. Et puisque la théorie des graphes fait partie des mathématiques, peu lui importe ce qu'est, en principe, un objet ; la seule chose importante est de savoir s'il s'agit d'un graphe, c'est-à-dire s'il possède les propriétés requises pour les graphes. Donc, avant de donner des exemples, nous ne distinguons dans l'objet considéré que ce qui, à notre avis, nous permettra de montrer une analogie, nous cherchons quelque chose de commun.

Revenons au réseau informatique. Il a une certaine topologie et peut être décrit de manière conventionnelle comme un certain nombre d'ordinateurs et de chemins les reliant. La figure ci-dessous montre une topologie entièrement maillée à titre d'exemple.

C'est essentiellement un graphique. Les cinq ordinateurs sont des sommets et les connexions (chemins de signalisation) entre eux sont des arêtes. En remplaçant les ordinateurs par des sommets, nous obtenons un objet mathématique - un graphe qui a 10 arêtes et 5 sommets. Vous pouvez numéroter les sommets de manière arbitraire, et pas nécessairement comme cela se fait sur la figure. Il convient de noter que dans cet exemple, aucune boucle n'est utilisée, c'est-à-dire une telle arête qui quitte le sommet et y pénètre immédiatement, mais des boucles peuvent se produire dans les problèmes.

Voici quelques notations importantes utilisées en théorie des graphes :

G=(V, E), ici G est un graphe, V sont ses sommets, et E sont des arêtes ;
|V| – ordre (nombre de sommets);
|E| – taille du graphe (nombre d'arêtes).

Dans notre cas (Fig. 1) |V|=5, |E|=10 ;

Lorsqu'un autre sommet est accessible depuis n'importe quel sommet, alors un tel graphe est appelé désorienté graphe connexe (Fig. 1). Si le graphe est connexe, mais que cette condition n'est pas satisfaite, alors un tel graphe est appelé orienté ou un digramme (Fig. 2).

Les graphes orientés et non orientés ont la notion de degré d'un sommet. Degré de sommet est le nombre d'arêtes qui le relient aux autres sommets. La somme de tous les degrés d'un graphe est égale au double du nombre de toutes ses arêtes. Pour la figure 2, la somme de toutes les puissances est 20.

Dans un digraphe, contrairement à un graphe non orienté, il est possible de passer du sommet h au sommet s sans sommets intermédiaires, uniquement lorsqu'une arête quitte h et entre dans s, mais pas l'inverse.

Les graphes orientés ont la notation suivante :

G=(V, A), où V sont des sommets, A sont des arêtes orientées.

Le troisième type de graphiques - mixte graphiques (fig. 3). Ils ont à la fois des bords dirigés et des bords non directionnels. Formellement, un graphe mixte s'écrit : G=(V, E, A), où chacune des lettres entre parenthèses désigne également ce qui lui a été précédemment attribué.

Dans le graphe de la figure 3, certains arcs sont orientés [(e, a), (e, c), (a, b), (c, a), (d, b)], d'autres sont non orientés [( e, d), (e, b), (d, c)…].

Deux graphiques ou plus à première vue peuvent sembler différents dans leur structure, ce qui est dû à leur représentation différente. Mais ce n'est pas toujours le cas. Prenons deux graphiques (Fig. 4).

Ils sont équivalents les uns aux autres, car sans changer la structure d'un graphique, vous pouvez en construire un autre. De tels graphiques sont appelés isomorphe, c'est-à-dire ayant la propriété que tout sommet avec un certain nombre d'arêtes dans un graphe a un sommet identique dans un autre. La figure 4 montre deux graphes isomorphes.

Lorsque chaque arête d'un graphe se voit attribuer une valeur, appelée poids de l'arête, alors un tel graphe suspendu. Dans différentes tâches, différents types de mesures peuvent agir comme des poids, par exemple, des longueurs, des prix d'itinéraire, etc. Dans une représentation graphique d'un graphique, les valeurs de poids sont généralement indiquées à côté des bords.

Dans chacun des graphiques que nous avons considérés, il est possible de sélectionner un chemin et, de plus, plusieurs. Chemin est une séquence de sommets, chacun étant relié au suivant par une arête. Si les premier et dernier sommets coïncident, alors un tel chemin est appelé un cycle. La longueur d'un chemin est déterminée par le nombre d'arêtes qui le composent. Par exemple, dans la Figure 4.a, le chemin est la séquence [(e), (a), (b), (c)]. Ce chemin est un sous-graphe, puisque la définition de ce dernier s'y applique, à savoir : le graphe G'=(V', E') n'est un sous-graphe du graphe G=(V, E) que si V' et E' appartiennent à V, E .