Concept
Lexique de la théorie des graphes
Concepts associés (127)
Algorithme A*
En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle.
Matrice laplacienne
En théorie des graphes, une matrice laplacienne, ou matrice de Laplace, est une matrice représentant un graphe. La matrice laplacienne d'un graphe G non orienté et non réflexif est définie par : où est la matrice des degrés de G et la matrice d'adjacence de G. Formellement : A la différence de la matrice d'adjacence d'un graphe, la matrice laplacienne a une interprétation algébrique ce qui rend son analyse spectrale fructueuse. Plus précisément la matrice correspond à l'opérateur de diffusion sur le graphe.
Circuit rank
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph (the size of a cycle basis). Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula where m is the number of edges in the given graph, n is the number of vertices, and c is the number of connected components.
Graphe de blocs
vignette|upright=1.4|Un graphe de blocs. En théorie des graphes, une branche des mathématiques combinatoires, un graphe de blocs ou arbre de cliques est un graphe non orienté dans lequel chaque composante biconnexe (ou « bloc ») est une clique. Les graphes de blocs ont été appelés aussi arbres Husimi (d'après Kôdi Husimi), mais ce nom fait plus référence aux graphes cactus, qui sont des graphes dans lesquels chaque composante biconnexe non triviale est un cycle.
Graphe de flot de contrôle
En informatique, un graphe de flot de contrôle (abrégé en GFC, control flow graph ou CFG en anglais) est une représentation sous forme de graphe de tous les chemins qui peuvent être suivis par un programme durant son exécution. Dans un GFC, les sommets du graphe représentent un bloc de base, c'est-à-dire un bout de code d'un seul tenant sans sauts ni cibles de sauts. Les cibles de sauts marquent le début d'un bloc de base, tandis que les sauts en marquent la fin. Les arcs représentent les sauts dans le flot de contrôle.
Algorithme de Kruskal
En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal. On considère un graphe connexe non-orienté et pondéré : chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe.
Théorie topologique des graphes
En mathématiques, la théorie topologique des graphes est une branche de la théorie des graphes . Elle étudie entre autres les plongements de graphes dans des surfaces, les graphiques en tant qu'espaces topologiques ainsi que les immersions de graphes. Un plongement d'un graphe dans une surface donnée, une sphère par exemple, est une façon de dessiner ce graphe sur cette surface sans que deux arêtes se croisent. Un problème fondamental de la théorie topologique des graphes, souvent présenté comme un casse - tête mathématique, est le problème des trois chalets.
Graphe roue
En théorie des graphes, le graphe roue Wn est un graphe d'ordre formé en ajoutant un sommet « centre » connecté à tous les sommets du graphe cycle Cn-1. La notation Wn provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent Wn-1, faisant référence à la longueur du cycle. Pour les valeurs impaires de n, le graphe Wn est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue Wn n'est pas parfait.
Conjecture de Hadwiger
En théorie des graphes, la conjecture de Hadwiger est une conjecture très générale sur les problèmes de coloration de graphes. Formulée en 1943 par Hugo Hadwiger, elle énonce que si le graphe complet à k sommets, noté , n'est pas un mineur d'un graphe , alors il est possible de colorer les sommets de avec couleurs. Hadwiger a prouvé les cas dans le même article qui formule la conjecture. Wagner a prouvé en 1937 que le cas est équivalent au théorème des quatre couleurs, et la démonstration en 1976 par Appel et Haken du théorème des quatre couleurs a donc prouvé en même temps la conjecture de Hadwiger pour le cas .
Multigraph
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. There are 2 distinct notions of multiple edges: Edges without own identity: The identity of an edge is defined solely by the two nodes it connects. In this case, the term "multiple edges" means that the same edge can occur several times between these two nodes.