Illeszkedési gráf

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
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.
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 Papposz-konfiguráció

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.

Példák[szerkesztés]

Fordítás[szerkesztés]

  • 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.

Jegyzetek[szerkesztés]

  1. a b c Grünbaum, Branko (2006), "Configurations of points and lines", The Coxeter Legacy, Providence, RI: American Mathematical Society, pp. 179–225. See in particular p. 181.
  2. Polster, Burkard (1998), A Geometrical Picture Book, Universitext, New York: Springer-Verlag, p. 5, ISBN 0-387-98437-2, doi:10.1007/978-1-4419-8526-2, <https://books.google.com/books?id=2PtPG4qjfZAC&pg=PA5>.
  3. Levi, F. W. (1942), Finite Geometrical Systems, Calcutta: University of Calcutta.
  4. Gropp, Harald (2007), "VI.7 Configurations", in Colbourn, Charles J. & Dinitz, Jeffrey H., Handbook of combinatorial designs (Second ed.), Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, Florida, pp. 353–355.
  5. Conder, M.; Malnič, A. & Marušič, D. et al. (2002), The Ljubljana Graph, IMFM Preprint 40-845, University of Ljubljana Department of Mathematics, <http://www.imfm.si/preprinti/PDF/00845.pdf>.

További információk[szerkesztés]