Lexique de la théorie des graphes

Article général Pour un article plus général, voir Théorie des graphes.
Sommaire : Haut - A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A

Acyclique 
graphe ne contenant pas de cycle.
Adjacence 
une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet.
Adjacence 
une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque éléments est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.
Adjacence 
une relation d'adjacence propriété de deux sommets d'être connectés par la même arête (dits sommets adjacents) ou propriété de deux arêtes de présenter une extrémité commune (dites arêtes adjacentes). Également appelé relation de voisinage.
Adjoint 
un graphe adjoint est synonyme de line graph.
Admittance 
autre nom d'une matrice laplacienne.
Aléatoire 
un graphe est aléatoire, ou non déterministe, dès que sa construction fait intervenir des probabilités.
Arbre 
graphe connexe et acyclique. Équivalent à un graphe connexe à sommets et arêtes.
Arbre enraciné ou arborescence 
graphe acyclique orienté où on distingue une racine de degré entrant nul, et où tous les autres sommets sont de degré entrant 1.
Arc 
arête dans un graphe orienté. Autre formulation : couple (ensemble ordonné de deux éléments) de sommets reliés par une arête dans un graphe non orienté.
Arc-transitif 
un graphe G est arc-transitif si son groupe d' automorphismes agit transitivement sur l'ensemble de ses arcs. Étant donné deux arêtes , il existe deux automorphismes et tels que , , et , , , .
Arête 
connexion entre deux sommets et . Dans le cas des graphes orientés on parle d'arc. Le terme « arête » est alors utilisé pour désigner l'ensemble des deux arcs , c'est-à-dire de vers , et , c'est-à-dire de vers . Ne pas confondre avec arête en géométrie.
Arête multiple 
ensemble d'arêtes parallèles relatif à un couple de sommets.
Arête parallèle 
arête ayant pour extrémités les mêmes sommets qu'une autre arête. On parle d'arêtes parallèles.
Arête-transitif 
un graphe est arête-transitif si son groupe d' automorphismes agit transitivement sur l'ensemble de ses arêtes. Autre formulation de la condition : pour tout couple d'arêtes, au moins un automorphisme envoie la première composante sur la seconde. Toutes les arêtes jouent exactement le même rôle à l'intérieur du graphe. Exemple : un graphe complet.
Automorphisme 
isomorphisme d'un graphe sur lui-même. Chaque graphe possède au moins un automorphisme : l'identité. L'ensemble des automorphismes d'un graphe forme un groupe.
Other Languages