26 - Graphe : cycles et parcours
Imaginons que nous désirions voyager d'un sommet A à un sommet B. Si ce voyage est possible :
- le parcours en largeur permettra de trouver UN chemin (si au moins un chemin existe) : celui nécessitant le moins de changement de direction (nombre d'arêtes)
- le parcours en profondeur de base permettra peut-être de trouver UN chemin (si un chemin existe et que l'arbre de parcours tombe par hasard dessus).
Nous allons analyser un peu plus le parcours en profondeur d'un graphe de façon à comment trouver un chemin dans un graphe sans tourner éternellement en rond.
Nous allons donc aujourd'hui voir comment trouver TOUS les chemins. Mais pour cela, il faut trouver le moyen de détecter les cycles afin de ne pas tourner à l'infini sur les mêmes sommets !
Logiciel nécessaire pour l'activité : -
Prérequis : Algo : Parcours en profondeur d'un Arbre
Evaluation ✎ : -
Documents de cours : open document ou pdf
1 - Rappel : parcours en profondeur d'un graphe
Partons du dernier exercice de l'activité précédente :
Voici la forêt que nous avions obtenu :
Si on veut relier S1 à S5, ça va aller. Mais si on veut relier S6 à S1, la Forêt de parcours obtenue pourrait nous laisser croire que ce n'est pas possible...
Pour trouver toutes les routes, vous pourriez vous dire qu'il suffit de tester toutes les possibilités.
01° Quel chemin évident apparaît pour un humain pour relier le sommet S6 au sommet S1 ?
...CORRECTION...
S6 → S5 → S4 → S2 → S1.
02° Quel autre chemin (idiot pour un humain voyant le plan car contenant une boucle) pourrait fournir un ordinateur qui teste juste toutes les possibilités ?
...CORRECTION...
S6 → S5 → S4 → S2 → S5 → S4 → S2 → S1.
Bilan :
- Si on ne considère que les cases BLANCHES pour avancer : on rate des possibilités pour avancer si par malchance on commence par la mauvaise case.
- Si on accepte de repartir vers des cases déjà visitées, on risque d'incorporer des possibilités comportant des boucles et donc d'avoir un algorithme qui propose une infinité de solutions consistant à tourner une fois sur S5-S4-S2, puis deux fois autour de S5-S4-S2, puis trois fois autour de S5-S4-S2...
03° Explorer le graphe en profondeur en suivant la nouvelle liste de sommets.
...CORRECTION...
Constat : selon le sommet de départ, l'Arbre de parcours en profondeur obtenu n'est pas le même...
Nous avons vu que le coût du parcours est linéaire par rapport à s+a. Relancer l'algorithme s fois pour placer à chaque fois l'un des sommets en première possition est une possibilité de force brute. Mais dans ce cas, nous allons avoir une complexité en 𝞗(sx(s+a)) et donc on atteint un coût plus que quadratique en fonction du nombre s de sommets...
2 - Parcours complet en profondeur d'un graphe
En réalité, nous allons faire exactement comme dans l'activité précédente, nous allons simplement rajouter deux informations sur les sommets lors du parcours. Voici donc deux nouveaux attributs qu'il faudra rajouter aux sommets :
- la date debut où le sommet a été découvert et visité la première fois (passage de BLANC à GRIS)
- la date fin où le sommet a été entièrement traité (tous ses arcs ou arêtes ont été utilisés, passage de GRIS à NOIR)
Pour gérer les dates, nous allons simplement utiliser un nombre (stocké via une variable date) qu'on incrémentera de un à chaque fois :
- qu'on commence l'exploration d'un sommet (passage de BLANC à GRIS) ou
- qu'on finalise l'exploration d'un sommet (passage de GRIS à NOIR).
Comment gérer ce nombre ?
- Nous pourrions utiliser une variable globale mais vous savez maintenant que cette possibilité est à éviter dans la mesure du possible.
- Nous pourrions transmettre la référence d'une variable mutable créée pour l'occassion et ne contenant qu'un compteur qu'on incrémente à chaque étape (un tableau, un dictionnaire...)
- Nous pourrions simplement rajouter un attribut date au graphe g. C'est sans doute le plus simple si c'est possible puisque g est déjà créé.
Voici alors l'algorithme complet réel d'un parcours en profondeur sur un graphe orienté :
Algorithme du parcours en profondeur (sur un graphe orienté)
Remarque : on peut l'utiliser également sur un graphe non orienté mais on ne gagnera en réalité pas d'informations supplémentaires par rapport à la version sans date de l'activité précédente.
ENTREES
- Un graphe noté g
SORTIE
Aucune ici mais on peut facilement modifier l'algorithme pour qu'il renvoie par exemple l'Arbre ou la Forêt du parcours. En réalité ici, on stocke l'arbre directement via les sommets : on leur attribue un parent.
ALGORITHME PARCOURS EN PROFONDEUR
on initialise le compteur d'étapes du graphe
g.date ← 0
on initialise tous les sommets
POUR chaque sommet u appartenant au graphe g
u.couleur ← BLANC
u.parent ← VIDE
u.debut ← 0
u.fin ← 0
Fin Pour
on lance le traitement des sommets un par un
POUR chaque sommet u appartenant au graphe g
SI u.couleur est BLANC
si on arrive ici, c'est que le sommet n'a pas encore été découvert
visiter_en_profondeur(u, g)
Fin Si
Fin Pour
Renvoyer VIDE (∅)
ALGORITHME de visiter_en_profondeur(u, g)
g.date ← g.date + 1
u.debut ← g.date
u.couleur ← GRIS
POUR chaque sommet v de la liste d'adjacence du sommet u
SI v.couleur est BLANC
si on arrive ici, c'est que le sommet n'a pas encore été visité
v.parent ← u.
visiter_en_profondeur(v, g)
Fin Si
Fin Pour
ici, tous les sommets adjacents ont été tentés
g.date ← g.date + 1
u.fin ← g.date
u.couleur ← NOIR
Renvoyer VIDE (∅)
Avant d'utiliser les nouvelles informations que nous allons obtenir, voyons ce que nous obtenons sur un exemple de parcours : les informations debut et fin apparaissent à gauche et à droite du noeud dans l'Arbre de parcours obtenu (et au dessus du sommet dans la liste des sommets).
3 - Détection des cycles dans un graphe orienté
Voyons comment détecter les cycles à l'aide d'un parcours en profondeur.
Comme vous le voyez, on obtient donc maintenant beaucoup plus d'informations. Voici les mêmes informations représentées sous forme chronologique : les étapes vers la droite et l'ordre de découverte vers le bas.
Avec un peu de réflexion, on se rend compte que les dates suffisent : elles permettent de retrouver si besoin l'ordre de découverte (et cet ordre ne sert à rien en soi). Voici donc le graphique que nous allons utiliser pour raisonner :
On notera U l’intervalle du sommet u et V l’intervalle du sommet v.
Pour l'instant, notre exploration des graphes est très incomplète : on n'a sélectionné que certains arcs et nous en avons supprimé beaucoup : avec notre forêt, on pourrait croire que depuis les sommets S7 et S8 on ne peut pas joindre le reste du graphe.
Arcs de liaison : on descend d'un niveau exactement
Les arcs en noir sont nommés les arcs de liaison : ce sont les arcs qu'on a utilisé pendant le parcours en profondeur : on est entré la première fois dans ce sommet par ce arc.
Ces arcs sont ceux qui caractérisent l'Arbre de parcours obtenu. Un Arc de liaison fait donc descendre exactement d'un niveau dans l'Arbre de parcours : il relie un sommet parent à son enfant direct.
Exemples : (S6, S3), (S1,S4), (S2,S5)...
Comment le programmme peut-il les détecter ?
Un arc (u,v) est un arc de liaison si u est le parent du sommet v dans l'Arbre de parcours. Seul le lien de parenté importe.
05° Pourquoi l’arc (S8,S7) n’est-il pas un arc de liaison sur ce parcours ?
...CORRECTION...
S8 n'est pas le père de S7 sur l'Arbre de parcours : on découvre S8 en venant de S7 et pas l'inverse.
05-b° Que deviendrait l’arc (S8,S7) dans le cas où on commencerait l’exploration par S8 par exemple ?
...CORRECTION...
Puisque la liste d'adjacence de S8 est [S6,S7], on commencerait l'exploration en partant d'abord vers S6. On lance donc l'exploration de toute la partie de gauche. Mais on ne pourrait pas découvrir S8 depuis S6.
Après avoir passé S6 en NOIR, on reviendrait donc en S8 pour tester l'arc (S8, S7) : S7 étant encore BLANC dans ce cas, cet arc deviendrait un arc de liaison.
05-c° La dénomination des arcs est-elle dépendante ou indépendante du choix de l’ordre des sommets dans un graphe quelconque ?
...CORRECTION...
La classification des arcs dépend des sommets qu'on explore en premier. Un arc peut changer de classification si on change l'ordre des découvertes : la forêt obtenue change.
Nous allons donc maintenant voir comment savoir si l'un des arcs grisés provoque un cycle ou pas. De cette façon, nous pourrons garder certains arcs en gris : ceux qui ne provoqueront pas de cycle en venant de S6.
Arc S4 vers S2
Cet Arc là ne doit pas être visité en venant de S6 : il provoque un retour en arrière car S2 est un ancêtre de S4.
Arcs arrière : on remonte d'un ou plusieurs niveaux
Les arcs arrière sont les arcs qui relient un sommet à l'un de ces ancêtres dans l'Arbre de profondeur. Ils permettent de revenir en arrière dans le parcours et de créer un cycle.
Ainsi venant de S6, on voit qu'emprunter (S4,S2) crée un cycle puisqu'on repasse nécessairement par le sommet S2 que nous avons forcément déjà traversé en venant de S6.
Comment le programme peut-il les détecter ?
Un arc (u,v) est un arc arrière si l'intervalle du sommet u de départ est inclus dans l'intervalle du sommet v de destination. On remonte donc vers un ancêtre.
U ⊂ V
Exemple : (S4, S2).
06-a° Que peut-on dire de l'intervalle [5;6] du sommet de départ S4 par rapport à celui [3;10] du sommet de destination S2 ?
- [5; 6] ⊂ [3;10]
- [3;10] ⊂ [5; 6]
- [5; 6] ∈ [3;10]
- [3;10] ∈ [5; 6]
...CORRECTION...
- [5; 6] ⊂ [3;10] : oui, l'intervalle [5;6] est inclus dans [3;10]
- [3;10] ⊂ [5; 6] : faux
- [5; 6] ∈ [3;10] : faux, appartient est utilisé pour désigner un élément appartenant à un ensemble et pas un ensemble par rapport à un autre ensemble.
- [3;10] ∈ [5; 6] : faux
06-b° Existe-il d'autres arcs arrière sur ce parcours en profondeur ?
...CORRECTION...
Trouver les chemins disponibles via la détection des cycles dans un graphe orienté AVEC les dates
Si on cherche naïvement les chemins disponibles dans un graphe, l'utilisation d'un cycle engendre en machine une infinité de solutions : on tourne une fois, on tourne deux fois...
Comment éviter les cycles ?
- un graphe possèdant un arc arrière contient au moins un cycle.
- un graphe ne possèdant pas d'arc arrière ne contient pas de cycle.
Eviter les cycles revient donc à supprimer les arcs arrière lors du déplacement dans le graphe.
07° Dessiner le graphe simplifié où les arcs arrière sont supprimés mais tous les autres sont utilisables.
...CORRECTION...
08° Ecrire les 4 chemins partant de S6 en menant à un "cul de sac" : vous n'avez bien entendu pas le droit d'utiliser un arc arrière. Vous pouvez par contre utiliser les arcs grisés.
1er chemin : S6 - S3 - S2 - S1 - S4
...
...CORRECTION...
- S6 - S3 - S2 - S1 - S4
- S6 - S3 - S2 - S5 - S4
- S6 - S3 - S5 - S4
- S6 - S5 - S4
09° Utiliser le graphe simplifié pour fournir tous les chemins explorables dans ce graphe partant de S7 sans réaliser de cycle. Pensez à utiliser la réponse à la question 07...
...CORRECTION...
Il suffit d'explorer le graphe en partant de S7 et en se dirigeant vers le bas à chaque fois.
Deux manières de rejoindre "l'étape S6" : S7 vers S6 ou S7 vers S8 vers S6.
On obtient donc le double de possibilités par rapport à la question 07.
- S7-S6-S3-S2-S1-S4
- S7-S6-S3-S2-S5-S4
- S7-S6-S3-S5-S4
- S7-S6-S5-S4
- S7-S8-S6-S3-S2-S1-S4
- S7-S8-S6-S3-S2-S5-S4
- S7-S8-S6-S3-S5-S4
- S7-S8-S6-S5-S4
10° Imaginons que chacun des sommets représente les pièces d'un jeu où on peut perdre ou gagner des pièces d'or.
- S7 : +50 po
- S8 : + 10 po
- S6 : - 20 po
- S3 : + 50 po
- S2 : - 10 po
- S5 : + 20 po
- S1 : + 40 po
- S4 : - 20 po
Par quel chemin passer ?
...CORRECTION...
Il suffit d'explorer le graphe en partant de S7 et en se dirigeant vers le bas à chaque fois.
On voit immédiatement que le chemin passant par S8 ne peut qu'être positif par rapport au chemin se dirigeant directement vers S6.
- S7-S8-S6-S3-S2-S1-S4 : 100 po
- S7-S8-S6-S3-S2-S5-S4 : 80 po
- S7-S8-S6-S3-S5-S4 : 90 po
- S7-S8-S6-S5-S4 : 40 po
Le premier chemin est donc préférable ici.
Trouver les chemins disponibles via la détection des cycles dans un graphe orienté SANS les dates
On peut trouver la nature des arcs au fur et à mesure de l’exploration, sans les dates :
Lors de l'exploration, si :
- on teste un arc menant à un sommet BLANC, il s'agit d'un arc de liaison : on le mémorise.
- on teste un arc menant à un sommet GRIS, il s'agit d'un arc arrière : on ne le mémorise pas (ou on mémorise qu'on ne doit pas l'emprunter).
- on teste un arc menant à un sommet NOIR, il s'agit d'autres types d'arcs. On peut juste dire qu'il ne s'agit ni d'un arc arrière, ni d'un arc de liaison.
Mais il faudra mémoriser sa nature dans une nouvelle structure de données gérant les arcs.
Dans ce cours, j'ai préféré utiliser les dates mais on pourrait modifier les listes d'adjacence pour y intégrer une information supplémentaire sur la nature de l'arc. On la place à 'ok' initialement et on change à 'arrière' si on détecte un arc arrière.
Exemple avec le sommet S2 :
- Plutôt que de stocker [1,5] dans la liste d'adjacence de S2,
- on pourrait ainsi stocker [(1,'ok'), (5, 'ok')]
- qui deviendrait [(1,'ok'), (5, 'ok')] à la fin du parcours en profondeur.
De la même façon, celle de S4 passerait de [(2, 'ok')] à [(2, 'arrière')].
11° Utiliser l'animation du parcours en profondeur sur ce graphe orienté. A quel moment détecte-t-on le premier arc arrière uniquement graçe à la couleur du sommet de destination ? Ce graphe contient-il des cycles ?
...CORRECTION...
On détecte le premier arc arrière au moment du test de l'arc (S4,S2) : il mène au sommet S2 déjà GRIS.
Puisqu'on vient de détecter un arc arrière, ce graphe contient au moins un cycle.
Conclusion
Pour visiter tous les chemins disponibles à partir d’une « racine » sans risque de tourner en rond, il suffit d’éviter les arcs arrière en les détectant :
- soit avec les dates stockées dans les sommets
- soit avec la couleur du sommet-destination des arcs lors du parcours initial en profondeur
4 - Affiner la connaissance des chemins avec les dates
Qu'apportent les dates alors ?
La datation permet de distinguer deux autres types d'arcs, ceux qui ne sont ni des arcs de liaison, ni des arcs arrière. Nous allons voir :
- les arcs avant : les arcs permettant de descendre plus rapidement dans l'Arbre de parcours obtenu. Une sorte de raccourci.
- les arcs transverse : les arcs qui relient des sommets dont aucun des deux n'est l'ancêtre de l'autre.
L'utilisation des dates permet donc d'apporter des informations supplémentaires sur la structure de la Forêt de parcours obtenue.
Regardons maintenant comment caractériser les autres arcs, ceux qui ne sont ni des arcs de liaison, ni des arcs arrière.
Arcs avant : on descend de plus d'un niveau
Les arcs avant sont les arcs (u,v) reliant un sommet-départ u à l'un de ses descendants v dans l'arbre, sans que v ne soit le fils de u.
L'arc (S6, S3) est juste un arc de liaison car S6 est le parent direct de S3.
L'arc (S6, S5) est un arc avant puisqu'il permet de joindre S5 plus rapidement qu'en passant par S3.
Comment le programme peut-il les détecter ?
Un arc (u,v) est un arc avant si
- l'intervalle du sommet-destination v est inclus dans l'intervalle du sommet-départ u.
- u n'est pas le parent de v (ça c'est un arc de liaisons)
V ⊂ U
u ≠ v.parent
Ici l'intervalle [8;9] de S5 est bien inclus dans l'intervalle [1;12] de S6 sans que S6 ne soit le parent de S5.
12° Trouver les autres arcs avant présents dans le parcours en profondeur proposé :
...CORRECTION...
Le seul autre arc avant est l'arc (S3,S5).
L'intervalle [8;9] de S5 est bien inclus dans l'intervalle [2;11] de S3 sans que S3 ne soit le parent direct de S5.
Arcs transverse : les liaisons entre sommets sans relation d'ancêtre-descendance
On y trouve donc les derniers arcs.
L'arc (S5,S4) est un exemple d'arc transerve entre sommet d'un même Arbre de parcours.
L'arc (S7,S6) est un exemple d'arc transerve entre sommet de deux Arbres différent de la Forêt de parcours.
Comment le programme peut-il les détecter ?
Un arc (u,v) est un arc transverse si les intervalles des sommets u et v sont disjoints, c'est à dire qu'ils n'ont pas de dates communes.
U ∩ V = ∅
[8;9] de S5 est bien disjoint avec [5;6] de S4.
[13;16] de S7 est bien disjoint avec [1;12] de S6.
Trouver un chemin dans un graphe
A partir de cette recherche, basée sur un départ supposé de S6, nous sommes capables d'obtenir les chemins sans cycle reliant les différents sommets.
Il suffit pour cela de simplifier le graphe en interdisant l'utilisation des arcs arrière mais en autorisant tous les autres.
Vous pouvez voir, à gauche, le graphe simplifié après suppression des arcs arrière.
A droite, une autre représentation du même graphe en utilisant le squelette de la forêt de parcours initial. Attention, le rajout des arcs avant et transverse sur la Forêt de parcours la transforme en graphe puisque certains noeuds de l'arbre peuvent mainteant avoir plusieurs parents : S4 ou S6 par exemple. Ce ne sont donc plus des noeuds d'Arbre mais des sommets de Graphe.
L'association des informations trouvées lors du parcours nous permet néanmoins d'affirmer que, sur ce parours, le sommet S7 est un peu particulier puisqu'il est le seul sommet n'ayant pas de prédecesseur : la forme de droite correspond à ce qu'on peut nommer un tri topologique : on trace l'ordre dans lequel on doit nécessairement visiter les sommets pour partir du sommet et atteindre le fond. Remplacer les sommets par les étapes de résolution d'un problème (construire un immeuble ?) et vous aurez compris qu'on aurait ici plusieurs manières de résoudre le problème (on voit que lors de la construction, certaines étapes que nous avions iniitialement prévues ne sont pas forcément utiles puisqu'on peut les contourner et aboutir à la même situation finale !).
Il faut néanmoins bien comprendre que les deux formes sont similaires et représentent bien le même parcours dans ce graphe simplifié.
Résumé sur les arcs et le parcours en profondeur d'un graphe orienté
On notera U l’intervalle du sommet u et V l’intervalle du sommet v.
| Type d'arc | Détection avec dates | Détection sans date |
|---|---|---|
| Arc de liaison (u,v) | u est le parent de v. u = v.parent |
L'arc mène vers un sommet BLANC |
| Arc arrière (u,v) | L'intervalle de u est inclus dans celui de v U ⊂ V |
L'arc mène vers un sommet GRIS |
| Arc avant (u,v) | u n'est pas le parent de v ET l'intervalle de v est inclus dans celui de u V ⊂ U u ≠ v.parent |
L'arc mène vers un sommet NOIR (mais c'est le cas d'un arc transverse aussi) |
| Arc transverse (u,v) | Les intervalles de v et u sont disjointsbr> U ∩ V = ∅ |
L'arc mène vers un sommet NOIR (mais c'est le cas d'un arc avant aussi) |
5 - Détection des cycles dans un graphe non orienté
Sur un graphe non orienté, difficile de séparer une arête arrière d'une arête avant puisqu'on peut suivre l'arête dans le deux sens. Or, soit on autorise l'accès à une arête (dans les deux sens), spot on n'en autorise pas l'accès (dans les deux sens).
Un graphe non orienté ne possède que des arêtes DE LIAISON et des arềtes ARRIERE.
Le choix de la classification d'une arête se fait simplement lors de sa première utilisation.
13° Utiliser l'animation du parcours en profondeur sur ce graphe non orienté. Tracer les intervalles. Trouver les arcs arrière. En déduire s'il existe des cycles dans ce graphe non orienté.
...CORRECTION...
14° Tracer les intervalles obtenus sur ce parcours. Trouver les arcs arrière. En déduire s'il existe des cycles dans ce graphe non orienté.
...CORRECTION...
Détection des cycles dans un graphe non orienté
Un parcours sur un graphe non orienté ne possède que
- des arêtes de liaison ou
- des arêtes arrière.
Dans un graphe non orienté, l'arête va être empruntée dans les deux sens pendant le parcours (contrairement à un arc qui n'est emprunté que dans un seul sens). On considère que l'arête est du type correspondant au premier type rencontré :
- Lors de la première utilisation de l'arête dans le parcours, l'arête mène à un sommet BLANC : c'est une "arête de liaison".
- Lors de la première utilisation de l'arête dans le parcours, l'arête mène à un sommet GRIS : c'est une "arête arrière" et on vient de détecter un cycle.
Comme il va falloir ne tenir compte que du premier passage, il faudra mémoriser le passage. Donc, autant utiliser l'algorithme en profondeur avec datation.
Par contre, si vous utilisez l'algorithme dans votre tête, la couleur de la première utilisation en utilisant votre cerveau pour mémoriser suffit.
15° Utiliser l'animation du parcours en profondeur sur ce graphe non orienté. En tant qu'humain, à quel moment détecte-t-on la première arête arrière ? Ce graphe contient-il des cycles ?
...CORRECTION...
Voici le moment où on détecte la première fois la présence d'une arête arrière et donc la présence de cycle : on emprunte l'arête reliant S2 et S3 pour la première fois et on obtient un sommet destination GRIS.
Attention : ce n'est PAS cette étape : nous avons déjà emprunté l'arête dans le sens (S1,S2) et l'arête a alors été déclarée de liaison. Le deuxième passage dans le sens (S2,S1) mène à un sommet GRIS mais cela ne change rien : le type "liaison" a déjà été attribué.
Résumé sur les arcs et le parcours en profondeur d'un graphe non orienté
| Type d'arc | Détection avec dates | Détection sans date (1er utilisation de l'arête) |
|---|---|---|
| Arête de liaison {u,v} | u est le parent de v. u = v.parent |
L'arête mène vers un sommet BLANC |
| Arête arrière {u,v} | L'intervalle de u est inclus dans celui de v U ⊂ V |
L'arc mène vers un sommet GRIS |
Finissons avec un complément totalement optionnel pour voir qu'on utilise bien les arêtes dans les deux sens. Si vous avez le temps.
On peut bien entendu se passer des dates mêmes avec un ordinateur mais il faudra trouver un moyen de mémoriser les passages d'une façon ou d'une autre pour ne tenir compte que du premier.
Ou alors, il faudra veuiller à parvenir à caractériser l'arête correctement la deuxième fois également :
La détection des cycles devient : lors de l'exploration, si
- l'arête mène à un sommet BLANC : c'est une "arête de liaison" rencontrée pour la première fois.
- l'arête mène à un sommet GRIS mais qui est le parent du sommet de départ : c'est une "arête de liaison" rencontrée dans l'autre sens.
- l'arête mène à un sommet GRIS sans que la destination ne soit le parent du sommet de départ : c'est une "arête arrière" rencontrée pour la première fois.
- l'arête mène à un sommet NOIR : c'est une "arête arrière" rencontré pour la deuxième fois.
| Type d'arc | Détection sans date (1er utilisation de l'arête) |
Détection sans date (2e utilisation de l'arête) |
|---|---|---|
| Arête de liaison {u,v} | L'arête mène vers un sommet BLANC | L'arête mène vers un sommet GRIS qui se trouve être le parent de u |
| Arête arrière {u,v} | L'arc mène vers un sommet GRIS qui n'est pas le parent de u | L'arc mène vers un sommet NOIR |
Comme vous le voyez, autant utiliser les dates ou un autre système qui ne catégorise l'arête que la première fois qu'on la rencontre.
16° Que peut-on dire de l'arête (S1,S3) lors de sa première utilisations ? lors de sa deuxième utilisation ?
...CORRECTION...
Première utilisation : S1 n'est pas le parent de S3. Or la destination est GRIS : il s'agit donc d'une arête arrière.
Deuxième utilisation : la destination est NOIR : il s'agit donc toujours d'une arête arrière.
17° Que peut-on dire de l'arête (S2,S3) lors de sa première utilisations ? lors de sa deuxième utilisation ?
...CORRECTION...
Première utilisation : la destination est BLANC : il s'agit donc d'une arête de liaison.
Deuxième utilisation : la destination S2 est GRIS mais S2 est le parent de S3 : il s'agit donc toujours d'une arête arrière.
6 - FAQ
Arcs arrière ou arrières
On écrit arcs arrière sans accord car ils font opposition aux arcs avant.
De la même façon, on note arcs tranverse et pas arcs transverses.
Avant, arrière et transverse font référence à une direction et ne sont pas des adjectifs ici.
Activité publiée le 09 05 2021
Dernière modification : 09 05 2021
Auteur : ows. h.