Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe (type abstrait)
Résumé
thumb|upright=1.3|Un graphe orienté, dont les arcs et certains sommets sont « valués » par des couleurs.
En informatique, et plus particulièrement en génie logiciel, le type abstrait graphe est
la spécification formelle des données qui définissent l'objet mathématique graphe et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'« abstrait » ce type de données car il correspond à un cahier des charges qu'une structure de données concrète doit ensuite implémenter.
La structure de données abstraite de graphes consiste en un ensemble fini, éventuellement mutable de sommets ou nœuds ou points, avec un ensemble de paires ordonnées ou non de tels éléments Ces paires sont des arêtes, arcs non orientés, ou lignes pour un graphe non orienté, et flèches, arêtes orientées , arcs, ou lignes orientées dans le cas orienté. Les sommets peuvent faire partie de la structure, ou être des entités extérieures, représentées par des entiers ou des références.
Une structure de graphe peut aussi associer, à chaque arête, une « valeur », telle qu'une étiquette ou une valeur numérique (un coût, une capacité, une longueur, etc.). Plus généralement, un graphe peut aussi être donnée par deux ensembles d'objets, un de sommets et un ensemble d'arêtes, muni de deux applications qui, à chaque arête, associent son sommet de départ et son sommet d'arrivée. Cette vision permet d'associer des valeurs à chaque objet (sommet ou arête).
Les opérations de base fournies par une structure de données de graphe G incluent usuellement :
sont_adjacents(G, x, y): teste s'il y a une arête de x à y;
voisins(G, x): liste les sommets qui sont adjacents à x;
ajouter_sommet(G, x): ajoute le sommet x s'il n'y figure pas déjà;
supprimer_sommet(G, x): supprime le sommet x s'il existe;
ajouter_arête(G, x, y): ajoute l'arête de x à y s'il n'y figure pas déjà;
supprimer_arête(G, x, y): supprime l’arête de x à y si elle existe;
retourner_valeur_sommet(G, x): retourne la valeur associée à x;
fixer_valeur_sommet(G, x, v): fixe la valeur de x à v.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.