Bo'sh grafik - Null graph

In matematik maydoni grafik nazariyasi, atama "null grafik"ga murojaat qilishi mumkin buyurtma -nol grafik, yoki muqobil ravishda har qanday qirrali bo'lmagan grafikaga (ikkinchisi ba'zan "bo'sh grafik" deb nomlanadi).

Buyurtma-nol grafigi

Buyurtma nolinchi grafik (nol grafik)
Vertices	0
Qirralar	0
Atrof	${ displaystyle infty}$
Automorfizmlar	1
Xromatik raqam	0
Xromatik indeks	0
Jins	0
Xususiyatlari	Ajralmas Nosimmetrik Kenglik -1
Notation	${ displaystyle K_ {0}}$
Grafiklar va parametrlar jadvali

The tartib-nol grafigi, ${ displaystyle K_ {0}}$, "no" ga ega noyob grafik tepaliklar (shuning uchun uning tartibi nolga teng). Bundan kelib chiqadiki ${ displaystyle K_ {0}}$ shuningdek yo'q qirralar. Shunday qilib null grafika muntazam grafik nol daraja. Ba'zi mualliflar bundan mustasno ${ displaystyle K_ {0}}$ grafik sifatida ko'rib chiqilishidan (yoki ta'rifi bo'yicha, yoki oddiyroq qulaylik sifatida). Shu jumladan ${ displaystyle K_ {0}}$ chunki to'g'ri grafik foydali bo'lishi kontekstga bog'liq. Ijobiy tomoni, ${ displaystyle K_ {0}}$ odatdagidan tabiiy ravishda amal qiladi nazariy grafik ta'riflari (bu buyurtma qilingan juftlik (V, E) uchun tepalik va chekka o'rnatiladi, V va E, ikkalasi ham bo'sh ), in dalillar uchun tabiiy asos bo'lib xizmat qiladi matematik induksiya va shunga o'xshash tarzda rekursiv ravishda aniqlangan ma'lumotlar tuzilmalari ${ displaystyle K_ {0}}$ rekursiya uchun asosiy holatni aniqlash uchun foydalidir (davolash orqali bekor daraxt sifatida bola nolga teng bo'lmagan nuqsonli qirralarning ikkilik daraxt, har bir null bo'lmagan ikkilik daraxtga ega aniq ikki bola). Salbiy tomondan, shu jumladan ${ displaystyle K_ {0}}$ grafik sifatida ko'plab aniqlangan formulalarni talab qiladi grafik xususiyatlari uchun istisnolarni o'z ichiga oladi (masalan, yoki "barchasini hisoblash" kuchli bog'langan komponentlar grafigi barchasini sanab "aylanadi" bekor emas grafikaning bir-biriga qattiq bog'langan komponentlari "yoki bog'langan grafikalar ta'rifini kiritmaslik uchun o'zgartirish kerak K₀). Bunday istisnolarga ehtiyoj qolmaslik uchun adabiyotlarda bu atama ko'pincha qabul qilinadi grafik "hech bo'lmaganda bitta vertexli grafika" ni anglatadi, agar kontekst boshqacha ko'rsatmasa.^[1][2]

Yilda toifalar nazariyasi, nolinchi tartibli grafik, "grafikalar toifasi" ning ba'zi ta'riflariga ko'ra, boshlang'ich ob'ekt toifasida.

${ displaystyle K_ {0}}$ bajaradi (bo'sh ) xuddi shunday asosiy grafik xususiyatlarining aksariyati ${ displaystyle K_ {1}}$ (bitta vertikali va qirralari bo'lmagan grafik). Ba'zi bir misollar sifatida, ${ displaystyle K_ {0}}$ ning hajmi nol, u unga teng komplekt grafigi ${ displaystyle { overline {K_ {0}}}}$, a o'rmon va a planar grafik. Bu ko'rib chiqilishi mumkin yo'naltirilmagan, yo'naltirilgan yoki hatto ikkalasi ham; yo'naltirilgan deb qaralganda, bu a yo'naltirilgan asiklik grafik. Va bu ikkalasi ham to'liq grafik va chekka bo'lmagan grafik. Shu bilan birga, ushbu grafik xususiyatlarining har biri uchun ta'riflar kontekstning ruxsat berishiga qarab farqlanadi ${ displaystyle K_ {0}}$.

Chegarasiz grafik

Chegarasiz grafik (bo'sh grafik, bo'sh grafik)
Vertices	n
Qirralar	0
Radius	0
Diametri	0
Atrof	${ displaystyle infty}$
Automorfizmlar	n!
Xromatik raqam	1
Xromatik indeks	0
Jins	0
Xususiyatlari	Ajralmas Nosimmetrik
Notation	${ displaystyle { overline {K}} _ {n}}$
Grafiklar va parametrlar jadvali

Har biriga tabiiy son n, chekka bo'lmagan grafik (yoki bo'sh grafik) ${ displaystyle { overline {K}} _ {n}}$ tartib n bilan grafik n tepaliklar va nol qirralar. Nolinchi grafaga ruxsat berilmagan kontekstlarda chekka bo'lmagan grafik ba'zan nol grafika deb nomlanadi.^[1][2]

Bu 0-muntazam grafik Notation ${ displaystyle { overline {K}} _ {n}}$ haqiqatidan kelib chiqadi n-vertex qirrali grafigi to'ldiruvchi ning to'liq grafik ${ displaystyle K_ {n}}$.

Shuningdek qarang

• Grafik nazariyasining lug'ati
• Velosiped grafigi
• Yo'l grafigi

Izohlar

Adabiyotlar

• Xarari, F. va o'qing, R. (1973), "Null grafasi ma'nosiz tushunchami?", Grafika va kombinatorika (Konferentsiya, Jorj Vashington universiteti), Springer-Verlag, Nyu-York, NY.