2. Mantiqiy masalalarni yechishning asosiy usullari

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 topilsa, 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 qirralar
(yoylar) soni n ga qarab belgilanadi va bu holda grafni (m, n) -graf deb ataydilar.
Agar G  (V ,U ) grafda U kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (orientirlanmagan) va faqat yo‘naltirilgan (orientirlangan) qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan (orientirlangan) graf deb ataladi. Orientirlangan graf, qisqacha, orgraf deb ham ataladi.
(a, b)
(a, b)
Qator hollarda orientirlanmagan qirralari ham, orientirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deb ataladi.
Agar G  (V ,U ) grafning (orgrafning) U korteji tarkibida V V to‘plamdan olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel qirralar (yoylar) deb ataladi. Karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi.
Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy), ya’ni grafning (a, a) U elementi sirtmoq deb ataladi. Sirtmoq, odatda,
yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi.
Umumiy holda uchlar to‘plami V va (yoki) qirralar (yoylar, qirra va yoylar) korteji U cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin V to‘plam va U kortej faqat chekli bo‘lgan G  (V ,U ) graflarni qaraymiz. Bunday graflar chekli graflar deb ataladi.
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 Om yoki Nm kabi belgilash qabul qilingan.
Istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz orientirlanmagan graf to‘la graf deb ataladi. Uchlari soni m ga teng bo‘lgan
to‘la graf Km bilan belgilanadi. Ravshanki, Km
grafning qirralar soni
bo‘ladi.
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 orientirlanmagan to‘la grafdagi qirralar sonidan ikki baravar ko‘pdir, ya’ni uchlari m ta bo‘lgan to‘la orgrafdagi
yoylar soni
bo‘ladi.
Agar grafning uchlariga qandaydir belgilar, masalan, 1,2,..., m sonlari mos qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi.
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