Collection · Mathématiques
Graphes parfaits
Dans Sciences
17 cartes4 joueurs l'ont commencée
Collection « Graphes parfaits » sur Wikicard : 17 cartes tirées de Wikipédia, dont Théorème de Kőnig (théorie des graphes), Graphe d'intervalles, Graphe cordal. Terminée, elle donne un badge brodé « Brodé », généré pour elle par IA.
Ses cartes
Graphe parfaitRareLe graphe parfait est une notion introduite par Claude Berge en 1960.
Graphe cordalPeu communeUn graphe cordal, il suffit de trouver un ordonnancement d'élimination parfaite, de créer une clique pour chaque sommet v {\displaystyle v} avec les voisins de v {\displaystyle v}…
Théorème de Kőnig (théorie des graphes)Peu communeLe théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i.
Graphe d'intervallesPeu communeUn graphe d'intervalles est le graphe d'intersection d'un ensemble d'intervalles de la droite réelle.
CographePeu communeUn cographe est un graphe simple qui peut-être construit de manière récursive selon les règles suivantes : le graphe à un sommet est un cographe, le complémentaire d'un cographe…
- Théorème des graphes parfaitsPeu communeLe théorème des graphes parfaits (parfois appelé théorème fort des graphes parfaits) est une caractérisation des graphes parfaits par certains sous-graphes exclus (en),…
- Théorème de DilworthPeu communeLe théorème de Dilworth est équivalent au théorème de Kőnig sur les couplages d'un graphe biparti.
Graphe scindéCommuneUn graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable.
Graphe de comparabilitéCommuneUn 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é.
K-arbreCommuneLes k-arbres sont exactement les graphes de largeur arborescente donnée, maximaux au sens que l'on ne peut pas ajouter d'arêtes sans augmenter leur largeur arborescente.
Graphe à distance héréditaireCommuneUn graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les…
Graphe à seuilCommuneUn graphe à seuil est un graphe qui peut être construit, en partant d'un graphe à un seul sommet, par application répétée d'une des deux opérations suivantes : Ajout d'un sommet…
Graphe moulinCommuneLe graphe moulin Wd(k,n) est un graphe non orienté construit, pour deux entiers k ≥ 2 et n ≥ 2, en joignant n copies du graphe complet Kk à un sommet universel partagé.
Graphe trivialement parfaitCommuneUn graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales.
Graphe de blocsCommuneUn graphe de blocs ou arbre de cliques est un graphe non orienté dans lequel chaque composante biconnexe (ou « bloc ») est une clique.
Graphe d'intervalles propreCommuneUn 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.
Graphe ptolémaïqueCommuneGraphe ptolémaïque est un graphe non orienté dont les distances des plus courts chemins entre sommets les plus courtes obéissent à l'inégalité de Ptolémée, qui à son tour a été…
Ouvrez des paquets de cartes tirées de Wikipédia, terminez vos collections pour gagner leur badge brodé, défiez d'autres joueurs en Joute. Gratuit, sans avantage payant.