Concept
Graphe d'intervalles
Concepts associés (23)
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.
Coloration de graphe
thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.
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.
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.
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).
Graphe de comparabilité
Dans la théorie des graphes, un graphe de comparabilité est un graphe non orienté qui relie les paires d'éléments qui sont comparables les uns aux autres dans un ordre partiel donné. On les trouve aussi sous le nom de transitively orientable graphs, partially orderable graphs, et containment graphs. Les graphes de comparabilité sont des graphes parfaits. Les cographes sont des graphes de comparabilité Les graphes qui sont de comparabilité et dont le complémentaire est aussi de comparabilité sont exactement les graphes de permutations.
Graphe d'intersection
En théorie des graphes, un graphe d'intersection est un graphe représentant les intersections d'une famille d'ensembles. Plus précisément, pour une famille d'ensembles finie donnée, on associe à chaque ensemble un sommet, et deux sommets sont reliés par une arête si les ensembles ont une intersection non nulle. Beaucoup de familles de graphe sont définies par l'intersection d'ensembles géométriques, par exemple des sphères dans le plan, ou des intervalles sur une droite.
Stable (théorie des graphes)
thumb|280px|L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. La taille maximum d'un stable d'un graphe, noté I(G), est un invariant du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G).
Graphe de permutation
En théorie des graphes, un graphe de permutation est un graphe non orienté dont les sommets représentent les éléments d'une permutation, et dont les arêtes relient les paires de sommets qui sont inversés dans la permutation. On peut aussi définir les graphes de permutations de manière géométrique : ce sont les graphes d'intersections de segments dont les extrémités sont sur deux droites parallèles. On définit les graphes de permutation de la manière suivante.
Coloration gloutonne
droite|vignette|upright=1.4| Deux colorations gloutonnes du même graphe couronne pour des ordres différents sur les sommets. La numérotation de droite se généralise aux graphes bicolores à n sommets, et l'algorithme glouton utilise couleurs. Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible.