Représentation de structures sous forme de graphes ################################################## Un graphe simple ================ .. figure:: images/graphe--0.svg :alt: schéma de graphe :align: center :width: 80% graphe orienté simple constitué de nœuds reliés entre eux Graphe orienté, graphe non orienté ================================== .. figure:: images/graphe-non-oriente.svg :alt: schéma de graphe :align: center :width: 80% exemple de graphe non-orienté .. note:: Dans un graphe non orienté, les liaisons ne comportent pas de direction. ---- .. figure:: images/graphe-oriente.svg :alt: schéma de graphe :align: center :width: 80% exemple de graphe orienté .. note:: Dans un graphe orienté, les liaisons comportent une direction, matérialisée ici par des flèches. nœuds et nœud racine ==================== .. figure:: images/graphe--1.svg :alt: schéma de graphe avec labels nœuds et nœuds racines :align: center :width: 80% Le graphe est constitué de « nœuds ». Le nœud d'origine est appelé « nœud racine » ou « racine ». nœuds descendants et ancêtres ============================= .. figure:: images/graphe-ancetres-descendant.svg :alt: schéma de graphe avec labels nœuds descendants et ancêtres :align: center :width: 80% Donné un nœud, en rouge dans l'illustration ci-dessus, tous les nœuds qui précèdent celui-ci sont appelés *nœuds ancêtres*. Tous les nœuds qui lui succèdent sont appelés *nœuds descendants*. nœuds parents et enfants ======================== .. figure:: images/graphe--2.svg :alt: schéma de graphe avec labels nœuds parents et enfants :align: center :width: 80% L'ancêtre direct d'un nœud, en rouge dans l'illustration ci-dessus, est appelé *nœud parent*. Le ou les descendanst directs d'un nœud est ou sont appelés *nœud parent(s)*. En anglais ========== .. list-table:: :header-rows: 1 * - français - anglais * - graphe - graph * - nœud - node * - nœud enfant - child node * - nœud parent - parent node * - nœud ancêtre - ancestor node * - nœud descendant - descendant node