Grafik nazariyasi. Grafiklar nazariyasi diskret matematikaning keng ko'lamli mustaqil bo'limidir

Korobova Anastasiya, gr talabasi. 14-PGS-48D

Bizning zamonamizda o'qish muhim ahamiyatga ega turli usullar, xususiyatlar va nostandart ilovalar. Atrofimizdagi voqelikda “Grafik” usulini qo‘llashni ko‘rib chiqamiz.

Matematikadagi "grafik" so'zi bir nechta nuqtalar chizilgan, ularning ba'zilari chiziqlar bilan bog'langan rasmni anglatadi. Avvalo, muhokama qilinadigan grafiklarning o'tmishdagi aristokratlar bilan hech qanday aloqasi yo'qligini aytish kerak. Bizning "grafiklarimiz" yunoncha "grapho" so'zidan kelib chiqqan bo'lib, "men yozaman" degan ma'noni anglatadi. "Grafika", "biografiya" so'zlarida bir xil ildiz.

Grafik nazariyasi bo'yicha birinchi ish Leonard Eulerga tegishli bo'lib, u 1736 yilda Sankt-Peterburg Fanlar Akademiyasi nashrlarida paydo bo'lgan.

Grafiklar mavjud:

fizikada - elektr davrlarini qurishda

kimyo va biologiyada - ularning zanjirlarining molekulalarini o'rganishda

tarixda - genealogik daraxtlarni (najara) tuzishda

geografiyada - xaritalar tuzishda

geometriyada - ko'pburchaklar, ko'pburchaklar, fazoviy figuralar chizmalari

iqtisodda - yuk tashish oqimlarining optimal yo'lini tanlash masalalarini hal qilishda (aviakompaniyalar, metro, temir yo'llar sxemalari)

Grafik nazariyasi matematika olimpiadalari masalalarini yechishda qo'llaniladi. Grafiklar masalaning shartlariga aniqlik beradi, yechimni soddalashtiradi va masalalarning o'xshashligini ochib beradi.

Endi fan va texnologiyaning istalgan sohasida siz grafiklar bilan uchrashasiz.

Yuklab oling:

Ko‘rib chiqish:

Taqdimotlarni oldindan ko'rishdan foydalanish uchun o'zingizga Google hisobini (hisob qaydnomasi) yarating va unga kiring: https://accounts.google.com

Slayd sarlavhalari:

Matematika bo'yicha taqdimot Mavzu: "Grafiklar" 14-PGS-48D guruhi talabasi Anastasiya Korobova tomonidan to'ldirilgan

Grafik - bu nuqtalarni bog'laydigan nuqtalar va chiziqlardan iborat rasm. Chiziqlar grafaning qirralari, nuqtalar esa cho'qqilar deyiladi. Juft sonli qirralari chiqadigan uchlari juft, toq sonlari toq deyiladi. Grafiklarga misollar Grafik nazariyasi

Leonard Eyler (1707 yil 4 aprel, Bazel, Shveytsariya — 1783 yil 7 sentyabr, Sankt-Peterburg, Rossiya imperiyasi) — matematika, shuningdek, mexanika, fizika, astronomiya fanlari rivojiga katta hissa qoʻshgan shveytsariyalik, nemis va rus matematigi. va bir qator amaliy fanlar. Eyler matematik tahlil, differensial geometriya, sonlar nazariyasi, taqribiy hisoblar, osmon mexanikasi, matematik fizika, optika, ballistika, kemasozlik, musiqa nazariyasi va boshqalarga oid 800 dan ortiq maqolalar muallifi.

Qog'ozdan qalamni ko'tarmasdan chizish mumkin bo'lgan rasm (grafik) unikursal deb ataladi. Muntazamlik 1. Qog'ozdan qalamni ko'tarmasdan faqat ikkita toq cho'qqisi bo'lgan grafik chizish mumkin, bunda harakat shu toq cho'qqilarning biridan boshlanib, ikkinchisida tugashi kerak. (A-rasm) 2-rasm. Ikkitadan ortiq toq uchlari boʻlgan grafikni “bir zarba bilan” chizish mumkin emas (B-rasm).Eyler grafiklari BA.

Muntazamlik 3. Grafikning barcha uchlari juft bo'lsa, qalamni qog'ozdan ko'tarmasdan, har bir chekka bo'ylab faqat bir marta chizilgan holda, ushbu grafikni chizing. Harakat har qanday cho'qqidan boshlanib, bir xil cho'qqida tugashi mumkin.

Uzoq vaqt davomida Königsberg aholisi orasida quyidagi topishmoq keng tarqalgan edi: qanday qilib barcha ko'priklardan (Pregolya daryosi bo'ylab) ularning hech birini ikki marta kesib o'tmasdan o'tish mumkin? Ko'pchilik bu muammoni ham nazariy, ham amaliy jihatdan, yurish paytida hal qilishga harakat qildi.Kenigsberg ko'priklari muammosi.

Bu grafik bo'lib, uning ba'zi qirralari yo'naltirilgan, ba'zilari esa yo'naltirilmagan bo'lishi mumkin. Aralash grafik

Vaznli hisob 1 2 4 2 3 A B C D E

Hech qanday tsiklga ega bo'lmagan har qanday bog'langan grafik daraxt deb ataladi. Daraxtlar Daraxtlar

Bu (ko'p) grafik bo'lib, uning qirralariga yo'nalish tayinlangan. Yo'nalishli qirralar, shuningdek, yoylar deb ham ataladi. Yo'naltirilgan grafik

Grafiklar mavjud:

Grafik nazariyasi matematika olimpiadalari masalalarini yechishda qo'llaniladi. Grafiklar masalaning shartlariga aniqlik beradi, yechimni soddalashtiradi va masalalarning o'xshashligini ochib beradi. Endi fan va texnologiyaning istalgan sohasida siz grafiklar bilan uchrashasiz.

E'tiboringiz uchun tashakkur!

talabalarni “Grafik” tushunchasi, uni qurishning asosiy tamoyillari bilan tanishtirish;

ob'ektlarni bog'laydigan munosabatlarni ajratib ko'rsatish qobiliyatini shakllantirish;

e'tiborni, mantiqiy fikrlash qobiliyatini rivojlantirish;

o'zaro yordamni, jamoada ishlash qobiliyatini tarbiyalash

Olingan bilimlarni amaliyotda mustahkamlash

xotirani, e'tiborni rivojlantirish;

mustaqillikni rivojlantirish;

kognitiv faollikni tarbiyalash.

Uskunalar:

• zamonaviy texnologiyalar bilan jihozlangan kompyuter sinfi, video proyektor, ekran;
• Windows XP kompyuterlar, dastur Microsoft Office 2003 yil PowerPoint;
• doskaning jihozlanishi (dars mavzusi, yangi atamalar). Tarqatma.

Dars rejasi.

II. Yangi material taqdimoti. (10 min.)

III. Materialni himoya qilish. Amaliy ish. (15-20 min.)

IV. Darsni yakunlash (2 daqiqa)

V. Uy vazifasi.

I. Tashkiliy moment. Bilimlarni yangilash.

Salom! Bizning darsimiz "Grafiklar" deb nomlanadi. “Grafiklar” tushunchasi bilan tanishamiz, ularni tasvirlash va shu mavzuga oid masalalar yechish usullarini o’rganamiz.

II Yangi material taqdimoti.

Grafik nazariyasi bo'yicha birinchi ish Leonard Eylerga (1736) tegishli, garchi "grafik" atamasi birinchi marta 1936 yilda vengriyalik matematik Denesh Koenig tomonidan kiritilgan. Grafiklar nuqtalardan tashkil topgan va chiziq segmentlari yoki egri chiziqlarning ushbu nuqtalarini bog'laydigan sxemalar deb ataladi (grafiklarga misollar 1-rasmda ko'rsatilgan).

Grafiklar yordamida bilimlarning turli sohalarida tuzilgan masalalarni yechish ko'pincha soddalashtirildi: avtomatlashtirish, elektronika, fizika, kimyo va boshqalarda. Grafiklar yordamida yo'llar, gaz quvurlari, issiqlik va elektr tarmoqlarining diagrammalari tasvirlangan. . Grafiklar matematik va iqtisodiy muammolarni hal qilishda yordam beradi.

Grafik - (yunoncha grapho - yozaman) ular orasidagi munosabatlar ob'ektining elementlarini vizual tasvirlash vositasidir. Bu ajoyib matematik ob'ektlar, ularning yordami bilan siz juda ko'p turli xil, bir-biriga o'xshamaydigan muammolarni hal qilishingiz mumkin.

Grafik ma'lumot modelining bir turidir

Grafik yoylar yoki chiziq segmentlari - qirralar bilan bog'langan cho'qqilar yoki tugunlardan iborat. Chiziq yo'naltirilishi mumkin, ya'ni u o'q (yoy), agar yo'naltirilmagan bo'lsa, chekkaga ega bo'lishi mumkin. Yoy yoki chekka bilan bog'langan ikkita cho'qqi qo'shni deyiladi.

Grafiklarga misollar (Slayd 4, 5, 6)

1-topshiriq (7-slayd):

Quyosh tizimining to'qqizta sayyorasi o'rtasida kosmik aloqa o'rnatilgan. Kruiz raketalari quyidagi yo'nalishlarda uchadi:

Yer - Merkuriy; Pluton - Venera; Yer - Pluton; Pluton - Merkuriy; Merkuriy - Venera; Uran - Neptun; Neptun - Saturn; Saturn - Yupiter; Yupiter - Mars; Mars - Uran.

Yerdan Marsga rejalashtirilgan raketalarda uchish mumkinmi?

Yechish: Shartning diagrammasini chizamiz: biz sayyoralarni nuqta bilan, raketalarning marshrutlarini esa chiziqlar bilan tasvirlaymiz.

Endi Yerdan Marsga uchib bo'lmasligi darhol ma'lum bo'ldi.

Yoy yoki chekka bilan bog'langan ikkita cho'qqi qo'shni deyiladi. Har bir chekka yoki yoy u bilan bog'langan raqamga ega. Raqam aholi punktlari orasidagi masofani, bir cho'qqidan ikkinchisiga o'tish vaqtini va hokazolarni ko'rsatishi mumkin.

2-topshiriq (9-slayd) - doskadagi yechim. Masha hayvonot bog'iga keldi va iloji boricha ko'proq hayvonlarni ko'rishni xohlaydi. U qaysi yo'ldan borishi kerak? Sariq, qizil, yashil?

3-topshiriq (11 slayd) - doskadagi yechim. Beshta futbol jamoalari A, B, C, D, E bir-birlari bilan o'ynashlari kerak. B, C, D bilan allaqachon A o'ynagan; B bilan A, C, D. Qanchadan qancha o'yin o'tkazildi? O'ynashga qancha vaqt qoldi?

Grafik tasviri (12-slayd)

Grafik yoylar ro'yxati (AB; 7) sifatida grafik yoki jadval yordamida ko'rsatilishi mumkin.

Ark ro'yxatlari	Grafik shakl	Jadval shakli
(AB; 7),		A V BILAN A 3 V 4 BILAN 3 4

III. Materiallarni birlashtirish: talabalar guruhlarga bo'linib, topshiriqlarni bajarishlari tavsiya etiladi. Kichik guruhda talabalar dars boshida olgan nazariy bilimlari asosida modellarni muhokama qiladilar. Bu materialning takrorlanishi va mustahkamlanishiga erishadi.

2-topshiriq (13-slayd)

IV. Dars xulosasi

Bolalar, bugun qanday yangi so'zlarni o'rgandingiz? (Grafik, grafik uchi, grafik qirralari.)

Grafikning uchlari nimani anglatishi mumkin? (Shaharlar; bog'langan ob'ektlar.)

Grafikning qirralari nimani anglatadi (yo'llar, harakatlar, yo'nalishlar)

Hayotda ular bilan qayerda uchrashishimiz mumkinligiga misol keltiring?

Grafiklar qanday tasvirlangan?

V. Uyga vazifa. (15-slayd)

Cho'qqilar soni deyiladi
grafikning tartibi.
Qovurg'alar soni deyiladi
grafikning o'lchami.

Ba'zi atamalar - 1

- R = (a, b) grafikning chetlaridan biri bo'lsin. Keyin
a va b uchlari terminal deb ataladi
qovurg'aning uchlari;
- Xuddi shu qirraning so'nggi uchlari
qo'shni deb ataladi;
- Ikki chekka mavjud bo'lsa, qo'shni deyiladi
umumiy terminal tepasi;
- Ikki chekka ko'p if deyiladi
ularning terminal cho'qqilari to'plamlari mos keladi;
- Agar uchlari bo'lsa, chekka halqa deyiladi
moslashish.

Ba'zi atamalar - 2

- V cho'qqining darajasi deg (V) bilan belgilanadi.
uchun qirralarning soni deb ataladi
qaysi uchi terminal hisoblanadi;
- Agar cho'qqi izolyatsiya qilingan bo'lsa deyiladi
bu hech kim uchun terminal emas
qovurg'alar;
- Agar cho'qqi bo'lsa barg deyiladi
aynan bittasi uchun terminal
qovurg'alar. q varaq uchun daraja (q) = 1 aniq.

Misol:

daraja (C) = 4
H1,… H4 - Barglar

Yana bir misol:

B va D shaharlari - izolyatsiya qilingan
tepaliklar; G va E shaharlari barglardir.

To'liq grafik

Agar mavjud bo'lsa, grafik to'liq deyiladi
ikkita cho'qqi bir chekka bilan bog'langan.
To'liq grafikning nechta qirralari bor
n tartibli?
N tartibli to'liq grafigi qirralarning soniga ega
Cn2 = n ga teng!/ (2 * (n-2)!) = n * (n-1) / 2

Keling, buni isbotlaylik ...

Ikki burchakli toʻliq grafik
bir chetini o'z ichiga oladi - bu aniq.
n * (n-1) / 2 formulasiga n = 2 o'rniga qo'ying
Biz olamiz:
n * (n-1) / 2 = 1
Formula n = 2 uchun to'g'ri

Induksion faraz

Faraz qilaylik, formula to'g'ri
k uchli grafik.
Keling, bu nimani anglatishini isbotlaylik
grafik uchun formulaning haqiqiyligi
c (k + 1) cho'qqi.

K cho'qqilari bilan to'liq grafikga yana bitta cho'qqi qo'shing.

Va uni birinchi K bilan bog'lang
cho'qqilar ...

Biz olamiz:

Bizda qancha qovurg'a borligini hisoblaymiz ...

K * (K-1) / 2 + K
=
K * (K + 1) / 2
Oxirgi ifoda olinadi,
agar formulada n o'rniga n * (n-1) / 2 bo'lsa
K + 1 ni almashtiring.

Adolat farazidan
n = k uchun bayonot nazarda tutadi
uchun bayonotning haqiqiyligi
n = k + 1.
Teorema isbotlangan.

To'liq grafiklarga misollar

Muhim tushuntirish

Yo'naltirilmagan grafikdagi qirralarni belgilovchi juftliklar tartibsizdir (ya'ni.
(a, b) va (b, a) juftliklari farq qilmaydi)

Yo'naltirilgan grafik

Grafikning qirralari o'rnatilgan bo'lsa
tartiblangan juftliklar (ya'ni (a, b) ≠ (b, a)),
Keyin grafik yo'naltirilgan deb ataladi
(yoki digraf)
Kontseptsiyaga qanday yo'nalish berish kerak
vizual ma'nosi?
Juda oddiy - qovurg'alar beriladi
o'qlar (boshdan oxirigacha)!

Digrafga misol

Aralash grafik

Aralash grafik uchlik (V, E, A).
V - cho'qqilar to'plami;
E - ko'p yo'naltirilmagan
qovurg'alar;
A - yo'naltirilgan qirralarning to'plami.
Aytgancha, yo'naltirilgan qirralar
yoylar deyiladi.

Grafik izomorfizmi

Ikkita grafik G1 va G2 bo'lsin
Agar birma-bir yozishma bo'lsa F
G1 va G2 grafalari cho'qqilari o'rtasida, shunday qilib:
- agar G1 grafigida chekka (a, b) bo'lsa, u holda G2 grafigi
chekka bor (F (a), F (b))
- agar G2 grafigida chekka (p, q) bo'lsa, u holda G1 grafigi
chekka bor (F-1 (p), F-1 (q))
keyin G1 va G2 grafiklari izomorf deb ataladi va
F moslashuvi izomorfizmdir.

Aniqlash

Digraflar va aralash grafiklar uchun
F mosligi saqlanishi kerak
yoylarning orientatsiyasi.

Izomorfizm uchun zarur shart-sharoitlar

Elementlar orasidagi qanday sharoitlarda
ikkita chekli to'plam bo'lishi mumkin
birma-bir o'rnatish
muvofiqlik?
Keyin va faqat keyin, ularning soni
elementlar bir xil.
Izomorfizm uchun zaruriy shart
grafiklar soni bir xil
cho'qqilari.

Bu etarli shartmi?

Yo'q, tepalar bo'lishi mumkin
turli yo‘llar bilan bog‘langan.

Bu grafiklar izomorfmi?

Cho'qqilar soni bir xil -
zarur shart bajarilgan ...

F yozishmalarini qurishga harakat qilmoqda ...

Bu izomorfizm emas: G1 qirrasini o'z ichiga oladi (A, D),
va G2-dagi bu qirralarning tasvirlari bog'lanmagan.

Yana bir urinish...

Va bu izomorfizm!

Bu grafiklar izomorfmi?

Afsuski yo `q…

Nazariy jihatdan, ikkita
izomorf grafik - bu bitta va bir xil
bir xil ob'ekt (faqat, ehtimol, boshqacha tasvirlangan ...)

Yo'llar (zanjirlar):

Yo'l (zanjir) ketma-ketlikdir
Cho'qqilar:
a1, a2,…, an
bu erda qo'shni uchlari ai va ai + 1
qovurg'alar bilan bog'langan.
Yo'lning uzunligi - uning tarkibiy qismlarining soni
qovurg'alar

Yo'llarga misollar:

(A, D, C) va (A, B, D) yo'llardir. (A, B, C) yo'l emas.

Digraf uchun yo'l tushunchasi saqlanib qoladi
kuch, lekin qo'shimcha kerak -
qoʻshni choʻqqilar
ketma-ketliklar
a1, a2,…, an
yoylar orqali ulanishi kerak.

Velosipedlar

Tsikl - bu boshlang'ich va ga ega bo'lgan yo'l
yakuniy cho'qqi o'yini.
Tsiklning uzunligi uning tarkibiy qismlarining soni
qovurg'alar.
Agar uning qirralari bo'lsa, tsikl oddiy deb ataladi
takrorlanmaydi.
Agar tsikl elementar deb ataladi
oddiy va undagi uchlari takrorlanmaydi.

Ulanish komponentlari

Ixtiyoriy grafikning uchlari mumkin
uchun sinflarga bo'linadi
bir xil sinfning istalgan ikkita uchi v1
va v2 - v1 dan v2 gacha yo'l bor
Bu sinflar komponentlar deb ataladi
ulanish.
Grafikda aynan bitta komponent bo'lsa
ulanish, keyin grafik chaqiriladi
ulangan.

Grafiklarning mashina tasviri.

Qo'shnilik matritsasi

- G grafikning uchlarini raqamlaymiz
1 dan n gacha bo'lgan ketma-ket butun sonlar;
- n × n va kvadrat jadval tuzamiz
uni nol bilan to'ldiring;
- Agar chekka ulanishi mavjud bo'lsa
i va j uchlari, keyin (i, j) va (j, i) pozitsiyalarida.
birliklarni qo'yish;
- Olingan jadval chaqiriladi
Grafikning qo'shnilik matritsasi G.

Misol

Qo'shni matritsaning ba'zi aniq xususiyatlari

- Agar cho'qqi izolyatsiya qilingan bo'lsa, unda uning chizig'i va
ustun butunlay nol bo'ladi;
- Har bir satr (ustun) uchun birliklar soni
mos keladigan darajaga teng
tepaliklar;
- Yo'naltirilmagan grafik uchun matritsa
ga nisbatan qo'shnilik simmetrikdir
asosiy diagonal;
- Loop yoqilgan birlikka mos keladi
asosiy diagonal.

Digraf uchun umumlashtirish

Digraf uchun qo'shnilik matritsasi
xuddi shunday qurish mumkin
yo'l, lekin tartibni hisobga olish uchun
vertices, buni qilishingiz mumkin:
Agar yoy j uchidan boshlansa va
k cho'qqisiga, so'ngra (j, k) pozitsiyasiga kiradi.
qo'shnilik matritsasi 1 ga o'rnatiladi va ichida
pozitsiyasi (k, j) -1 o'rnatildi.

Insidans matritsasi

- G grafikning uchlarini raqamlaymiz
1 dan boshlab ketma-ket butun sonlar
n;
- Keling, to'rtburchaklar stol quramiz
n satr va m ustun (ustunlar
grafikning chetlariga mos keladi);
- j-chi chetining uchi bo'lsa
tepasi k, keyin holatda
(k, j) bittaga o'rnatiladi. Umuman
boshqa holatlar nolga o'rnatiladi.

Digraf uchun insidans matritsasi

- Agar j-chi yoy k cho'qqisidan chiqadi,
keyin 1 (k, j) holatiga qo'yiladi;
- Agar j-yoyi k cho'qqisiga kirsa, u holda
pozitsiyasi (k, j) -1 ga o'rnatiladi.
- Boshqa hollarda, (k, j) holatida
nol qoldi.

Matritsaning ustunlaridan boshlab
hodisalar qirralarni tasvirlaydi, keyin
har bir ustun bo'lmasligi mumkin
nolga teng bo'lmagan ikkitadan ortiq elementlar

Insidans matritsasiga misol

Qovurg'alar ro'yxati

Grafikni ifodalashning yana bir usuli
- ikki o'lchovli massiv (juftlar ro'yxati).
Juftlar soni qovurg'alar soniga teng
(yoki yoylar).

Qirralarning ro'yxatiga misol

Turli taqdimot usullarini solishtirish

- Qirralarning ro'yxati eng ixcham va
insidans matritsasi eng kam
ixcham;
- Insidans matritsasi qachon foydalidir
tsikllarni qidirish;
- Qo'shnilik matritsasi osonroq
qolganlari foydalanish uchun.

Grafik o'tish

Grafikni chetlab o'tish uning ustida takrorlash deyiladi
shunday cho'qqilar har bir cho'qqi
bir marta ko'rilgan.

Shartnoma - 1

Grafikni qidirishdan oldin
n cho'qqi bilan Chk massivini yarating
n ta element va uni to'ldiring
nollar.
Agar Chk [i] = 0 bo'lsa, u holda i-chi uchi Ko'proq
ko'rilmagan.

Shartnoma - 2

Keling, ma'lumotlar strukturasini yarataylik
(saqlash) biz bo'ladi
jarayondagi cho'qqilarni eslab qolish
chetlab o'tish. Saqlash interfeysi
uchta funktsiyani ta'minlashi kerak:
- yuqori qismini qo'shing;
- yuqori qismini chiqarib oling;
- saqlash joyi bo'sh yoki yo'qligini tekshiring;

Shartnoma - 3

j cho'qqisi qo'yilganda
ombori, deb belgilangan
ko'rilgan (ya'ni o'rnatilgan
Chk [j] = 1)

Bypass algoritmi-1

1) ixtiyoriy boshlang'ich uchini oling,
biz chop etamiz va uni saqlashga kiritamiz;

3) Saqlash joyidan Z uchini oling;
4) Z bilan bog'langan Q cho'qqisi bo'lsa va bo'lmasa
belgilangan, keyin Z ni saqlashga qaytaramiz,
biz Q saqlashga qo'yamiz, biz Q bosamiz;
5) 2-bosqichga o'ting

Aylanib o'tish algoritmi-2

1) Ixtiyoriy boshlang'ich uchini oling va
biz uni omborga keltiramiz;
2) Xotira bo'shmi? HA bo'lsa - tugatish;
3) Z cho'qqisini saqlashdan oling, chop eting va
xotiradan o'chirish;
4) Biz barcha uchlarini omborga joylashtiramiz,
Z bilan bog'langan va hali belgilanmagan;
5) 2-bosqichga o'ting

Qaysi ma'lumotlar tuzilmalari saqlash uchun mos keladi?

- Stack (PUSH - qo'shish; POP - ekstrakti)
- Navbat (ENQUE - qo'shish; DEQUE -
ekstrakti)
Ikkala tuzilma ham tekshirishga imkon beradi
ma'lumotlarning mavjudligi.

Algoritm-1 stek bilan birlashtirilgan
chuqurlik-birinchi yurish deb ataladi
Algoritm-2 navbat bilan birlashtirilgan
kenglik-birinchi o'tish deyiladi

Grafik - chekli V uchlari to'plami va uchlar juftlarini bog'lovchi R qirralar to'plami, G = (V, R). V va R to'plamlarning kardinalliklari N va M ga teng. Qirralar to'plami bo'sh bo'lishi mumkin. Ustlarga har qanday tabiatdagi ob'ektlar (aholi punktlari, kompyuter tarmoqlari) misol bo'ladi. Kenarlarga misollar yo'llar, yon tomonlar, chiziqlar.

Bir chekka bilan bog'langan cho'qqilar qo'shni deyiladi. Umumiy uchiga ega bo'lgan qirralar ham qo'shni deyiladi. Qirra va uning har ikki uchi hodisa deyiladi. Cho'qqining darajasi - unga tushadigan qirralarning soni. Har bir grafik tekislikda qirralarga mos keladigan chiziqlar bilan bog'langan cho'qqilarga mos keladigan nuqtalar to'plami bilan ifodalanishi mumkin.

Grafik marshruti - bu cho'qqilar va qirralarning ketma-ketligi. Agar marshrut yopilgan (tsiklik) bo'lsa, boshlang'ich va oxirgi uchlari bir-biriga to'g'ri kelsa. Agar barcha uchlari va qirralari boshqacha bo'lsa, marshrut oddiy zanjirdir. Agar har bir cho'qqiga boshqasidan kirish mumkin bo'lsa, grafik ulanadi. Kesilgan qirralari bo'lmagan cho'qqilar izolyatsiyalangan deb ataladi.

Hodisa matritsasi

Aloqa ro'yxatlari

Qovurg'alar ro'yxati

Bog'langan og'irlikdagi yo'naltirilmagan grafik grafikning qo'shnilik matritsasi

Minimal og'irlikdagi daraxtni qurish. Kruskal algoritmi Grafikdan barcha qirralar olib tashlanadi va barcha cho'qqilar ajratilgan joyda kengayuvchi subgraf olinadi. Har bir cho'qqi bitta to'plamga joylashtirilgan. Qirralar og'irlikning ortib borish tartibida tartiblangan. Qirralar og'irliklarining ko'tarilish tartibida ketma-ket ravishda kengayuvchi daraxtga kiritiladi.

4 ta holat mavjud: 1) kiritilgan chekkaning ikkala uchi ham bir elementli kichik to‘plamlarga tegishli, keyin ular yangi, bog‘langan kichik to‘plamga birlashtiriladi; 2) cho'qqilarning biri bog'langan kichik to'plamga tegishli, ikkinchisi esa yo'q, keyin ikkinchisini birinchisi tegishli bo'lgan to'plamga kiritamiz; 3) ikkala cho'qqi ham turli bog'langan kichik to'plamlarga tegishli, keyin biz kichik to'plamlarni birlashtiramiz; 4) Ikkala cho'qqi ham bitta bog'langan kichik to'plamga tegishli, keyin biz bu chetni istisno qilamiz.

Grafik uchun minimal vaznli daraxt qurish misoli GG Bajarilishi kerak bo'lgan harakatlar Cho'qqilar to'plami 1-chizma Izolyatsiya qilingan va cho'qqilari bo'lgan kengayuvchi subgrafni qurish Biz 5 ta bitta elementli kichik to'plamni olamiz: (V 1), (V 2), (V 3), (V 4), (V 5) 2Minimal ogʻirlikdagi (R 15) chetini toping va uni yoyiladigan pastki grafaga qoʻshing.Uchli choʻqqilarning bogʻlangan kichik toʻplamini hosil qiling: (V 1, V 5). Kichik toʻplamlarni saqlash (V 2), (V 3), (V 4)

Amallar Bajarilgan cho'qqilar to'plami 3-chizma Qolganlar orasidan minimal og'irlikdagi chetni toping (R 45) va uni o'tkazuvchi pastki chiziqqa qo'shing.Ulangan kichik to'plamga cho'qqi qo'shing: (V 1, V 5, V 4). Kichik to'plamlarni saqlang (V 2), (V 3) 4 Qolganlari orasidan minimal og'irlikdagi (R 23) chetini toping va uni kengaytmali pastki grafaga qo'shing.Yangi bog'langan cho'qqilar kichik to'plamini hosil qiling: (V 2, V 3). Birinchi ulangan kichik to'plamni saqlang (V 1, V 5, V 4).

Amallar Bajarilgan cho'qqilar to'plami 5-chizma Qolganlar orasidan minimal og'irlikdagi chetini toping (R 25) va uni o'tkazuvchi pastki grafaga qo'shing.Kichki to'plamlarni bitta bog'langan kichik to'plamga birlashtiring (V 1, V 5, V 4, V 2, V). 3). 6Qolgan qirralar grafikga kiritilmagan, chunki ularning barcha uchlari allaqachon bitta bog'langan to'plamga tegishli.

Amallar Bajarilgan cho'qqilar to'plami 7-chizma Grafik olinadi, ya'ni: spanning (barcha cho'qqilar yoqilgan); ulangan (barcha cho'qqilarni marshrutlar bilan ulash mumkin); daraxt (davrlarsiz); minimal vaznga ega. 8 Olingan kengaytmali daraxt minimal vaznga ega: R 12 + R 25 + R 15 + R 45 = = 80 9 G grafigining siklik soni g = mn + 1 = 8-5 + 1 = 4 ga to'g'ri keladi. daraxtga kiritilmagan qirralarning soni.

Oʻzgaruvchilarni eʼlon qilish Grafik choʻqqilarining koordinatalarini saqlash uchun ikkita butun sonli besh elementli X va Y massivlari Grafik qirralarining ogʻirliklarini saqlash uchun butun sonli ikki oʻlchovli R massiv. Loop hisoblagichlari uchun butun son oʻzgaruvchilar i, n va k. Saqlash uchun butun sonli oʻzgaruvchi S. minimal vaznli daraxtning qirralari og'irliklarining yig'indisi

5 ta grafik cho'qqilarning tasodifiy koordinatalarini yaratish (i bo'ylab aylanish). Chet og'irliklarini hisoblash. Og'irlangan digrafning qo'shnilik matritsasini hosil qilish (n va k da o'rnatilgan halqalar) O'lchovli yo'naltirilmagan grafikning qo'shnilik matritsasini chiqarish - boshlang'ich matritsa elementlarining yarmi (boshlang'ich qiymat k = n + 1) Dastur tanasi