Toshkent viloyati Chirchiq Davlat pedagogika instituti Aniq fanlar fakulteti

graflar deb ataladi.

G  (V ,U )
graflarni qaraymiz. Bunday graflar chekli

Hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan (ajralgan,


xolis, yalong‘och) uch deb ataladi.
Faqat yakkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va yoylar bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. Uchlari soni m ga teng

bo‘lgan bo‘sh grafni O_m

yoki

N_m kabi belgilash qabul qilingan.

Istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf to‘la graf deb ataladi. Uchlari soni m ga teng bo‘lgan to‘la

graf

K bilan belgilanadi. Ravshanki,

K grafning qirralar soni

_{C 2 } m(m 1)

m
bo‘ladi.

m m ₂

m
Agar orgrafning istalgan ikkita uchini har bir yo‘nalishda tutashtiruvchi faqat bittadan yoy mavjud bo‘lsa, u holda unga to‘la orgraf deb ataladi. Ravshanki, to‘la grafdagi qirralarning har birini ikkita (yo‘nalishlari bir-biriga qarama-qarshi bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. Shuning uchun, to‘la orgrafdagi yoylar soni oriyentirlanmagan to‘la grafdagi qirralar sonidan ikki baravar ko‘pdir, ya’ni uchlari m ta bo‘lgan to‘la orgrafdagi

yoylar soni

2C ²  m(m 1)
bo‘ladi.

Agar grafning uchlariga qandaydir belgilar, masalan, qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi.

1,2,...,m
sonlari mos

Agar

G  (V ,U )
va G' (V ',U ')
graflarning uchlari to‘plamlari, ya’ni V va V '

to‘plamlar orasida uchlarning qo‘shnilik munosabatini saqlaydigan o‘zaro bir

qiymatli moslik o‘rnatish mumkin bo‘lsa, u holda G va G' graflar izomorf graflar

deb ataladi. Bu ta’rifni quyidagicha ham ifodalash mumkin: agar  x,y V va

ularga mos bo‘lgan

x', y'V '
( x  y ,


x'  y') uchun

xy  x' y'
( xy U ,


x' y'U ' )

bo‘lsa, u holda G va G' graflar izomorfdir. Agar izomorf graflardan biri

oriyentirlangan bo‘lsa, u holda ikkinchisi ham, albatta, oriyentirlangan bo‘lishi va ulardagi mos yoylarning yo‘nalishlari ham bir-birlariga mos bo‘lishlari shart.

Graf uchiga insident qirralar soni shu uchning lokal darajasi, yoki,

qisqacha, darajasi, yoki valentligi deb ataladi. Grafdagi a uchning darajasini bilan belgilaymiz.

 (a)

Sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga

olish kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra deb ham, ikkita qirra deb ham hisoblash mumkin. Ravshanki, ajralgan uchning darajasi nolga teng. Darajasi birga teng uch chetki (yoki osilgan) uch deb ataladi. Chetki (osilgan) uchga insident qirra ham chetki (yoki osilgan) qirra deb ataladi.
Agar grafning barcha uchlari bir xil r darajaga ega bo‘lsa, u holda bunday graf r darajali regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki