Toshkent viloyati Chirchiq Davlat pedagogika instituti Aniq fanlar fakulteti

qirralari qo‘shniligi matritsasi deb ataladi.
Ravshanki, sirtmoqsiz va karrali qirralarsiz graf qirralari qo‘shniligi matritsasi bosh diagonalga nisbatan simmetrik kvadrat matritsadir va uning bosh diagonali nollardan iborat.

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

_

^bij ^{ }
1, agar i uch u _j qirraga insident bo' lsa,

_ 0, agar i uch

u _j qirraga intsident bo' lmasa,

ko‘rinishda aniqlangan

B  (b_ij )
( i  1,2,...,m ,


j  1,2,...,n ) matritsa grafning

insidentlik matritsasi deb ataladi.

Agar G graf karrali qirralarga ega bo‘lmasa, u holda uchlari G grafning barcha uchlaridan iborat bo‘lgan shunday yagona G graf mavjudki, G grafdagi barcha juft uchlar faqat va faqat G grafda qo‘shni bo‘lmagandagina qo‘shnidir. Bunday G graf berilgan G grafning to‘ldiruvchi grafi deb ataladi.

Berilgan graf uchun to‘ldiruvchi grafni qurish jarayonini ham graflar ustida bajariladigan amallar qatoriga kiritish mumkin. G graf uchun to‘ldiruvchi grafni qurish amalini qo‘llash natijasida G graf hosil bo‘ladi. Isbotlash mumkinki,

G  G
munosabat o‘rinlidir.
Graflar ustida shunday amallarni bajarish mumkinki, ular elementlari soni

berilgan grafdagidan ko‘proq bo‘lgan boshqa graflarning hosil bo‘lishiga olib keladi. Bunday amallar qatoriga uchni qo‘shish amali yoki qirrani (yoyni) qo‘shish amalini kiritish mumkin.
Grafga yangi uchni qo‘shish turlicha usul bilan amalga oshirilishi mumkin.
Masalan, yangi v uchni berilgan grafga qo‘shish shu grafning v₁ va v₂ uchlariga
insident bo‘lgan qandaydir u qirrasiga qo‘shish orqali quyidagicha ikki bosqichda bajarilishi mumkin:

1. 
   
   u qirra berilgan grafdan olib tashlanadi;
   

2. hosil bo‘lgan grafga ikkita yangi qirralar: v va v₁ uchlarga insident u₁

   
   

qirra hamda v va v₂

uchlarga insident u₂
qirra qo‘shiladi.

Bu jarayon grafda qirraga darajasi 2 bo‘lgan yangi uchni qo‘shish
(kiritish) yoki qirrani ikkiga bo‘lish amali deb ataladi.
Agar G graf G' grafdan qirrani ikkiga bo‘lish amalini chekli marta ketma-

ket qo‘llash vositasida hosil qilingan bo‘lsa, u holda G graf grafi deb ataladi.