Problème de plus court cheminvignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le 'problème de plus court chemin' est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur.
Algorithme de parcours en largeurL'algorithme de parcours en largeur (ou BFS, pour Breadth-First Search en anglais) permet le parcours d'un graphe ou d'un arbre de la manière suivante : on commence par explorer un nœud source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nœuds depuis un nœud source dans un graphe non pondéré (orienté ou non orienté). Il peut aussi servir à déterminer si un graphe non orienté est connexe.
Graph labelingIn the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph G = (V, E), a vertex labelling is a function of V to a set of labels; a graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labelling is a function of E to a set of labels. In this case, the graph is called an edge-labeled graph. When the edge labels are members of an ordered set (e.
Graphe aléatoirevignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme.
Graphe (type abstrait)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.
Boucle (théorie des graphes)In graph theory, a loop (also called a self-loop or a buckle) is an edge that connects a vertex to itself. A simple graph contains no loops. Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges between the same vertices): Where graphs are defined so as to allow loops and multiple edges, a graph without loops or multiple edges is often distinguished from other graphs by calling it a simple graph.
MultigraphIn 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.
Théorie spectrale des graphesEn mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées .
Matrice laplacienneEn 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.
Graphe étoilethumb|upright=3|Les graphes en étoile S3, S4, S5 et S6. En mathématiques, et plus particulièrement en théorie des graphes, une étoile Sk est le graphe biparti complet K1,k. On peut aussi le voir comme un arbre avec un nœud et k feuilles, du moins lorsque k > 1. Enfin, on peut le définir comme un graphe connexe dont tous les sommets sauf un sont de degré 1. Certains auteurs définissent toutefois Sk comme l'arbre à k sommets de diamètre maximal 2. Attention, avec cette définition, une étoile n'a que k − 1 feuilles.
