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.

index du module :

• Définitions
• Réaliser l’arborescence d’un site web

objectifs

prolongements

En m1105, La suite logique de ce module est le module module-drawio, logiciel permettant de représenter entre autres des graphes.

Référentiel

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 » [1].
		Un sommet, aussi appelé nœud, est une abstraction indivisible [2]. 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 » [3]. 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. [6]
		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.

---

Notes

[1]

« 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

[2]

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

[3]	« 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

[4]	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

[5]

« 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

[6]	« Cycle (théorie des graphes). » Wikipédia, l’encyclopédie libre. 29 mai 2020, 07:18 UTC. 29 mai 2020, 07:18 <http://fr.wikipedia.org/w/index.php?title=Cycle_(th%C3%A9orie_des_graphes)&oldid=171423046>.