Üres gráf

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

Nulladrendű gráf (nullgráf)
Csúcsok száma0
Élek száma0
Derékbőség ∞ {\displaystyle \infty }
Kromatikus szám0
Élkromatikus szám0
Automorfizmusok1
Génusz0
Spektrum0
EgyébEgész spektrumú
Szimmetrikus
Jelölés K 0 {\displaystyle K_{0}}

A K 0 {\displaystyle K_{0}} 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 K 0 {\displaystyle K_{0}} -t nem tekintik gráfnak. Az, hogy a K 0 {\displaystyle K_{0}} -t érvényes gráfnak tekintik-e, általában a kontextuson múlik. A pro érvek közé tartozik, hogy a K 0 {\displaystyle K_{0}} 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 K 0 {\displaystyle K_{0}} 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 K 0 {\displaystyle K_{0}} 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 K 0 {\displaystyle K_{0}} , ahogy a K 1 {\displaystyle K_{1}} (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 K 0 {\displaystyle K_{0}} mérete nulla, megegyezik komplementerével, K 0 ¯ {\displaystyle {\overline {K_{0}}}} -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 K 0 {\displaystyle K_{0}} -t.

Élmentes gráf

Élmentes gráf (üres gráf, nullgráf)
Csúcsok száman
Élek száma0
Sugár0
Átmérő0
Derékbőség ∞ {\displaystyle \infty }
Kromatikus szám1
Élkromatikus szám0
Automorfizmusokn!
Génusz0
EgyébEgész spektrumú
Szimmetrikus
Jelölés K ¯ n {\displaystyle {\overline {K}}_{n}}

Bármely n természetes számhoz tartozik egy n rendű K ¯ n {\displaystyle {\overline {K}}_{n}} é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 K ¯ n {\displaystyle {\overline {K}}_{n}} jelölés onnan ered, hogy az n-csúcsú élmentes gráf éppen a K n {\displaystyle K_{n}} teljes gráf komplementere..

Kapcsolódó szócikkek

Jegyzetek

  1. ↑ a b Weisstein, Eric W.: Empty Graph (angol nyelven). Wolfram MathWorld
  2. ↑ a b Weisstein, Eric W.: Null Graph (angol nyelven). Wolfram MathWorld
  • 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.