Lexique de la théorie des graphes

Ê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 GraphSearch.

Découvrez-en plus sur les applications Graph.

NOTOC 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ément 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.

À 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.

Publications associées (1)

Concepts associés (257)

Cours associés (64)

Séances de cours associées (559)

MOOCs associés (2)

MATH-506: Topology IV.b - cohomology rings

Singular cohomology is defined by dualizing the singular chain complex for spaces. We will study its basic properties, see how it acquires a multiplicative structure and becomes a graded commutative a

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.

MATH-434: Lattice models

Lattice models consist of (typically random) objects living on a periodic graph. We will study some models that are mathematically interesting and representative of physical phenomena seen in the real

Fonctions Trigonométriques, Logarithmiques et Exponentielles

Ce cours donne les connaissances fondamentales liées aux fonctions trigonométriques, logarithmiques et exponentielles. La présentation des concepts et des propositions est soutenue par une grande gamm

Fonctions Trigonométriques, Logarithmiques et Exponentielles

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks

IEEE COMPUTER SOC2022

Algèbre linéaire: base canonique

Explore la base canonique en algèbre linéaire, en se concentrant sur la représentation matricielle, la diagonalisation et les polynômes caractéristiques.

Algèbre linéaire : Diagonalisation

Explore la diagonalisation des matrices et les conditions de diagonalisation exacte, avec des exemples démontrant le processus.

Transformations linéaires : matrices et noyaux

Couvre les transformations linéaires, les matrices, les noyaux et les propriétés des matrices inversible.

Cycle (théorie des graphes)

thumb|Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle. Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).

Graphe de Petersen

Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.

Graphe orienté acyclique

En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.