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ő.. See in particular p. 181.. 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..
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. 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..
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.
Példák 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, R3-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 Q4, 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..
Fordítás
Jegyzetek
További információk
Kategória:Halmazcsaládok Kategória:Konfigurációk Kategória:Geometriai gráfok