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
u1 , u2 ,..., un
( 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 (bij )
( 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 v1 va v2 uchlariga
insident bo‘lgan qandaydir u qirrasiga qo‘shish orqali quyidagicha ikki bosqichda bajarilishi mumkin:
u qirra berilgan grafdan olib tashlanadi;
hosil bo‘lgan grafga ikkita yangi qirralar: v va v1 uchlarga insident u1
qirra hamda v va v2
uchlarga insident u2
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.
|
