Diko : graphe parfait

graphe parfait

Catégories

Nom, Number:Sing, Gender:Mas, Nom masculin singulier

Lemme

›

graphe parfait

Informations lexicales

Langue:français, Morpho:min

Informations sémantiques

⊙, source:wiki

polarité

Variantes

›

Graphe parfait

‹

Graphe parfait

Définitions

1. (Théorie des graphes) Graphe pour lequel sont égaux le nombre chromatique de chaque sous-graphe induit, et la taille de la plus grande clique dudit sous-graphe induit.

Un graphe est parfait, si et seulement si, il ne comporte ni trou impair ni antitrou impair : ceci est présumé vrai : ceci est la conjecture du graphe parfait de Berge.

(Mathématiques et sciences humaines, Numéros 158 à 163, École des hautes études en sciences sociales, 2002)

2. 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.

Liens externes

›

dbnary:1-graphe-parfait-nom

•

wiki:graphe parfait

Associations d'idées

[F]

›