Графлар устида амаллар

2 Qo‘shmalik matritsasi. Bizga G yo‘naltirilmagan graf berilgan bo‘lib, u chekli bo‘lsin. Aytaylik (a₁,…,a_n), G grafning qirralari bo‘lsin. U holda qo‘shmalik matritsasi ||A_ij||, i=1,m, j=1, n m ta qator va n ta ustundan iborat bo‘ladi, A_ij matrisaning ustunlariga G ning tugunlari, qatorlariga G ning qirralarini mos qo‘yamiz. U holda
A_ij=
šoidadan foydadanib šœshmalik matritsasini ќosil šilamiz. 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
A_ij=

	a1 a2 a3 a4 a5 a6 a7
ye1	-1 1 1 0 0 0 0
ye2	-1 0 0 0 0 0 0
ye3	0 -1 0 1 0 0 0
ye4	0 0 -1 0 1 0 0
ye5	0 0 -1 0 0 1 0
ye6	0 0 -1 1 0 0 1
ye7	0 0 0 0 0 0 2

šoidadan foydadanib šœshmalik matritsasini ќosil šilamiz.

Misol.


3 Qo‘shnilik matritsasi. Faraz qilaylik G graf yo‘naltirilmagan bo‘lsin. Grafning qo‘shnilik matritsasida A_ij ning ustunlariga ham qatorlariga ham grafning tugunlarini mos qo‘yamiz. U xolda
A_ij=
šoidadan foydadanib šœshnilik matritsasini ќosil šilamiz.
Misol. 1-rasmda keltirilgan yo‘naltirilmagan graf uchun šœshnilik matritsasi šuyidagicha 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 A_ij ning ustunlariga ham satrlariga ham grafning tugunlarini mos qo‘yamiz. Uholda
šoidadan foydadanib šœshnilik matritsasini ќosil šilamiz.
Misol. 2-rasmda keltirilgan yo‘naltirilgan graf uchun
šœshnilik matritsasi šuyidagicha 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 anišlanadi.
M=
Mashrutning uzunligi deb, shu marshrutda mavjud qo‘shni (ye_i-1, e_i) 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(a₁,a₃)= (ye₀, ye₁)=2;
d(a₁,a₄)=(ye₀, ye₂)=2;
d(a₁,a₄)=(ye₀, ye₁, ye₃)=3
Grafning diametri deb, eng katta uzunlikka ega bo‘lgan masofaga aytiladi.

Misol. d(a₁,a₄)=(ye₀, ye₁, ye₃)=3.

s tugun G grafning fiksirlangan tuguni bo‘lsin. x esa grafning ixtiyoriy tuguni bo‘lsin. s tugun uchun maksimal masofani hisoblaymiz. Qandaydir s₀ tugun uchun bu maksimal masofa boshqa tugunlarga nisbatan minimal bo‘lsa, uholda s₀ G grafning markazi deyiladi va s₀ uchun aniqlangan masofa G grafning radiusi deyiladi.

Bu misolda markaz 3 yoki 6 tugunlar bo‘lishi mumkin, chunki r(c)=
4 Eyler grafi. Bizga yo‘naltirilmagan G graf byerilgan 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 toš bœlib, šolgan barcha tugunlarining lokal darajalari juft bœlishi kerak.
Agar G yo‘naltirilmagan grafda Eyler sikli mavjud bo‘lsa, bunday grafga Eyler grafi deyiladi.
Misol.


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 S₁=( ye₀, ye₁, ye₄ ye₅, ye₆) – Gamilton sikli, S₂=( ye₀, ye₁, ye₇, ye₆) - Gamilton sikli emas, chunki a₅ tugun qatnashmayapti.

Topshiriš variantlari.
Šuyidagi keltirilgan yunaltirilgan va yunaltirilmagan graflar uchun:
1) Grafni tœldiruvchisini toping.
2) Grafni kism grafini toping.
3) Šœshmalik matritsani tuzing.
4) Šœ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 širralar sonini tugunlarning lokal darajalari va šœshnilik matritsasi oršali anišlang.