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 . | |
| Notation | |
|---|---|
| Nombre de sommets | |
| Distribution des degrés | régulier de degré |
| 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 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 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].
Exemples[modifier | modifier le code]
Le graphe biparti de Kneser H5,2 est le graphe de Desargues (figure).
Les graphes bipartis de Kneser Hn,1 sont les graphes couronnes.
Propriétés[modifier | modifier le code]
Le graphe biparti de Kneser a sommets. Il est régulier de degré .
Comme le Graphe de Kneser, il est sommet-transitif.
Le graphe biparti de Kneser peut être formé comme une double couverture bipartie (en) du graphe de Kneser en dupliquant chaque sommet et en remplaçant chaque arête par une paire d'arêtes reliant les paires correspondantes de sommets[2].
Voir aussi[modifier | modifier le code]
Références[modifier | modifier le code]
- (en) Ya-Chen Chen, « Kneser graphs are Hamiltonian for n ≥ 3 », Journal of Combinatorial Theory, series B, vol. 80, no 1, , p. 2 (DOI 10.1006/jctb.2000.1969, lire en ligne).
- (en) J. E. Simpson, Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), vol. 85, , p. 97-110.
Lien externe[modifier | modifier le code]
(en) Eric W. Weisstein, « Bipartite Kneser Graph », sur MathWorld
