Concept
Lexique de la théorie des graphes
Concepts associés (127)
Graphe médian
En théorie des graphes, un graphe médian est un type de graphe. Étant donné un triplet de nœuds dans un graphe, les médians de ces sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets. Un graphe médian est un graphe tel que pour tout triplet de nœuds il existe un unique médian. En théorie des graphes, les médians d'un triplet de sommets sont les sommets se trouvant sur les plus courts chemins entre ces sommets. Autrement dit, si est l'ensemble de sommets sur les plus courts chemins entre et , alors l'ensemble des sommets médians est .
Eulerian path
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this: Given the graph in the image, is it possible to construct a path (or a cycle; i.
Homéomorphisme de graphes
En théorie des graphes, une branche des mathématiques, deux graphes et sont homéomorphes si l'on peut obtenir un même graphe en subdivisant certaines de leurs arêtes. Deux graphes sont homéomorphes si et seulement si leurs représentations graphiques usuelles (avec des segments de droites reliant les sommets entre eux) sont homéomorphes au sens que ce mot a en topologie. Subdivision La subdivision d'une arête conduit à un graphe contenant un nouveau sommet et où l'on a remplacé l'arête par deux nouvelles arêtes, et .
Graphe chemin
In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order v_1, v_2, ..., v_n such that the edges are {v_i, v_i+1} where i = 1, 2, ..., n − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2. Paths are often important in their role as subgraphs of other graphs, in which case they are called paths in that graph.
Graphe arête-connexe
En théorie des graphes, un graphe k-arête-connexe est un graphe connexe qu'il est possible de déconnecter en supprimant k arêtes et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k arêtes dont la suppression rende le graphe déconnecté, mais la suppression de k-1 arêtes, quelles qu'elles soient, le fait demeurer connexe. Un graphe régulier de degré k est au plus k-arête-connexe et k-sommet-connexe. S'il est effectivement k-arête-connexe et k-sommet-connexe, il est qualifié de graphe optimalement connecté.
Lemme des poignées de main
vignette|250px|Dans ce graphe, un nombre pair de sommets (les quatre sommets numérotés 2, 4, 5, et 6) a des degrés impairs. La somme des degrés des sommets vaut 2 + 3 + 2 + 3 + 3 + 1 = 14, deux fois le nombre d'arêtes. En théorie des graphes, une branche des mathématiques, le lemme des poignées de main est la déclaration selon laquelle chaque graphe non orienté fini a un nombre pair de sommets de degré impair. Plus trivialement, dans une réunion de plusieurs personnes dont certaines se serrent la main, un nombre pair de personnes devra serrer un nombre impair de fois la main d'autres personnes.
Distance (théorie des graphes)
En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie. Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe. Catégorie:Concept
Graphe d'intervalles propre
Un graphe d'intervalles propre est un graphe d'intervalles possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre. Un graphe d'intervalles propre est nécessairement un graphe sans griffe. Soit un graphe possédant une griffe comme sous-graphe induit. On appelle les quatre sommets de la griffe d'intervalles respectives ,, et tels que le sommet soit celui relié aux trois autres et que . Comme la griffe est un graphe induit, , et ne sont pas voisins dans . On a donc .
Maximum cardinality matching
Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.
Tri topologique
En 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.