.. _modules__arborescences: arborescences ############# Ce module vise à donner quelques bases simplifiées de compréhension des graphes et de leurs représentations graphiques. Cela dans le but de préparer à la lecture et à la représentation de structures telles que l'arborescence de sites internets et/ou des documents webs. Ce module ne traite pas de la théorie des graphes. .. toctree:: :maxdepth: 1 :caption: index du module : definitions/index.rst sur-le-web/index.rst objectifs ********* prolongements ************* En :ref:`m1105`, La suite logique de ce module est le module :ref:`module-drawio`, logiciel permettant de représenter entre autres des graphes. .. list-table:: Référentiel :header-rows: 1 * - Compréhensions à long terme (comprendre que…) - Objectifs d’Apprentissage (être capable de…) - Connaissances Essentielles (savoir que…) * - Un graphe est un modèle abstrait combinant des éléments et leurs éventuelles liaisons. Cette abstraction peut généralement faire l'objet d'une représentation graphique. - Nommer et définir différents concepts relatifs aux graphes. - Un **graphe** est « un ensemble non vide mais fini de **sommets** (ou **neuds**) combinés à un ensemble d'**arêtes** qui joignent des paires de sommets distincts » [#DSCgraphe]_. * - - - Un **sommet**, aussi appelé nœud, est une abstraction indivisible [#DSCsommet]_. |br| Un sommet peut être lié, par une ou plusieurs **arêtes**, à un ou plusieurs sommets (deux sommets peuvent être liés entre eux par plusieurs arêtes). * - - - Un **sommet** peut recevoir un **label** : un terme ou ensemble de terme désignant le concept représenté par le sommet. * - - - Une **arête** est « une connexion entre deux **sommets** d'un **graphe** » [#DSCarrete]_. Un lien peut être pourvu d'orientation (dans le cas d'un **graphe non orienté**) ou en être dépourvu (dans la cas d'un **graphe orienté**). * - - - Un **graphe non orienté** est un graphe dont toutes les **arêtes** ne possèdent aucune orientation. * - - - Un **graphe orienté** est un graphe dont toutes les **arêtes** possèdent une orientation. * - - - Un graphe sera dit **d'un seul tenant** si pour n'importe quel couple de nœud, et faisant abstraction de l'orientation des arêtes, il existe un chemin reliant lesdits nœuds. * - - - Une suite d'arêtes consécutives dont les sommets extrémités sont les identique est appelé un **cycle**. [#wikipedia-cycle]_ * - - - Une graphe dépourvu de **cycle** est appelé un graphe acyclique. * - Il existe différents types de graphes. - Nommer et définir les différents type de graphes présentés. - Un **arbre** est un graphe acyclique et d'un seul tenant. * - - - Un **arbre enraciné** est un **arbre** dont un des sommets est désigné comme la **racine**. * - - - Une arborescence est un arbre enraciné orienté de telle manière à ce qu'un unique chemin existe depuis la **racine** vers chacun des autres sommets du graphe. * - L'arborescence est un type de graphe qui peut être utilisé pour représenter la structure interne d'un site interne ou d'un document web. - Nommer et définir différents concepts précis relatifs notamment aux **arborescence** - La **racine** est, dans une arborescence, le seul sommet qui n'est pas pointé par une arête. * - - - Dans une arborescence, les **feuilles** sont les sommets qui ne sont associés à aucune arête pointant vers un autre sommet. Ce sont les extrémités de l'arbre. * - - - Dans une arborescence, on parle d'**ascendants** ou **ancêtres** pour désigner, en regard d'un sommet, tous les sommets situés entre ledit sommet et la racine incluse. * - - - Dans une arborescence, on parle de **descendants** pour désigner, en regard d'un sommet, tous les sommets situés entre celui-ci et les extrémités vers lesquelles celui-ci pointe. * - - - Dans une arborescence, on parle **d'enfants** pour désigner les descendant d'un nœud auquel celui-ci est directement connecté. * - - - Dans une arborescence, on parle de **parent** pour désigner l'ascendant d'un nœud auquel celui-ci est directement connecté. * - Dans l'arborescence d'un site internet on représente la structure du site en partant de la page d'accueil - Parcourir un site internet en vue d'en établir la cartographie sous forme d'arborescence - * - - - Il n'est pas nécéssaire de représenter tous les liens entre les pages * - - - Les différentes pages peuvent être représentées par niveau de profondeur (n.0, n.1, n.2) * - L'objectif de la constitution de l'arborescence n'est pas de faire une cartographie complète de toutes les pages du site à un instant t, mais davantage de représenter sa structure. - Reconnaître des pages correspondant à un même modèle. - Il n'est pas nécessaire de représenter plusieurs pages représentant des occurrences d'un même modèle. * - Il est important, lorsque l'on édite une arborescence, d'indiquer des labels informatifs et clairs concernant la nature et l'objet des sommets. - Nommer les sommets d'une arborescence de manière **claire** et **informative**, en précisant la **nature** et l'**objet** de chacun. - * - - - ---- .. rubric:: Notes .. [#DSCgraphe] « *A nonempty but finite set of vertices (or nodes) together with a set of edges that join pairs of distinct vertices.* » Martin, L. (Trans.). (2016). Graph. In A. Butterfield, G. Ekembe Ngondi, & A. Kerr (Eds.), A Dictionary of Computer Science (7th ed.). Oxford University Press. https://doi.org/10.1093/acref/9780199688975.001.0001 .. [#DSCsommet] Ou plus précisemment « *une sous-structure d'une structure de données hiérarchique qui ne peux pas être subdivisée, e.g. un sommet dans un graphe ou arbre.* », « *A substructure of a hierarchical data structure that cannot be further decomposed, e.g. a vertex in a graph or tree.* » Martin, L. (Trans.). (2016). Edge. In A. Butterfield, G. Ekembe Ngondi, & A. Kerr (Eds.), A Dictionary of Computer Science (7th ed.). Oxford University Press. https://doi.org/10.1093/acref/9780199688975.001.0001 .. [#DSCarrete] « *A connection between two vertices of a *graph.* » Martin, L. (Trans.). (2016). Edge. In A. Butterfield, G. Ekembe Ngondi, & A. Kerr (Eds.), A Dictionary of Computer Science (7th ed.). Oxford University Press. https://doi.org/10.1093/acref/9780199688975.001.0001 .. [#DSCarbre] Pour une définition plus complète voire notamment (2016). Tree. In A. Butterfield, G. Ekembe Ngondi, & A. Kerr (Eds.), A Dictionary of Computer Science (7th ed.). Oxford University Press. https://doi.org/10.1093/acref/9780199688975.001.0001 .. [#DSCnode] « Une sous-structure d'une structure de données hiérarchique qui ne peux pas être subdivisée, e.g. un sommet dans un graphe ou arbre. », « A substructure of a hierarchical data structure that cannot be further decomposed, e.g. a vertex in a graph or tree. » (2016). Node. In A. Butterfield, G. Ekembe Ngondi, & A. Kerr (Eds.), A Dictionary of Computer Science (7th ed.). Oxford University Press. https://doi.org/10.1093/acref/9780199688975.001.0001 .. [#wikipedia-cycle] "Cycle (théorie des graphes)." Wikipédia, l'encyclopédie libre. 29 mai 2020, 07:18 UTC. 29 mai 2020, 07:18 . .. |br| raw:: html