Gráftulajdonság
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/250px-6n-graf.svg.png)
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.[1]
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.[1] 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.[2]
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.[1]
- 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.[1]
- 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.[1]
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 unó 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.[1]
- 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.[1]
- 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ú.[1]
- 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.[1]
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
- ↑ a b c d e f g h i Lovász, László (2012), "4.1 Graph parameters and graph properties", Large Networks and Graph Limits, vol. 60, Colloquium Publications, American Mathematical Society, pp. 41–42.
- ↑ Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), "3.10 Graph Parameters", Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Springer, pp. 54–56, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
Fordítás
- Ez a szócikk részben vagy egészben a Graph property 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.
További információk
- ELTE jegyzet: Gráfparaméterek Archiválva 2017. március 26-i dátummal a Wayback Machine-ben
- Laták Ivett: Gráfparaméterek (matematika alapszakos szakdolgozat)