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

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

Egész paraméterek

Valós paraméterek

Sorozatok és polinomok

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

  1. ↑ 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.
  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.

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