Concept
Graphe dual
Concepts associés (40)
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 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.
Feedback arc set
vignette|Ce graphe orienté n'a pas de circuits: il n'est pas possible de partir d'un sommet quelconque et de revenir à ce même point, en suivant les connexions dans la direction indiquée par les flèches. En théorie des graphes, un graphe orienté peut contenir des circuits, c'est-à-dire des chemins qui reviennent sur leur point de départ. Dans certaines applications, ces circuits sont indésirables, et on cherche à les éliminer pour obtenir un graphe orienté acyclique (souvent abrégé en DAG).
Orientation (graph theory)
In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph). A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.
Polynôme de Tutte
Le polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité. L'importance de ce polynôme provient des informations qu'il contient sur le graphe .
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é.
Forbidden graph characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.
Orientation forte
Une orientation forte est, en théorie des graphes, l'attribution d'un sens à chaque arête d'un graphe non orienté (une orientation) qui en fait un graphe fortement connexe. Par exemple, on peut attribuer une orientation forte à un réseau routier s'il est possible de faire de chaque rue un sens unique sans rendre aucune intersection inaccessible. Le théorème de Robbins caractérise les graphes fortement orientables, qui sont exactement les graphes connexes sans pont.
Steinitz's theorem
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
Acyclic orientation
In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. The chromatic number of any graph equals one more than the length of the longest path in an acyclic orientation chosen to minimize this path length. Acyclic orientations are also related to colorings through the chromatic polynomial, which counts both acyclic orientations and colorings.