Grafika va grafikning metrik xarakteristikalari

Информация о документе

Цена	2000UZS
Размер	114.5KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Рефераты
Предмет	Педагогика

Grafika va grafikning metrik xarakteristikalari

Купить

MUNDARIJA
I BOB. “GRAFIK” TUSHUNCHASI
1.1. Grafiklarning matritsali tasviri
1.2. Grafiklar ustida amallar
1.3. Marshrutlar, zanjirlar, tsikllar
II BOB. GRAFIKNING METRIK XARAKTERISTIKALARI
2.1. Grafiklar nazariyasini fan va texnikaning turli sohalarida qo‘llash
2.2.. Amaliy qism
XULOSA G
FOYDALANILGAN ADABIYOTLAR RAFI k matritsaning qo'shnilik marshruti

KIRISH
Grafiklar nazariyasi - bu matematikaning keng amaliy qo'llanilishiga ega
bo'lgan bo'limi. Grafik nazariyasi diskret matematikaning bir sohasi bo'lib, uning
xususiyati ob'ektlarni o'rganishga geometrik yondashuvdir. Hayotning ko'p
holatlarida, xususan, dizayn amaliyotida biz qog'ozga shaharlar, alohida ob'ektlar,
temir yo'l kesishmalari va boshqalarni tasvirlaydigan nuqtalarni chizishimiz va bu
nuqtalarni qandaydir bog'lanish yoki munosabatlarni ko'rsatadigan chiziqlar yoki
o'qlar bilan bog'lashimiz kerak. Turli nomlar ostidagi bunday sxemalar hamma
joyda, elektr zanjirlarida, fizikada - radio sxemalarida uchraydi; iqtisodda - ishni
tashkil etish sxemalari va boshqalar. Asosan, barcha sxemalar grafiklar deb
ataladigan mustaqil matematik ob'ektlar sifatida mavhum shaklda ko'rib chiqiladi.
O'rganilayotgan ob'ektlarga bunday yondashuv grafiklar nazariyasining keng
ko'lamli, jumladan, shaharsozlik va ilmiy tadqiqotlar sohasida qo'llanilishiga
imkon beradi. Eylerga tegishli bo'lgan grafiklar nazariyasi bo'yicha birinchi ish
1736 yilda paydo bo'lgan va Königsberg ko'priklari muammosini hal qilish bilan
bog'liq edi. Biroq, bu Eylerning deyarli yuz yil davomidagi yagona ishi edi.
Dastlab, grafiklar nazariyasi matematikaning ahamiyatsiz bo'limi bo'lib tuyuldi,
chunki u faqat matematik o'yin-kulgilar va jumboqlar bilan shug'ullangan,
masalan, sxemalarni loyihalashda, bosilgan elektron plata yoki mikrosxemadagi
elementlarning o'zaro bog'lanish topologiyasi, transport muammosi, muammo.
dunyo bo'ylab sayohat qilish va hokazo. Matematikaning rivojlanishi va uning
qo'llanilishi grafiklar nazariyasining rivojlanishiga kuchli turtki bo'ldi. 10-asrning
o rtalaridayoq grafiklar elektr zanjirlari va molekulyar zanjirlarni qurishdaʻ
qo llanila boshlandi. "Grafik" atamasi birinchi marta 1936 yilda kiritilgan.
ʻ
Vengriyalik matematik Denes König. Uning ishida grafiklar nazariyasi alohida
matematik fan sifatida taqdim etilgan bo‘lib, u hozirgi vaqtda avtomatlashtirish,
telemexanika, kibernetika, elektronika, fizika, iqtisodiyot, psixologiya, biologiya
va fanning boshqa sohalarida keng qo‘llaniladi.

I BOB. “GRAFIK” TUSHUNCHASI
V bo'sh bo'lmagan to'plam bo'lsin, V (2)
uning barcha ikki elementli kichik
to'plamlari to'plami. (V,E) juftlik, bu erda E to'plamning V (2) ixtiyoriy kichik
to'plami
, grafik (yo'naltirilmagan grafik) deb ataladi. V to‘plamning elementlari
grafikning cho‘qqilari, E to‘plamning elementlari esa qirralar deyiladi. Demak,
grafik chekli V to‘plam cho‘qqilari va E qirralarning to‘plamidir, E ⊂ V (2)
.
Grafik atamasi birinchi marta 1936 yilda taniqli venger matematigi
D.Kenigning kitobida paydo bo'lgan, garchi grafiklar nazariyasining dastlabki
muammolari Eyler (18-asr) davriga borib taqalsa.
Grafikning G cho'qqilari va qirralari to'plamlari mos ravishda VG va EG
bilan belgilanadi. Grafikning uchlari va qirralari uning elementlari deyiladi. Raqam
|VG| Grafikning uchlari soni G uning tartibi deb ataladi va |G| bilan belgilanadi.
Agar |G|=n,|EG|=m bo'lsa, grafik (n, m)-grafik deyiladi.
Grafikning ikkita u va v cho'qqilari qo'shni deyiladi, agar {u, v} to'plam
chekka bo'lsa, aksincha emas. Agar e={u, v} chekka bo'lsa, u va v uchlari uning
uchlari deyiladi. Bu vaziyatda e qirrasi u va v uchlarini bog'laydi, deb ham
aytamiz.
Ikki qirralarning umumiy uchi bo'lsa, qo'shni deyiladi.
Agar v uchi e chetining uchlaridan biri bo'lsa, v cho'qqisi va e chekkasi
hodisa deyiladi, aks holda tushmaydi.
E'tibor bering, qo'shnilik grafikning bir hil elementlari orasidagi
munosabatdir, insidans esa bir-biriga o'xshamaydigan elementlar orasidagi
munosabatdir.
Grafikning qandaydir v cho‘qqisiga tutashgan G barcha cho‘qqilari to‘plami
v cho‘qqisining muhiti deyiladi va NG(v) yoki oddiygina N(v) bilan belgilanadi.
Grafiklarni chizmalar (geometrik grafiklar) shaklida tasvirlash qulay. n
o'lchovli evklid fazosi e n geometrik grafik e n fazodagi nuqtalar
to'plami va oddiy

egri chiziqlarning E to'plamidir: 1) E dagi har bir yopiq egri chiziq V to'plamning
faqat bitta v nuqtasini o'z ichiga oladi; 2) E dagi har bir yopiq bo'lmagan egri
chiziq V to'plamning aniq ikkita nuqtasini o'z ichiga oladi, bu uning chegara
nuqtalari; 3) E dagi egri chiziqlar V to'plamdagi nuqtalardan tashqari umumiy
nuqtalarga ega emas. Bunda V to'plamning nuqtalari grafikning uchlariga, juft
nuqtalarni bog'laydigan chiziqlar esa qirralarga to'g'ri keladi.
Grafik G, agar uning ikkita uchi qo'shni bo'lsa, to'liq deyiladi. n tartibli to‘liq
grafik Kn bilan belgilanadi.
Grafikning istalgan ikkita cho'qqisi qo'shni bo'lmasa (ya'ni uning qirralari
yo'q) degenerativ (bo'sh) deb ataladi.
G va H grafiklar va s bo'lsin : VG → VH bijeksiya. Agar har qanday u va v
uchlari uchun ularning tasvirlari s (u) va s (v) H da qo‘shni bo‘lsa, agar u va v G da
qo‘shni bo‘lsa, u holda bu bijeksiya G va H grafiklarining izomorfizmi deyiladi va
G va H grafiklari izomorf. Biz izomorf grafiklarni G ≅ H (shuningdek H G) bilan
belgilaymiz .
Agar G grafigi G' geometrik grafigiga izomorf bo'lsa, G' grafig G ning
geometrik realizatsiyasi deyiladi.
Shubhasiz, grafik izomorfizm munosabati ekvivalentdir. Binobarin, barcha
grafiklar to'plami sinflarga bo'linadi, shunda bir sinfning grafiklari juft izomorf
bo'ladi va turli sinflarning grafiklari izomorf bo'lmaydi. Izomorf grafiklarni
aniqlash tabiiydir, ya'ni. tasodif deb hisoblanadi (ular bitta rasmda tasvirlanishi
mumkin). Ular elementlarning o'ziga xos xususiyati bilan farq qilishi mumkin,
ammo "grafik" tushunchasini kiritishda aynan shu narsa e'tiborga olinmaydi.
Ba'zi hollarda izomorf grafiklarni farqlash hali ham kerak, keyin esa
"yorliqlangan grafik" tushunchasi foydalidir. Agar n-tartibli grafigi, agar uning
cho'qqilariga ba'zi teglar, masalan, 1, 2, ..., n belgilari berilgan bo'lsa, etiketli
deyiladi . Grafikning har bir cho'qqisini o'z raqami bilan aniqlab, (demak, {1, 2, ...,
n} raqamlar to'plamiga ega cho'qqilar to'plami), biz etiketli G va H grafiklarining
tengligini aniqlaymiz. bir xil tartib: G=H keyin va faqat EG =EH bo'lganda.
Agar ko'rib chiqilayotgan grafiklar faqat izomorfizmgacha farq qilishini

ta'kidlash kerak bo'lsa, ular: "mavhum grafik" deyishadi.
Ba'zida yuqorida muhokama qilingan "grafik" tushunchasi etarli emas va biz
ikkita cho'qqi bir nechta qirralar bilan bog'lanishi mumkin bo'lgan umumiyroq
ob'ektlarni ko'rib chiqishimiz kerak. Shunday qilib, "multigraf" tushunchasi paydo
bo'ladi. Multigraf juftlik (V, E), bunda V - bo'sh bo'lmagan to'plam (cho'qqilar) va
E - V (2) to'plamning kichik to'plamlari oilasi
(qirralar). "To'plam" o'rniga "oila"
atamasidan foydalanish V (2)
to'plamining elementlarini E da takrorlash
mumkinligini anglatadi, ya'ni. Bir nechta qirralarga ruxsat beriladi.
Yana bir umumlashma shundaki, bir nechta qirralardan tashqari,
pastadirlarga ham ruxsat beriladi, ya'ni. cho'qqini o'ziga bog'laydigan chekka.
Psevdograf - bu juftlik (V, E), bu erda V - bo'sh bo'lmagan to'plam (cho'qqilar) va
E - tartibsiz juftliklarning (qirralarning) ma'lum bir oilasi, har xil bo'lishi shart
emas.
Yo'naltirilgan grafiklar ham o'rganiladi. Keyin V (2)
to‘plam V to‘plamning
tartiblangan juft elementlaridan iborat dekart kvadrat V 2
bilan almashtiriladi.
Yo‘naltirilgan grafik (yoki digraf) bu juftlik (V, A), bu yerda V cho‘qqilar
to‘plamidir. , A yo'naltirilgan qirralarning to'plami bo'lib, ular yoylar , A V 2 deb
ataladi
.
Agar a=(v1, v2) yoy bo'lsa, u holda v1 va v2 uchlari mos ravishda uning
boshi va oxiri deyiladi.
Yo'naltirilgan multigraf yo'naltirilmaganga o'xshash tarzda aniqlanadi.
Yoylari va yo'naltirilmagan qirralari bo'lgan aralash grafiklar ham hisobga olinadi.
Yo‘naltirilgan (yoki aralash) grafik G ning E to‘plamidagi har bir juftlikni (u, v)
bir xil u va v elementlaridan tashkil topgan tartibsiz juftlik {u, v} bilan almashtirib,
G bilan bog‘langan H=( psevdografini olamiz. =(V, E) grafik V, E 0
). H grafigi G
grafigining asosi ekanligi ham aytiladi.
Digraf, agar uning asosi to'liq grafik bo'lsa, turnir deyiladi.

"Grafik" tushunchasining barcha ko'rib chiqilgan umumlashmalari uchun
izomorfizm tushunchasi xuddi shunday tarzda qo'shnilikni, qirralarning ko'pligini,
halqalarni va yoylarning yo'nalishlarini saqlaydigan cho'qqilar to'plamlari
o'rtasidagi ikkilanish sifatida kiritiladi.

G grafik bo'lsin, w: EG → R +
har bir chekka e ga manfiy bo'lmagan w(e)
sonni belgilaydigan haqiqiy qiymatli funktsiya - e chekkasining og'irligi. Biz
juftlikni (G, w) vaznli grafik deb ataymiz. Og'irlangan grafikning har qanday
subgrafining og'irligi (ehtimol noto'g'ri) deganda biz uning qirralari og'irliklarining
yig'indisini tushunamiz.
1.1.. Grafiklarning matritsali tasviri
n, VG={1, 2, ... , n} tartibli G-yorliqli grafik bo lsin. Ikkilik n × n matritsaniʻ
A=A(G) qo‘yib aniqlaymiz
A(G) grafikning qo‘shnilik matritsasi deb ataladi G. Bu diagonalida nollar
bo‘lgan simmetrik matritsa. Chiziqdagi birlar soni mos keladigan cho'qqi
darajasiga teng.
→ A(G) muvofiqligi n tartibli etiketli grafiklar to‘plamining diagonali nol
bo‘lgan ikkilik simmetrik n × n matritsalar to‘plamiga bijeksiyasini belgilaydi .
Ko'p va psevdograflarning A qo'shni matritsalari xuddi shunday
aniqlanadi: ik i va k uchlarini bog'lovchi qirralarning soniga teng (bu holda halqa
ikki qirrani bildiradi).
Yo'naltirilgan grafikning qo'shnilik matritsasi A(G) ham aniqlanadi.
Shubhasiz, agar A(G) n tartibli G digrafining qo‘shni matritsasi bo‘lsa, u
holda

bular. A(G) matritsaning i-qatoridagi birliklar soni i-chi tepalikning tashqi
darajasiga, k-ustundagi birliklar soni esa yarim darajaga teng. k-chi uchi.
Teorema. Grafiklar izomorf bo'ladi, agar ularning qo'shni matritsalari bir-
biridan satr va ustunlarning bir xil o'rin almashtirishlari orqali olingan bo'lsa.
Teorema multigraflar, psevdograflar va digraflar uchun ham amal qiladi.
G a (n, m)-grafik, VG={1, 2, ... , n } EG={e1, e2,... , em } bo‘lsin . Ikkilik n
× m matritsani I=I(G) shartlar bilan aniqlaymiz
I matritsa G grafikning insidans matritsasi deb ataladi. Har bir ustunda aynan
ikkitadan teng ustunlar mavjud emas; Yuqoridagidek, G → I(G) muvofiqligi
tasvirlangan shartlarni qanoatlantiruvchi n × m matritsalar to‘plamiga chekkalari
raqamlangan (n, m)-grafiklar to‘plamining bijeksiyasidir .
Digraf uchun insidans matritsasi I:
Teorema. Grafiklar izomorf bo'ladi, agar ularning insidans matritsalari bir-
biridan satr va ustunlarni ixtiyoriy almashtirish orqali olingan bo'lsa.
Teorema multigraflar, psevdograflar va digraflar uchun ham amal qiladi.
Qo'shnilik va insidans matritsalarining xossalari:
1) A(G) matritsa elementlari yig‘indisi, bunda G=(V, E) multigraf, V={v1,
v2, ..., vn } , i-qator bo‘ylab (yoki bo‘ylab) i-ustun) d( vi) ga teng. 2) A(G) matritsa
elementlarining yig‘indisi, bunda G=(V, E) yo‘naltirilgan psevdograf ,
V={v1, v2, ... , vn } , i-qatorda va i-ustunda mos ravishda d( vi ), d( vi ) ga
teng.

$3) Bo'sh bo'lmagan yoylar to'plamiga ega G-yo'naltirilgan multigraf bo'lsin. Keyin: a) I(G) matritsa satrlari yig’indisi nol qatorga teng; b) I(G) matritsaning istalgan qatori qolgan qatorlarning chiziqli birikmasidir; v) I(G) matritsaning darajasi n-1 dan oshmaydi; d) G matritsaning istalgan konturi uchun I(G) matritsaning ushbu konturga kiritilgan yoylarga mos keladigan ustunlari yig’indisi nol ustunga teng. 4) G qirralari bo‘sh bo‘lmagan multigraf bo‘lsin. Keyin, koordinatali qo'shilish moduli 2 bilan: a) I(G) matritsa satrlari yig'indisi nol qatorga teng; b) I(G) matritsaning istalgan qatori qolgan qatorlar yig‘indisidir; c) G dagi har qanday sikl uchun I(G) matritsasining ushbu tsiklga kiritilgan qirralarga mos keladigan ustunlari yig'indisi nol ustunga teng . 1.2.. Grafiklar ustida amallar VG, EH EG bo'lsa, G grafikning pastki grafigi deyiladi . Agar H G grafikning kichik grafigi bo'lsa, H grafigida joylashgan deyiladi. Agar u grafikning o'zidan farq qilsa, pastki grafik to'g'ri deb ataladi. Agar VH =VG bo'lsa, H pastki grafigi G grafigining kengayuvchi subgrafi deyiladi. Agar H pastki chiziqning uchlari to'plami U bo'lsa va uning qirralari to'plami G grafikning ikkala uchi U ga tegishli bo'lgan barcha qirralarning to'plamiga to'g'ri kelsa, H cho'qqilar to'plami tomonidan hosil qilingan pastki grafik deyiladi. U va G(U) bilan belgilanadi. Agar H subgrafaning qirralari to'plami E' EG bo'lsa va uning uchlari to'plami G grafikning E' cho'qqilaridan barcha chekka uchlari to'plamiga to'g'ri kelsa, H pastki grafik to'plam tomonidan hosil qilingan pastki grafik deyiladi. qirralari E' va G(E') bilan belgilanadi. v grafigning G cho'qqisi bo'lsin.U holda H=Gv grafigini qurish amali v uchini o'chirish deyiladi. Ushbu amal natijasida tuzilgan H grafigi EG to'plamining v cho'qqisiga tushadigan va VH =VG\{v} nuqtalaridan tashqari barcha qirralarini$ $o'z ichiga oladi. E grafigining G qirrasi bo lsin. U holda H=Ge grafigini qurish amali e chetini o chirish deyiladi. Ushbu amal natijasida tuzilgan H grafigi G grafikning barcha uchlarini o'z ichiga oladi va EH =EG\{e}. Cho'qqi yoki chekkani olib tashlash, shuningdek pastki grafaga o'tish mavjud grafikdan kamroq elementlarga ega bo'lgan boshqa grafiklarni olish uchun ishlatilishi mumkin bo'lgan amallardir. Endi mavjud grafiklardan ko'p sonli elementlarga ega grafiklarni olish imkonini beruvchi amallarni ko'rib chiqamiz. Agar G=(VG, EG) grafigining u va v cho’qqilari yonma-yon bo’lmasa, u holda H=(VH, EH) grafigi G grafikdan e={u, v} chetini qo’shish orqali olingan deyiladi. agar VH =VG va EH = EG { e } bo'lsa, H=G+e yozing . ∩ VG va EH =EF ∩ EG bo'lsa, H grafigi F va G grafiklarning birlashishi (yoki superpozitsiyasi) deyiladi . Bu holatda biz H=F ∩ G deb yozamiz. F ∩ G birlashmasi V F ∩ V G = ∅ bo'lsa, dis'yunktiv deyiladi . Har qanday grafiklar to'plamining birlashuvi va ayiruvchi birlashmasi xuddi shunday aniqlanadi va ikkinchi holda, birlashtirilayotgan grafiklarning ikkitasi umumiy cho'qqilarga ega bo'lmasligi kerak. G1=(V1, E1) va G2=(V2, E2) bo‘lsin. U holda grafiklar ko‘paytmasi (G 1× G2 bilan belgilanadi) grafik G bo‘lib, uning uchun VG =V 1× V2 asl grafiklar cho‘qqilari to‘plamlarining dekart ko‘paytmasi, EG esa quyidagicha aniqlanadi: cho‘qqilar (u1, u2) va (v1, v2 ) G grafigida qo‘shni bo‘ladi, agar u1=v1 va u2 va v2 G2 da qo‘shni bo‘lsa yoki u2=v2 va u1 va v1 G1 da qo‘shni bo‘lsa. 1.3. Marshrutlar, zanjirlar, tsikllar Grafik uchlari va qirralarining v1, e1, v2, e2, ... , en, vn+1 ketma-ketligi ei =vivi+1 (i=1, n) 1 va vn uchlarini birlashtiruvchi marshrut deyiladi. +1 (yoki (v1vn+1)-marshrut). Shubhasiz, grafikda marshrutni ko'rsatish uchun v1, v2, ..., vn+1 ketma-ketligini ko'rsatish kifoya. uning uchlari yoki qirralarining e1, e2,... , en ketma-ketligi.$