A matematika, azon belül a gráfelmélet területén egy gráftulajdonság (graph property), gráfparaméter vagy gráfinvariáns (graph invariant) a gráfok olyan jellemzője, amely a gráfok izomorfiájára érzéketlen, csak az adott gráf szerkezetétől függ..
Definíciók Bár a gráfok lerajzolása és reprezentációja a gráfelmélet fontos témakörei, a gráf absztrakt struktúrájának megragadása érdekében a gráftulajdonságok definíció szerint megőrződnek egy gráf összes lehetséges izomorfizmusában. Más szavakkal, ez magának a gráfnak a jellemzője, nem egy konkrét lerajzolásának vagy reprezentációjának.
A „gráftulajdonság” kifejezést általában azokra a jellemzőkre használják, melyek igaz/hamis értéket vehetnek fel, míg az „invariáns” vagy „paraméter” kifejezéseket a kvantitatív jellemzőkre. Például „a gráfnak nincsenek 1 fokszámú csúcsai” egy tulajdonság, míg „a gráf 1 fokszámú csúcsainak száma” egy paraméter.
Formálisabban, egy gráftulajdonság gráfok olyan osztályozása, melyben két izomorf gráf közül vagy mindkettő beletartozik az osztályba, vagy egyik sem tartozik bele. Ezzel egyenértékű megfogalmazás lehetséges az osztály indikátorfüggvényének segítségével, ami igaz értéket rendel az osztályba tartozó gráfokhoz, hamisat pedig a többihez; itt is, két izomorf gráfhoz tartozó értékeknek egyezniük kell. A gráfinvariáns vagy gráfparaméter hasonlóan formalizálható olyan függvényként, melynek értelmezési tartománya a gráfok, értékkészlete pedig akár az egész számok, valós vagy komplex számok, számsorozatok vagy polinomok; de értékük két izomorf gráfra meg kell egyezzen..
A tulajdonságok tulajdonságai Sok gráftulajdonság jól viselkedik a gráfokon definiált természetes részben rendezések vagy előrendezések tekintetében: Egy gráftulajdonság örökletes, ha a P tulajdonsággal rendelkező gráfok minden feszített részgráfja is rendelkezik a P tulajdonsággal. Például a perfektség vagy a merev körűség örökletes tulajdonságok. Egy gráftulajdonság monoton, ha a P tulajdonsággal rendelkező gráfok minden részgráfja is rendelkezik a P tulajdonsággal. Például a párosság vagy a háromszögmentesség monoton tulajdonságok. Minden monoton tulajdonság örökletes, de a fordítottja nem feltétlenül igaz; például a merev körű gráfok részgráfjai nem feltétlenül merev körűek, ezért ez a tulajdonság nem monoton. Egy gráftulajdonság a minorképzés műveletére zárt, ha a P tulajdonsággal rendelkező gráfok minden minorja is rendelkezik a P tulajdonsággal. Például a síkgráfnak levés a minorképzés műveletére zárt. Minden a minorképzés műveletére zárt tulajdonság monoton, de ennek fordítottja nem feltétlenül igaz; például a háromszögmentes gráfok minorjai tartalmazhatnak háromszögeket. Ezek a meghatározások kiterjeszthetők a gráfok tulajdonságairól azok paramétereire is: egy gráfparaméter akkor örökletes, monoton vagy a minorképzés műveletére zárt, ha a paramétert formalizáló, a gráfokat a valós számokra leképező függvényhez tartozó részben rendezés szerint monoton.
Vizsgálták a gráfparaméterek viselkedését a gráfok diszjunkt unió művelete tekintetében is: Egy gráfparaméter additív, ha G és H gráfok esetén a paraméter értéke G és H diszjunkt unióján megegyezik G és H paramétereinek összegével. Például a csúcsok száma vagy az élek száma additív. Egy gráfparaméter multiplikatív, ha G és H gráfok esetén a paraméter értéke G és H diszjunkt unióján megegyezik G és H paramétereinek összegével. Például a Hosoya-index (a párosítások száma) multiplikatív. Egy gráfparaméter maximum tulajdonságú ha G és H gráfok esetén a paraméter értéke G és H diszjunkt unióján megegyezik G és H paraméterei közül a maximálissal. Például a kromatikus szám maximum tulajdonságú. Egy gráfparaméter minimum tulajdonságú ha G és H gráfok esetén a paraméter értéke G és H diszjunkt unióján megegyezik G és H paraméterei közül a minimálissal. Például a δ(G) minimális fokszám minimum tulajdonságú.
A fentieken túl a gráftulajdonságok jellemezhetőek az általuk leírt gráfok típusa szerint: beszélhetünk egyszerű és multigráf-paraméterekről aszerint, hogy megengedjük-e a hurok-, illetve többszörös éleket; beszélhetünk irányítatlan vagy irányított gráfok paramétereiről stb.
A paraméterek értékei A gráftulajdonságot meghatározó függvény érkezési halmaza lehet például: igazságérték, igaz/hamis, a gráftulajdonság indikátorfüggvénye esetén; (nemnegatív) egész szám, például a csúcsok száma vagy a gráf kromatikus száma; valós szám, például a gráf frakcionális kromatikus száma; egész számok sorozata, például a gráf fokszámsorozata; polinom, például a gráf Tutte-polinomja.
Gráfparaméterek és gráfizomorfizmus A könnyen kiszámítható gráfparaméterek segíthetnek a gráfizomorfizmus felismerésében; pontosabban kizárásában, mivel két izomorf gráf paramétereinek meg kell egyezniük, de két megegyező paraméterű gráf nem szükségképpen izomorf egymással.
Egy I(G) gráfinvariáns teljes, ha a G és H gráfnál az I(G) és I(H) egyenlőségéből a gráfok izomorfizmusa is következik. Az ilyen invariáns keresése (a gráfok kanonikalizációja problémája) könnyű megoldást nyújtana a gráfizomorfizmus-problémára. Sajnos általában még a polinom értékű invariánsok sem teljesek. Például a karomgráf és a 4 csúcs között húzódó útgráf kromatikus polinomjai megegyeznek.
Példák Tulajdonságok Összefüggő gráf Páros gráf Síkgráf Háromszögmentes gráf Perfekt gráf Euler-kört tartalmazó gráf Hamilton-kört tartalmazó gráf
Egész paraméterek Rend, a csúcsok száma Méret, az élek száma Az összefüggő komponensek száma Ciklikus rang, az élek, csúcsok és komponensek számának lineáris kombinációja Átmérő, a csúcspárok közti legrövidebb úthosszak közül a legnagyobb Girthparaméter vagy bőség, a legrövidebb kör hossza Csúcsösszefüggőség, a legkisebb lehetséges számú csúcs, melynek eltávolításával a gráf szétesik Élösszefüggőség, a legkisebb lehetséges számú él, melynek eltávolításával a gráf szétesik Kromatikus szám, a legkevesebb szín, amivel a gráf csúcsait színezni lehet anélkül, hogy szomszédos csúcsok színe megegyezzen Élkromatikus szám, a legkevesebb szín, amivel a gráf éleit színezni lehet anélkül, hogy szomszédos csúcsok színe megegyezzen Listakromatikus szám, a legkisebb k, szám, amire a gráf k-listaszínezhető Függetlenségi szám, a legnagyobb független csúcshalmaz elemszáma Klikkszám, a legnagyobb teljes részhalmaz mérete Arboricitás Gráf génusza Oldalszám Hosoya-index Wiener-index Colin de Verdière-gráfinvariáns Boxicity
Valós paraméterek Klaszterezettség Közöttiség-központiság Frakcionális kromatikus szám Algebrai összefüggőség Cheeger-állandó (izoperimetrikus szám) Estrada-index Gráf erőssége Gráf sűrűsége
Sorozatok és polinomok Fokszámsorozat Gráf spektruma A szomszédsági mátrix karakterisztikus polinomja Kromatikus polinom, a -színezések száma függvényében Tutte-polinom, egy kétváltozós függvény, amiben a gráf összefüggőségének jelentős része el van kódolva
Kapcsolódó szócikkek Gráflogika, a gráfok tulajdonságait leíró formális nyelvek egyike Topológiai index, a kémiai gráfelmélet szorosan kapcsolódó fogalma
Jegyzetek
Fordítás
További információk ELTE jegyzet: Gráfparaméterek Laták Ivett: Gráfparaméterek (matematika alapszakos szakdolgozat)
* Kategória:Gráfelmélet