1. To'plamlar, ularning berilish usullari va ular ustida amallar

Insidentlik matritsalari. Uchlari 1,2,..., m va qirralari u₁,u₂,...,u_n ( n≥1 ) bo’lgan belgilangan graf berilgan bo’lsin. Bu grafning uchlariga satrlari, qirralariga esa ustunlari mos keluvchi va elementlari

ko’rinishida aniqlangan matrisani grafning uchlari insendentlik matrisasi deb ataymiz.
25. Izomorfizm tushunchasi.
Ta’rif. 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.
Bir xil strukturaga ega graf izomarfizm bo`ladi.
Ta’rif . Agar graflarning uchlari to`plami orasida qo`shnilik munosabatini saqlovchi biyeksiya mavjud bo`lsa, bu ikkita graf izomorf deyiladi. G graf G’ grafga izomorf bo`lsa, G=G’ kabi belgilanadi.
Ta’rif. Agar graf o`zining to`ldiruvchisiga izomorf bo`lsa, graf o`zini o`zi
to`ldiruvchi deyiladi.

26. Eyler va Gamilton graflari.
Eyler graflari. Graflar nazariyasining shakllanishi Kyonigsberg ko’priklari
haqidagi masala bilan bog’liq ekanligi yaxshi ma‟lum. L. Eyler 1736 yilda bu masalaning yechimga ega emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda bog’lamli grafda barcha qirralardan faqat bir marta o’tadigan sikl mavjud bo’ladi?
Ta’rif. Turli qirralardan tashkil topgan marshurt zanjir deyiladi.
Ta’rif. Boshi va ohiri ustma-ust tushuvchi zanjir yopiq zanjir deyiladi.
Ta’rif. Hech bo`lmaganda bitta qirraga ega yopiq zanjir sikl deyiladi.
Ta’rif. Agar zanjir grafning barcha uchlaridan bir martadan o`tsa, bunday
zanjirga gamilton zanjiri deyiladi.
Ta’rif. Grafning barcha qirralaridan bir martadan o`tgan zanjir eyler zanjiri
deyiladi.
Ta’rif . Iхtiyoriy ikkita uchini marshrut bilan birlashtirish mumkin bo`lgan
graf bog`liq graf deyiladi.
Ta’rif. Grafning barcha uchlaridan o`tuvchi karrali qirralar va ilmoqlarga
ega bo`lmagan graf eyler grafi deyiladi.
Ta’rif. Agar bog`liqli grafda har bir uchdan faqat bir martadan o`tuvchi tsikl
(yoki marshrut) mavjud bo`lsa, bunday graf gamilton grafi deyiladi.
Grafning har bir qirrasidan faqat bir marta o’tadigan zanjir Eyler zanjiri deb ataladi. Yopiq Eyler zanjiriga (ya‟ni Eyler sikliga) ega graf Eyler grafi deb ataladi. Agar grafda yopiq bo’lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler grafi deb ataladi.