Ü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

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.

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

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.

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

Kapcsolódó szócikkek
 Gráfelméleti fogalomtár
 Körgráf
 Útgráf

Jegyzetek

 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.

Gráfcsaládok
Reguláris gráfok
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 A nulladrendű gráf az egyetlen , csúcsokkal nem rendelkező gráf ( ezért a rendje 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 . 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 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 . A jelölés onnan ered , hogy az n-csúcsú élmentes gráf éppen a teljes gráf komplementere . . Kapcsolódó szócikkek Gráfelméleti fogalomtár Körgráf Útgráf Jegyzetek Harary , F. and Read , R. " Is the null graph a pointless concept ? " , Graphs and Combinatorics ( Conference , George Washington University ) , Springer-Verlag , New York , NY. Gráfcsaládok Reguláris gráfok