Érintőgráf
A matematika, azon belül a gráfelmélet területén egy érintőgráf (tangency graph) vagy kontaktgráf (contact graph) olyan gráf, melynek csúcsai mértani objektumoknak (pl. görbék, egyenes szakaszok vagy sokszögek), élei pedig ezen objektumok valamilyen értelemben vett érintkezésének feleltethetők meg.

Ismert, hogy a síkgráfoknak többféle mértani reprezentációja létezik, pl. előállíthatók körlapok, háromszögek – vagy a páros gráfok esetében – függőleges és vízszintes egyenes szakaszok érintőgráfjaiként is.

A szakirodalom nagy terjedelemben foglalkozik a síkgráfok kontaktgráfként való előállításával. Az egyik korai eredmény Koebe 1936-ban született tétele, mely szerint minden síkgráf előállítható egymást érintő körlapok segítségével (tehát, hogy minden síkgráfnak létezik érmegráf-reprezentációja).

Példák érintőgráfokra
 Háromszög-érintőgráfok
 Körlap-érintőgráfok (érmegráfok)
 (négyzet alapú) téglatest-érintőgráfok
 T-érintőgráfok (a csúcsok tengely-igazított T alakok, az élek a T-k közötti érintkezéseket jelzik)
 (egyenlő szárú) L-érintőgráfok (a csúcsok tengely-igazított L alakok, az élek az L-ek közötti érintkezéseket jelzik); minden L-reprezentációhoz tartozik vele ekvivalens reprezentáció, ahol az L-ek szárai egyenlő hosszúságúak.

Érintőgráfokkal kapcsolatos eredmények
Koebe–Andreev–Thurston-féle körpakolási tétel:
a körlapok érintőgráfjai pontosan a síkgráfok. Számos alkalmazása van a gráfelméletben, a gráflerajzolás, hálógenerálás területén, a neuroanatómiában stb.

A tengely-igazított szakaszok kontaktgráfjai (rács-érintőgráfok)) pontosan megegyeznek a síkba rajzolható páros gráfokkal.

A háromszögmentes síkgráfok reprezentálhatók legfeljebb három lépcsőjű töröttvonal-szegmensek érintőgráfjaiként. Megvalósíthatók továbbá tengely-igazított szaakszok, L-alakok és Γ-alakok érintőgráfjaiként is.

A nem tengely-igazított szakaszok érintőgráfjai pontosan azok a síkgráfok, melyekben k csúcshoz mindig legfeljebb 2k − 3 élű feszített részgráf tartozik.

A Schnyder-realizer segítségével konstruálható síkgráfok T-érintőgráfja vagy háromszög-érintőgráfja.

A síkba rajzolható Laman-gráfok reprezentálhatók L-érintőgráfokként, ha az L-alakok mind a négy 90°-ban elforgatott alakja jelen lehet. A síkba rajzolható Laman-gráfok a síkgráfok fontos osztályait tartalmazzák (soros-párhuzamos gráfok, külsíkgráfok, síkba rajzolható 2-fák stb.) és a merevségelmélettel való kapcsolatuk miatt használják őket a strukturális mechanikában, kémiában és fizikában is.

Bármely síkgráf rendelkezik „megfelelő” érintőgráf-reprezentációval egymást érintő téglatesteket (tengely-illesztett dobozokat) felhasználva, egy erősebb állítás szerint pedig bármely síkgráf reprezentálható négyzet alapú hasábok érintőrendszereként. Bármely síkgráfnak létezik (nem szükségképpen „megfelelő”) reprezentációja kockák érintőrendszereként (egy „megfelelő” reprezentációban a téglatestek területe sohasem nulla).

Jegyzetek

Kapcsolódó szócikkek
 Metszetgráf

Gráfcsaládok
A matematika , azon belül a gráfelmélet területén egy érintőgráf ( tangency graph ) vagy kontaktgráf ( contact graph ) olyan gráf , melynek csúcsai mértani objektumoknak ( pl. görbék , egyenes szakaszok vagy sokszögek ) , élei pedig ezen objektumok valamilyen értelemben vett érintkezésének feleltethetők meg . Ismert , hogy a síkgráfoknak többféle mértani reprezentációja létezik , pl. előállíthatók körlapok , háromszögek – vagy a páros gráfok esetében – függőleges és vízszintes egyenes szakaszok érintőgráfjaiként is . A szakirodalom nagy terjedelemben foglalkozik a síkgráfok kontaktgráfként való előállításával . Az egyik korai eredmény Koebeban született tétele , mely szerint minden síkgráf előállítható egymást érintő körlapok segítségével ( tehát , hogy minden síkgráfnak létezik érmegráf-reprezentációja ) . Példák érintőgráfokra Háromszög-érintőgráfok Körlap-érintőgráfok ( érmegráfok ) ( négyzet alapú ) téglatest-érintőgráfok T-érintőgráfok ( a csúcsok tengely-igazított T alakok , az élek a T-k közötti érintkezéseket jelzik ) ( egyenlő szárú ) L-érintőgráfok ( a csúcsok tengely-igazított L alakok , az élek az L-ek közötti érintkezéseket jelzik ) ; minden L-reprezentációhoz tartozik vele ekvivalens reprezentáció , ahol az L-ek szárai egyenlő hosszúságúak . Érintőgráfokkal kapcsolatos eredmények Koebe–Andreev–Thurston-féle körpakolási tétel : a körlapok érintőgráfjai pontosan a síkgráfok . Számos alkalmazása van a gráfelméletben , a gráflerajzolás , hálógenerálás területén , a neuroanatómiában stb . A tengely-igazított szakaszok kontaktgráfjai ( rács-érintőgráfok ) ) pontosan megegyeznek a síkba rajzolható páros gráfokkal . A háromszögmentes síkgráfok reprezentálhatók legfeljebb három lépcsőjű töröttvonal-szegmensek érintőgráfjaiként . Megvalósíthatók továbbá tengely-igazított szaakszok , L-alakok és Γ-alakok érintőgráfjaiként is . A nem tengely-igazított szakaszok érintőgráfjai pontosan azok a síkgráfok , melyekben k csúcshoz mindig legfeljebb −élű feszített részgráf tartozik . A Schnyder-realizer segítségével konstruálható síkgráfok T-érintőgráfja vagy háromszög-érintőgráfja . A síkba rajzolható Laman-gráfok reprezentálhatók L-érintőgráfokként , ha az L-alakok mind a négy-ban elforgatott alakja jelen lehet . A síkba rajzolható Laman-gráfok a síkgráfok fontos osztályait tartalmazzák ( soros-párhuzamos gráfok , külsíkgráfok , síkba rajzolhatófák stb. ) és a merevségelmélettel való kapcsolatuk miatt használják őket a strukturális mechanikában , kémiában és fizikában is . Bármely síkgráf rendelkezik „ megfelelő” érintőgráf-reprezentációval egymást érintő téglatesteket ( tengely-illesztett dobozokat ) felhasználva , egy erősebb állítás szerint pedig bármely síkgráf reprezentálható négyzet alapú hasábok érintőrendszereként . Bármely síkgráfnak létezik ( nem szükségképpen „ megfelelő” ) reprezentációja kockák érintőrendszereként ( egy „ megfelelő” reprezentációban a téglatestek területe sohasem nulla ) . Jegyzetek Kapcsolódó szócikkek Metszetgráf Gráfcsaládok