Graphe biparti de Kneser

Ne doit pas être confondu avec Graphe de Kneser.

Graphe biparti de Kneser
Le graphe de Desargues est le graphe biparti de Kneser ${\displaystyle H_{5,2}}$.
Notation	${\displaystyle H_{n,k}}$
Nombre de sommets	${\displaystyle 2C_{k}^{n}}$
Distribution des degrés	régulier de degré ${\displaystyle C_{n-k}^{k}}$
Nombre chromatique	2
Propriétés	Régulier Biparti Sommet-transitif
modifier

En théorie des graphes, une branche des mathématiques, les graphes bipartis de Kneser ${\displaystyle 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 ${\displaystyle 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^[1].

Le graphe biparti de Kneser H_5,2 est le graphe de Desargues (figure).

Les graphes bipartis de Kneser H_n,1 sont les graphes couronnes.

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

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

Le graphe biparti de Kneser ${\displaystyle H_{n,k}}$ peut être formé comme une double couverture bipartie (en) du graphe de Kneser ${\displaystyle KG_{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^[2].

(en) Eric W. Weisstein, « Bipartite Kneser Graph », sur MathWorld

• Portail des mathématiques