Concept
Stable (théorie des graphes)
Concepts associés (39)
Induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges (from the original graph) connecting pairs of vertices in that subset. Formally, let be any graph, and let be any subset of vertices of G. Then the induced subgraph is the graph whose vertex set is and whose edge set consists of all of the edges in that have both endpoints in . That is, for any two vertices , and are adjacent in if and only if they are adjacent in .
Graphe parfait
En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
Problème de la clique
thumb|upright=1.5|Recherche exhaustive d'une 4-clique dans ce graphe à 7 sommets en testant la complétude des C(7,4)= 35 sous-graphes à 4 sommets. En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées.
Clique (théorie des graphes)
thumb|Exemple de graphe possédant une 3-clique (en rouge) : les trois sommets de ce sous-graphe sont tous adjacents deux-à-deux. thumb|Exemple de « biclique » : le graphe biparti complet K3,3. Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents. Une clique maximum d'un graphe est une clique dont le cardinal est le plus grand (c'est-à-dire qu'elle possède le plus grand nombre de sommets).
Vertex cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.
Couplage (théorie des graphes)
En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.
Graphe complémentaire
frame|right|Le graphe de Petersen, à gauche et son complémentaire, à droite. En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple est un graphe simple ayant les mêmes sommets et tel que deux sommets distincts de soient adjacents si et seulement s'ils ne sont pas adjacents dans . Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles. En effet, l'ensemble des sommets de G reste inchangé. Le complémentaire du complémentaire est le graphe original.
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
Graphe biparti complet
En théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque sommet de est relié à chaque sommet de . Si le premier ensemble est de cardinal m et le second ensemble est de cardinal n, le graphe biparti complet est noté . Si m = 1, le graphe complet biparti K1,n est une étoile et est noté .
Graphe cordal
thumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.