Illeszkedési gráf
A Papposz-gráf, a Papposz-konfigurációból képezett 18 csúcsú illeszkedési gráf. Az egy betűvel jelölt csúcsok a konfiguráció egy pontjának, a három betűvel jelölt csúcsok a konfiguráció három ponton átmenő egyeneseinek felelnek meg.
Derékbőség	≥ 6
Egyéb

A matematika, azon belül a kombinatorika és gráfelmélet területén illeszkedési gráf, incidenciagráf vagy Levi-gráf (Levi graph vagy incidence graph) alatt egy illeszkedési struktúrához tartozó páros gráf értendő.^[1][2] Egy illeszkedési geometria vagy projektív konfiguráció pontjaiból és egyeneseiből gráfot alkotunk oly módon, hogy a gráf minden csúcsa egy pontnak vagy egyenesnek felel meg, élei pedig a pontok és egyenesek közötti illeszkedéseknek. A Levi-gráf nevet F. W. Leviről kapták, aki 1942-ben írt róluk.^[1][3]

Pontok és egyenesek illeszkedési gráfjai általában legalább 6-os girthparaméterrel (bőséggel) rendelkeznek: bármely 4-kör ugyanazon a két ponton átmenő két egyenesnek felelne meg. Megfordítva, bármely, legalább 6 girthű páros gráf tekinthető egy absztrakt illeszkedési struktúra Levi-gráfjának.^[1] A geometrikai konfigurációk Levi-gráfjai biregulárisak, és minden, legalább 6 bőségű bireguláris gráf tekinthető egy absztrakt konfiguráció Levi-gráfjának.^[4]

Illeszkedési gráfok más incidenciastruktúrákhoz is definiálhatók, például az euklideszi tér síkjai és pontjai közötti illeszkedésekre. Minden illeszkedési gráfhoz tartozik egy ekvivalens hipergráf és vice versa.

• A Desargues-gráf a 10 pontból és 10 egyenesből álló Desargues-konfiguráció Levi-gráfja. MInden egyenesen 3 pont van és minden ponton 3 egyenes megy át. A 3-reguláris, 20 csúcsból álló Desargues-gráf tekinthető a G(10,3) általánosított Petersen-gráfnak vagy az 5,2 paraméterű páros Kneser-gráfnak is.
• A Heawood-gráf a Fano-sík Levi-gráfja. A (3,6)-cage-ként is ismert gráf 3-reguláris és 14 csúcsa van.
• A Möbius–Kantor-gráf az euklideszi síkban egyenes vonalakkal nem lerajzolható, 8 pontból és 8 egyenesből álló Möbius–Kantor-konfiguráció Levi-gráfja. 3-reguláris és 16 csúcsa van.
• A Papposz-gráf a 9 pontból és 9 egyenesből álló Papposz-konfiguráció Levi-gráfja. A Desargues-konfigurációhoz hasonlóan minden egyenesen 3 pont van és minden ponton 3 egyenes megy át. 3-reguláris és 18 csúcsa van.
• A Gray-gráf egy olyan konfiguráció Levi-gráfja, ami 27, R³-beli 3×3×3-as rácspontból és a köztük lévő 27 merőleges egyenesből áll. 3-reguláris és 54 csúcsa van.
• A Tutte–Coxeter-gráf a Cremona–Richmond-konfiguráció Levi-gráfja. A (3,8)-cage-ként is ismert gráf 3-regurláis és 30 csúcsa van.
• A Q₄, azaz a négydimenziós hiperkockagráf a két, kölcsönösen egymásba írt tetraéder pontjai és síkjai által alkotott Möbius-konfiguráció Levi-gráfja.
• A 112 csúcsú Ljubljana-gráf a Ljubljana-konfiguráció Levi-gráfja. Az 56 egyenesből és 56 pontból álló konfigurációban minden egyenesen pontosan 3 pont van, minden ponton pontosan 3 egyenes megy át és bármely két egyenes legfeljebb egy pontban metszi egymást.^[5]

• Ez a szócikk részben vagy egészben a Levi graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• Weisstein, Eric W.: Levi Graph (angol nyelven). Wolfram MathWorld