Gráftulajdonság

Példagráf, a következő tulajdonságokkal: síkgráf, összefüggő, rendje 6, mérete 7, átmérője 3, girthparamétere 3, csúcsösszefüggősége 1, fokszámsorozata <3, 3, 3, 2, 2, 1>

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

Tulajdonságok[szerkesztés]

Egész paraméterek[szerkesztés]

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[szerkesztés]

Sorozatok és polinomok[szerkesztés]

Fokszámsorozat
Gráf spektruma
A szomszédsági mátrix karakterisztikus polinomja
Kromatikus polinom, a $k$ -színezések száma $k$ 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[szerkesztés]

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[szerkesztés]

↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ 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[szerkeszté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[szerkesztés]

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)

[l-1] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ 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.

[2] 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.

[1]

[2]