Théorème flot-max/coupe-minLe théorème flot-max/coupe-min (ou max flow/min cut en anglais) est un théorème important en optimisation et en théorie des graphes. Il stipule qu'étant donné un graphe de flots, le flot maximum pouvant aller de la source au puits est égal à la capacité minimale devant être retirée du graphe afin d'empêcher qu'aucun flot ne puisse passer de la source au puits. Ce théorème est un cas particulier du théorème de dualité en optimisation linéaire et généralise le théorème de Kőnig, le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).
Graph embeddingIn topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Modèle de Barabási-AlbertLe modèle de Barabási–Albert (BA) est un algorithme pour la génération aléatoire de réseaux sans échelle à l'aide d'un mécanisme d'attachement préférentiel. On pense que plusieurs systèmes naturels ou humains, tel que l'Internet, le world wide web, les réseaux de citations, et certains réseaux sociaux sont approximativement sans échelle. Ils contiennent en tout cas quelques nœuds (appelés hubs ou moyeux) avec un degré inhabituellement élevé par rapport aux autres nœuds du réseau.
Community structureIn the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes is densely connected internally. In the particular case of non-overlapping community finding, this implies that the network divides naturally into groups of nodes with dense connections internally and sparser connections between groups. But overlapping communities are also allowed.
Graphe de Ramanujanvignette|Le graphe de Pappus, qui selon les valeurs propres de sa matrice de connexion, est aussi un graphe de Ramanujan. Un graphe de Ramanujan, nommé d'après Srinivasa Ramanujan, est un graphe régulier dont le trou spectral (spectral gap) est presque aussi grand que possible. De tels graphes sont d'excellents graphes expanseurs. Autrement dit, il s'agit d'une famille de graphes où chaque sommet a un même degré (régulier) et où les deux valeurs propres les plus élevées ont une différence presque aussi grande que possible.
Graphe completEn théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note .
Graphe régulierEn théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c'est-à-dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré est appelé un graphe -régulier ou graphe régulier de degré . Un graphe 0-régulier est un ensemble de sommets déconnectés; un graphe 1-régulier a un nombre pair de sommets et est un ensemble d'arêtes déconnectées ou couplage; enfin, un graphe 2-régulier est un ensemble de cycles déconnectés.
Graphe cycleLes graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.
Algorithme gloutonUn algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton.
Tri topologiqueEn théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Soit un graphe orienté avec et . Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6.
