Graphe biparti de Kneser

Modèle:Confusion Modèle:Infobox Graphe En théorie des graphes, une branche des mathématiques, les graphes bipartis de Kneser $H_{n,k}$ forment une famille de graphes non orientés définie comme suit :

Soient E un ensemble à n éléments et k un entier inférieur à n. Les sommets du graphe $H_{n,k}$ représentent les sous-ensembles de E à k éléments ou à n − k éléments. Deux sommets sont reliés par une arête lorsque l'un des sous-ensembles qu'ils représentent est inclus dans l'autre.

Exemples

Le graphe biparti de Kneser Modèle:Math est le graphe de Desargues (figure).

Les graphes bipartis de Kneser Modèle:Math sont les graphes couronnes.

Propriétés

Le graphe biparti de Kneser a $2C_k^n$ sommets. Il est régulier de degré $C_k^{n-k}$.

Comme le Graphe de Kneser, il est sommet-transitif.

Le graphe biparti de Kneser $H_{n,k}$ peut être formé comme une Modèle:Lien du graphe de Kneser $K{G}_{n,k}$ en dupliquant chaque sommet et en remplaçant chaque arête par une paire d'arêtes reliant les paires correspondantes de sommets.