Toshkent viloyati Chirchiq Davlat pedagogika instituti Aniq fanlar fakulteti

uchlari, V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi.
Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz.

G  (V ,U )
grafning ta’rifiga ko‘ra, U bo‘sh kortej bo‘lishi ham mumkin.

Agar U bo‘sh bo‘lmasa, u holda bu kortej

(a, b)
( a V ,

b V ) ko‘rinishdagi

juftliklardan tashkil topadi, bunda

a  b
bo‘lishi hamda ixtiyoriy
(a, b)
juftlik U

kortejda istalgancha marta qatnashishi mumkin.

(a,b) U

juftlikni tashkil etuvchi a va b uchlarning joylashish tartibidan

bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash

mumkin. Agar

(a,b)
juftlik uchun uni tashkil etuvchilarning joylashish tartibi

ahamiyatsiz, ya’ni

(a, b)  (b, a)
bo‘lsa,
(a,b)

juftlikka yo‘naltirilmagan

(oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu tartib

muhim, ya’ni

(a, b)  (b, a)
bo‘lsa, u holda
(a,b)
juftlikka yoy yoki yo‘naltirilgan

(oriyentirlangan) qirra deyiladi.


U kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yo yoylari korteji, yoki qirralari va yoylari korteji deb ataymiz.
Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.

G  (V ,U )
graf elementlarining soni (|V |  | U | )ga tengdir, bu yerda G grafning

uchlari soni | V | 0

va | U |
bilan uning qirralari (yoylari) soni belgilangan.

Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida (a,b) ,

yoki ab , yoki

(a;b)
ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi:

masalan, yoy uchun

(a, b)
yoki

(a, b) , qirra uchun

(a, b) , yoy yoki qirra uchun u

(ya’ni uchlari ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda.
Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini

ta’kidlaymiz, ya’ni

(a,b)
va (b, a)
yozuvlar bir-biridan farq qiluvchi yoylarni

ifodalaydi. Agar yoy

(a,b)
ko‘rinishda ifodalangan bo‘lsa, u holda a uning

boshlang‘ich uchi, b esa oxirgi uchi deb ataladi. Bundan tashqari, yoy
(a,b)

ko‘rinishda yozilsa, u haqida a uchdan chiquvchi (boshlanuvchi) va b uchga kiruvchi (uchda tugovchi) yoy deb aytish ham odat tusiga kirgan.

Qirra uchun uning

(a,b)
yozuvidagi harflar joylashish tartibi muhim rol

o‘ynamaydi va a va b elementlar qirraning uchlari yoki chetlari deb ataladi.

Agar grafda yo

(a,b)
qirra, yo
(a,b)
yoy, yoki
(b, a)
yoy topillsa, u holda a

va b uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan uchlar deb aytiladi.
Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga
(yoyga) insident, o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi.
Grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar
(yoylar) deyiladi.
Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi.
Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni m va