2. Элементы теории множеств

Vertex darajasi

daraja (v j ) uchlari v j - bu unga tushadigan qirralarning soni, ya'ni uning muhitidagi cho'qqilar .

G cho'qqilarining maksimal va minimal darajalari  (G) belgilari bilan ko'rsatilgan Va ( G ) mos ravishda:

 (G) = ( G )=

Grafik G=(V,E) uning barcha uchlari darajalari bir xil bo'lsa, muntazam yoki bir jinsli ( r darajasida ) deyiladi . Muntazam grafikning darajasi uning uchlari darajasidir.

Grafik cho'qqilarining darajalari yig'indisi

Tasdiqlash ("qo'l siqish lemmasi")

Grafikning barcha cho'qqilarining yig'indisi qirralarning ikki barobariga teng bo'lgan juft sondir:

Lemmaning talqini: har bir qo'l siqishda ikkita qo'l ishtirok etganligi sababli, qo'l siqishlarning istalgan sonida umumiy qo'l siqish soni juft bo'ladi (bu holda har bir qo'l qo'l siqishda qancha ishtirok etgan bo'lsa, shuncha marta hisobga olinadi).

Natija

Har qanday grafikda toq darajali uchlari soni juft.

Grafik izomorfizmi

Ikkita grafik G 1 va G2 _ Agar ularning cho'qqilari va qirralari to'plamlari o'rtasida shunday birma-bir xaritalash mavjud bo'lsa, ular izomorf bo'ladi , shunda grafiklarning mos qirralari G 1 bo'ladi. va G 2 bu grafiklarning mos keladigan uchlariga tushadi.

Agar G grafigi R n dagi G' geometrik grafigiga izomorf bo'lsa , u holda G ' grafikning R n fazoda geometrik realizatsiyasi deyiladi .

R3 _
R2 _
Hisoblash _ R2 _ hisoblanadi grafikning geometrik amalga oshirilishi _ R3 _

Izomorf grafiklarga misol

Vertex mosligi: v 1  v 2 ',v 2  v 3 ',v 3  v 1 ',v 4  v 4 ',v 5  v 5 ' ;