Algoritm tushunchasi

elementar deb nomlanadi.
Graf turlari. Yoʻnaltirilgan graf - (qisqacha orgraf) - qirralari
yoʻnaltirilgan graf . Yoʻnaltirilmagan graf - uchlar juftligi tartiblanmagan graf. Bogʻlangan graf - bu har qanday uch juftligi oʻrtasida kamida bitta yoʻl mavjud boʻlgan graf.
Daraxt - bu bogʻlangan asiklik grafik, ya’ni sikllar yoʻq va tepalik
juftligi orasida bitta yoʻl bor (18-rasm). Kirishning nol darajasiga ega
boʻlgan uch daraxtning ildizi, chiqish nol darajaga ega tugunlar esa
barglar deb nomlanadi.
28 Grafning tasvirlanish usullari (qo’shnilik matritsasi, insidentlik matritsasi, qo’shnilik ro’yxati)
Qoʻshnilik matritsasini n-tartibli A=[ai,aj] nosimmetrik kvadrat matritsa sifatida aniqlaymiz, unda aij elementlar 1 ga teng, agar grafda {vi,Vj} qirrasi boʻlsa, ya’ni vi va vj qoʻshni boʻlsa, 0 ga teng, agar bunday qirra mavjud boʻlmasa.

Insidentlik matritsasi. Insidentlik matritsasi - bu grafning
elementlari (qirra - uch) orasidagi bogʻlanishlar koʻrsatiladigan grafni
tasvirlash shakli. Matritsaning ustunlari qirralarga, satrlar uchlarga
toʻgʻri keladi. Demak, matritsa kvadrat boʻlmaydi. Matritsa
yacheykasidagi nolga teng boʻlmagan qiymat uch va qirra (ularning
insidentligi) oʻrtasidagi munosabatni bildiradi.

Qoʻshnilik roʻyxati. Qoʻshnilik roʻyxati - bu grafni uchlar roʻyxati
("roʻyxatlar roʻyxati") toʻplami sifatida koʻrsatish usuli - grafning har bir
uchi qoʻshni uchlar roʻyxatiga toʻgʻri keladi. Masalan, 1 -rasmni biz
quyidagi qoʻshnilik roʻyxati bilan tavsiflashimiz mumkin:
a: {b, c, d, e}
b: {a}
c: {a, d}
d: {a, c, e}
e: {a, f}
f: {e}

29 Graflar ustida amallar
Graflar bilan ishlashda barcha asosiy amallar (masalan, grafni bitta
koʻrinishda ikkinchisiga oʻtkazish, bosib chiqarish yoki grafni chizish)
uning tizimli oʻtishini, ya’ni grafning har bir uchiga va har bir qirrasiga
tashrif buyurishni nazarda tutadi. Ushbu algoritmlarning eng mashhurlari grafda oʻtish boʻyi boʻyicha qidiruv (DFS) va oʻtish eni boʻyicha qidiruv (BFS) algoritmlari boʻlib, ular qoʻllaniladigan muammolarni hal qilish uchun koʻplab boshqa algoritmlar uchun asos boʻlib xizmat qiladi.
BFS algoritmi. Tasvirdan koʻrinib turibdiki, algoritmning oʻzi juda
ahamiyatsiz. Tashrif uchun uchlar navbati saqlanib qoladi. Keyingi
uchga tashrif buyurganida, hali tashrif buyurmagan va hali navbatda
boʻlmagan barcha qoʻshnilari navbatga qoʻshiladi. Uchga allaqachon
tashrif buyurilganligini tekshirish uchun bir qator yorliqlardan
foydalaniladi.
Grafda oʻtish boʻyi boʻyicha qidiruv (DFS) - bu graf uchlaridan
oʻtishning rekursiv algoritmi. Agar boʻyi boʻyicha birinchi qidirish usuli
nosimmetrik tarzda bajarilgan boʻlsa (grafning uchlari darajalar boʻyicha
koʻrib chiqilgan boʻlsa), unda bu usul iloji boricha chuqurroq harakat
qilishni oʻz ichiga oladi. Keyingi rivojlanishning mumkin emasligi
shundan iboratki, keyingi qadam harakatlanishning bir nechta variantiga
ega boʻlgan (ulardan biri toʻliq oʻrganib chiqilgan), ilgari tashrif
buyurgan uch oxirgisiga oʻtish boʻladi.
30 Daraxtlar grafning xususiy holati sifatida
Daraxt - bu bogʻlangan asiklik graf, ya’ni sikllar yoʻq va uchlar
juftligi orasida bitta yoʻl bor (29-rasm). Kirishning nol darajasiga ega
boʻlgan uch daraxtning ildizi, chiqish nol darajaga ega tugunlar esa