2.2 Qo‘shmalik matritsasi. Bizga G yo‘naltirilmagan graf berilgan bo‘lib, u chekli bo‘lsin. Aytaylik (a1,…,an), G grafning qirralari bo‘lsin. U holda qo‘shmalik matritsasi ||Aij||, i=1,m, j=1, n m ta qator va n ta ustundan iborat bo‘ladi, Aij matritsaning ustunlariga G ning tugunlari, qatorlariga G ning qirralarini mos qo‘yamiz. U holda
Aij=
q oidadan foydadanib qœshmalik matritsasini ќosil qilamiz. Misol.
|
a1
|
a2
|
a3
|
a4
|
a5
|
a6
|
a7
|
e1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
e2
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
e3
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
e4
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
e5
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
e6
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
e7
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
e8
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
e9
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
e10
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
Agar G yo‘naltirilgan graf bo‘lsa, u holda
Aij=
|
a1 a2 a3 a4 a5 a6 a7
|
e1
|
-1 1 1 0 0 0 0
|
e2
|
-1 0 0 0 0 0 0
|
e3
|
0 -1 0 1 0 0 0
|
e4
|
0 0 -1 0 1 0 0
|
e5
|
0 0 -1 0 0 1 0
|
e6
|
0 0 -1 1 0 0 1
|
e7
|
0 0 0 0 0 0 2
|
qoidadan foydadanib qœshmalik matritsasini ќosil qilamiz.
Misol.
2.3 Qo‘shnilik matritsasi. Faraz qilaylik G graf yo‘naltirilmagan bo‘lsin. Grafning qo‘shnilik matritsasida Aij ning ustunlariga ham qatorlariga ham grafning tugunlarini mos qo‘yamiz. U xolda
Aij=
qoidadan foydadanib qœshnilik matritsasini ќosil qilamiz.
Misol. 1-rasmda keltirilgan yo‘naltirilmagan graf uchun qœshnilik matritsasi quyidagicha bœladi.
|
a1 a2 a3 a4 a5 a6 a7
|
a1
|
0 1 1 0 1 0 0
|
a2
|
1 0 0 1 0 1 0
|
a3
|
1 0 0 1 1 0 0
|
a4
|
0 1 1 0 0 1 0
|
a5
|
1 0 1 0 0 0 1
|
a6
|
0 1 0 1 0 0 1
|
a7
|
0 0 0 0 1 1 0
|
G yo‘naltirilgan graf bo‘lsin. U holda qo‘shnilik matritsasi Aij ning ustunlariga ham satrlariga ham grafning tugunlarini mos qo‘yamiz. Uholda
qoidadan foydadanib qœshnilik matritsasini ќosil qilamiz.
Misol. 2-rasmda keltirilgan yo‘naltirilgan graf uchun
qœshnilik matritsasi quyidagicha bœladi.
|
a1 a2 a3 a4 a5 a6 a7
|
a1
|
0 1 1 0 0 0 0
|
a2
|
0 0 0 1 0 0 0
|
a3
|
0 0 0 0 1 1 1
|
a4
|
0 0 0 0 0 0 0
|
a5
|
0 0 0 0 0 0 0
|
a6
|
0 0 0 0 0 0 0
|
a7
|
0 0 0 0 0 0 1
|
Teorema. Agar grafda karrali qirralari hamda sirtmoq mavjud bo‘lmasa, n ta tugunga ega bo‘lgan va bog‘liq komponentasi K ga teng bo‘lgan grafning qirralari soni eng ko‘pi bilan aniqlanadi.
M=
Mashrutning uzunligi deb, shu marshrutda mavjud qo‘shni (ei-1, ei) qirralar soniga aytiladi.
Grafning ixtiyoriy a va ixtiyoriy v tugunlari orasidagi masofa deb, shu tugunlarni bog‘lovchi eng kichik uzunlika ega bo‘lgan zanjirga aytiladi.
Misol.
d(a1,a3)= (e0, ye1)=2;
d(a1,a4)=(e0, ye2)=2;
d(a1,a4)=(e0, ye1, ye3)=3
Grafning diametri deb, eng katta uzunlikka ega bo‘lgan masofaga aytiladi.
Misol. d(a1,a4)=(e0, ye1, ye3)=3.
s tugun G grafning fiksirlangan tuguni bo‘lsin. x esa grafning ixtiyoriy tuguni bo‘lsin. s tugun uchun maksimal masofani hisoblaymiz. Qandaydir s0 tugun uchun bu maksimal masofa boshqa tugunlarga nisbatan minimal bo‘lsa, uholda s0 G grafning markazi deyiladi va s0 uchun aniqlangan masofa G grafning radiusi deyiladi.
Bu misolda markaz 3 yoki 6 tugunlar bo‘lishi mumkin, chunki r(c)=2.
2.4 Eyler grafi. Bizga yo‘naltirilmagan G graf berilgan bo‘lsin. Eyler sikli shunday siklki, unda grafning ma’lum bir tugunidan chiqib, barcha qirralardan faqat bir marta o‘tib, yana shu tugunga qaytib kelishi kerak.
Grafda Eyler sikli mavjud bulishi uchun:
a) Graf boglangan bo‘lishi;
b) Grafning barcha tugunlarining lokal darajalari juft
bœlishi kerak;
Grafda Eyler zanjiri mavjud bœlishi uchun:
a) Graf boglangan bo‘lishi;
b) Grafning 2 ta tuguni(boshlanish va oxirgi) lokal darajalari toq bœlib, qolgan barcha tugunlarining lokal darajalari juft bœlishi kerak.
A gar G yo‘naltirilmagan grafda Eyler sikli mavjud bo‘lsa, bunday grafga Eyler grafi deyiladi.
Misol.
2.5 Gamilton grafi. Agar grafda oddiy sikl mavjud bo‘lib, bu siklda grafning barcha tugunlari qatnashsa, bunday sikl Gamilton sikli deyiladi.
Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda tugunlarning xammasi ishtirok etsa. Tugun va qirralar takrorlanmasligi kerak.
Grafda Gamilton sikli mavjud bo‘lsa, bu graf Gamilton grafi deyiladi.
Misol.
Bu grafda oddiy sikl S1=( ye0, ye1, ye4 ye5, ye6) – Gamilton sikli, S2=( ye0, ye1, ye7, ye6) - Gamilton sikli emas, chunki a5 tugun qatnashmayapti.
Topshiriq variantlari.
Quyidagi keltirilgan yunaltirilgan va yunaltirilmagan graflar uchun:
1) Grafni tœldiruvchisini toping.
2) Grafni kism grafini toping.
3) Qœshmalik matritsani tuzing.
4) Qœshnilik matritsani tuzing.
5) Grafni markazini toping.
6) Grafni diametrini toping.
7) Grafni radiusini toping.
8) Grafda Eyler sikli mavjudligini tekshiring.
9) Grafda Gamilton sikli mavjudligini tekshiring.
10) Grafni siklomatik sonini toping.
11) Grafni qirralar sonini tugunlarning lokal darajalari va qœshnilik matritsasi orqali aniqlang.
29)
Foydalanilgan adabiyotlar
T.P. Lixtarnikov, D.L.Sukacheva Matematicheskaya logika. Sant-Peterburg,1999 g.
S. Yablonskiy. Vvedenie v diskretnoy matematiki. 1979. M. 261-s.
X.T.Turaev. Matematik mantik, va diskret matematika. Ukuv kullanma. T-2004. 456 b.
X.T.To‘raev, I.A.Azizov, Otaqulov S.O. Kombinatorika va graflar nazariyasi. SamDU nashr-matbaa markazi.2006. 267 bet.
|
