Üres gráf

(Nullgráf szócikkből átirányítva)
Ez a közzétett változat, ellenőrizve: 2018. november 12.

A matematika, azon belül a gráfelmélet területén a nullgráf kifejezés utalhat a nulladrendű gráfra vagy bármely élmentes gráfra (melyeket üres gráf néven is említenek).

Nulladrendű gráf

szerkesztés
Nulladrendű gráf (nullgráf)
Csúcsok száma0
Élek száma0
Derékbőség 
Kromatikus szám0
Élkromatikus szám0
Automorfizmusok1
Génusz0
Spektrum0
EgyébEgész spektrumú
Szimmetrikus
Jelölés 

A   nulladrendű gráf az egyetlen, csúcsokkal nem rendelkező gráf (ezért a rendje 0). Mivel nincsenek csúcsai, ezért élei sincsenek. Egyes szerzők (definíció szerint vagy csak praktikus okokból) a  -t nem tekintik gráfnak. Az, hogy a  -t érvényes gráfnak tekintik-e, általában a kontextuson múlik. A pro érvek közé tartozik, hogy a   létezése természetesen következik a gráf fogalmának halmazelméleti megalapozásából (a csúcsok és élek (V, E) rendezett párjai; ebben az esetben mindkét halmaz üres); matematikai bizonyításokban az indukció természetes kiindulópontja, a rekurzívan meghatározott adatstruktúráknál a   szintén hasznos a rekurzió alapeseteként (ha a null fát a nem nulla bináris fa hiányzó éleinek ‘gyerek’ csúcspontjaként kezeljük, bármely nem nulla bináris fának pontosan két gyereke van). A kontra érvek közé tartozik, hogy a   gráfként kezelésével számos gráftulajdonság képletében külön esetként kell kezelni a nullgráfot (például a „számoljuk meg egy gráf erősen összefüggő komponenseit” kifejezésből „számoljuk meg a gráf nemnulla erősen összefüggő komponenseit” lesz, vagy az összefüggő gráf definícióját kell módosítani úgy, hogy kimaradjon belőle a K0). A kivételek elkerülése végett a szakirodalomban gyakran a „gráf” fogalmát úgy értik, hogy „legalább egy csúccsal rendelkező gráf”, ha a kontextus nem enged másra következtetni.[1][2]

A kategóriaelmélet területén a nullgráf, a „gráfok kategóriája” egyes meghatározásaiban a kategória kezdeti objektuma.

A  , ahogy a   (az egy csúccsal és nulla éllel rendelkező gráf) is, a legtöbb alapvető gráftulajdonságnak semmitmondóan eleget tesz. Néhány példa: a   mérete nulla, megegyezik komplementerével,  -lal, erdő, síkgráf. Tekinthető irányítatlan vagy irányított gráfnak vagy akár mindkettőnek; ha irányított, akkor irányított körmentes gráf. Egyszerre teljes gráf és élmentes gráf. Az egyes gráftulajdonságok definíciója azonban függ attól, hogy a kontextusban megengedjük-e a  -t.

Élmentes gráf

szerkesztés
Élmentes gráf (üres gráf, nullgráf)
Csúcsok száman
Élek száma0
Sugár0
Átmérő0
Derékbőség 
Kromatikus szám1
Élkromatikus szám0
Automorfizmusokn!
Génusz0
EgyébEgész spektrumú
Szimmetrikus
Jelölés 

Bármely n természetes számhoz tartozik egy n rendű   élmentes gráf, éltelen gráf (vagy üres gráf), mely az n csúcsból és nulla élből álló gráf. Olyan kontextusban, ahol a nulladrendű gráf nem megengedett, nullgráfnak is nevezik.[1][2]

A   jelölés onnan ered, hogy az n-csúcsú élmentes gráf éppen a   teljes gráf komplementere..

Kapcsolódó szócikkek

szerkesztés
  • Harary, F. and Read, R. (1973), "Is the null graph a pointless concept?", Graphs and Combinatorics (Conference, George Washington University), Springer-Verlag, New York, NY.