| Wikipédia en français - L'encyclopé... |
Lexique de la théorie des graphes
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
- 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
(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
. 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
- 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.
| Pour la suite, voir Wikipédia.org… |
© Cet article se sert du contenu de Wikipédia® et est autorisé sous les termes de la Licence de Documentation libre GNU et est distribué sous les termes de la licence Creative Commons Paternité-Partage des Conditions Initiales à l'Identique 3.0 non transposé.
