Grafikda bog’liq kompenentlarini qidirish algaritmlari
![Graflarning vizual namoyish qilinishi Odatda zanjir mustaqil graf sifatida emas,
balki ba’zi bir graflarning bir qismi sifatida qaraladi. Zanjirning uzunligi - uni
tashkil etuvchi qirralarning soni. Oddiy zanjirning uzunligi o z ichiga olgan grafʻ
uchlari sonidan, umumiy zanjirning uzunligi esa ushbu graf qirralarining sonidan
oshmasligi aniq. Graflar nazariyasida zanjir tushunchasi keng qo llaniladi.
ʻ
Masalan, bog langan grafni har qanday uchlar juftligi kamida bitta zanjir bilan
ʻ
bog langan graf sifatida belgilash mumkin. Sikllar. Sikl (oddiy sikl) - bu yopiq
ʻ
zanjir (oddiy zanjir). Oddiy siklga ?????? 8 grafi misol bo la oladi. Oddiy siklni
ʻ
ifodalovchi graf ???????????? bilan belgilanadi. Zanjirlarda bo lgani kabi, sikllarni ba’zi bir
ʻ
graflarning qismlari sifatida ko rib chiqish qiziq. 85 Regulyar graflar. 16-rasmdagi
ʻ
?????? 1, ?????? 3,8, ?????? 11 graflari ularning har birida barcha uchlar bir xil darajaga ega
ekanligi bilan ajralib turadi. Bunday graflar regulyar yoki bir jinsli deb nomlanadi.
20-rasmda uchinchi, to rtinchi va beshinchi darajadagi muntazam sakkizta uchli
ʻ
graflar ko rsatilgan.
ʻ
Grafni tasvirlash usullari Grafni tasvirlash uchun bir nechta usullardan
foydalaniladi. Graflardan o tish uchun siz o zingizning muammoingizni eng
ʻ ʻ
samarali hal qiladiganlardan foydalanishingiz kerak. Ko pincha, tanlov qo shnilik
ʻ ʻ
matritsasi va qo shnilik ro yxati o rtasida bo ladi (quyidagi jadval ikkala
ʻ ʻ ʻ ʻ
yondashuvning samaradorligini taqqoslaydi). Shu bilan birga, o rnatilgan C-
ʻ
massivga tayanib, o zingizning ma’lumotlar tuzilmalaringizni modellashtirishingiz
ʻ
va STD-da mavjud bo lgan turli xil konteynerlardan foydalanishingiz mumkin.
ʻ
Qo shnilik matritsasi. Qo shnilik matritsasini n-tartibli
ʻ ʻ ?????? = [ ???????????? , ???????????? ] nosimmetrik
kvadrat matritsa sifatida aniqlaymiz, unda ???????????? , ?????? elementlar 1 ga teng, agar grafda
{ ???????????? , ???????????? } qirrasi bo lsa, ya’ni
ʻ ???????????? va ???????????? qo shni bo lsa, 0 ga teng, agar bunday qirra ʻ ʻ
mavjud bo lmasa. Ta’rifdan kelib chiqadiki, har qanday i uchun ∑
ʻ ???????????? , ?????? ?????? ?????? =1 =
7](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_7.png)
![Matematikada tsiklik grafi tsiklni o'z ichiga olgan grafni yoki tsikllarning turli xil
ta'riflari bilan tsikl bo'lgan grafni anglatishi mumkin. Qarang: sikl (grafik
nazariyasi), grafdagi sikl. O'rmon (graf nazariyasi), tsiklsiz yo'naltirilmagan graf.
Ikki bog'langan graf, har bir chekkasi tsiklga tegishli bo'lgan yo'naltirilmagan
grafik.Bu erda biz ikkita narsani qilishni xohlaymiz.Grafiklarni sinab ko'rish uchun
norasmiy algoritm haqida tasavvurga ega bo'ling.
Grafning asiklik ekanligini aniqlash uchun axborot tuzilmamiz ro yxati vaʻ
funksiyalaridan qanday foydalanishni ko rsating.
ʻ
Yo'naltirilgan grafikning ba'zi bir ko'rinishini hisobga olgan holda, biz tsikllar
mavjudligini bilishni xohlashimiz mumkin (tugundan o'ziga qaytib, ehtimol boshqa
tugunlar orqali).
Hech bo'lmaganda bitta shunday tsiklga ega bo'lgan grafik tsiklik, bo'lmagani esa
asiklik deb ataladi. Asil yo'naltirilgan grafiklar, shuningdek, daglar deb ataladi.
Diagrammada tsikl yo'qligi aniq ko'rsatilgan Tavsiya etilgan amaliyot
Yo'naltirilgan grafikda tsiklni aniqlang Urunib ko'r! Yondashuv: Muammoni
quyidagi fikrga asoslanib hal qilish mumkin: Yo'naltirilgan grafikdagi tsiklni
topish uchun biz chuqurlikdan birinchi o'tish (DFS) texnikasidan foydalanishimiz
mumkin. Bu grafikda orqa chekka [ya'ni, tugun o'z ajdodlaridan biriga ishora
qiluvchi] bo'lsagina, grafikda tsikl mavjud degan fikrga asoslanadi. Orqa tomonni
aniqlash uchun biz hozirgacha tashrif buyurilgan tugunlarni va joriy rekursiya
stekidagi tugunlarni (ya'ni, biz tashrif buyurayotgan joriy yo'lni) kuzatib
borishimiz kerak. Agar rekursiya paytida biz allaqachon rekursiya stekidagi
tugunga erishsak, grafikda tsikl mavjud. Eslatma: Agar grafik uzilgan bo'lsa, DFS
o'rmonini oling va orqa qirralarni tekshirish orqali alohida daraxtlardagi tsiklni
tekshiring. Fikrni amalga oshirish uchun quyidagi bosqichlarni bajaring: Quyidagi
parametrlarga ega bo'lgan rekursiv dfs funksiyasini yarating - joriy cho'qqi, tashrif
buyurilgan massiv va rekursiya to'plami. Joriy tugunni tashrif buyurilgan deb
belgilang, shuningdek, rekursiya stekidagi indeksni belgilang. Barcha cho'qqilar va
har bir cho'qqi uchun tsiklni takrorlang, agar u hali tashrif buyurilmagan bo'lsa,
rekursiv funktsiyani chaqiring (Bu qadam grafiklar o'rmoni mavjud bo'lsa, biz har
bir o'rmonni tekshirayotganimizga ishonch hosil qilish uchun amalga oshiriladi):
Har bir rekursiya chaqiruvida joriy cho'qqining tashrif buyurilmagan barcha
qo'shni cho'qqilarini toping: Agar qo'shni cho'qqi allaqachon rekursiya to'plamida
belgilangan bo'lsa, haqiqiy qiymatini qaytaring. Aks holda, o'sha qo'shni cho'qqi
uchun rekursiv funktsiyani chaqiring. Rekursiya qo'ng'irog'idan qaytganingizda,
joriy tugun endi kuzatilayotgan yo'lning bir qismi emasligini ko'rsatish uchun
rekursiya to'plamidan joriy tugun belgisini olib tashlang. Funktsiyalardan biri rost
bo'lsa, kelajakdagi funksiya chaqiruvlarini to'xtating va javob sifatida true
qiymatini qaytaring.
9](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_9.png)
![Tasvir:
Quyidagi grafni ko'rib chiqing:
Tasavvur qilaylik, biz iteratsiyani 0 cho'qqisidan boshlaymiz. Dastlab, tashrif
buyurilgan[] va recStack[] massivlarida 0 belgilanadi, chunki u joriy yo'lning bir
qismidir.
Endi 0 ning ikkita qo'shni cho'qqi 1 va 2 bor. Keling, 1 cho'qqiga o'tishni ko'rib
chiqaylik. Shunday qilib, 1 tashrif buyurilgan[] va recStack[] da belgilanadi.
10](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_10.png)
![Vertex 1 ga tashrif buyuriladi 1-vertex faqat bitta qo'shni cho'qqiga ega. 2 uchun
rekursiv funksiyani chaqiring va uni tashrif buyurilgan[] va recStack[] da
belgilang.
Vertex 2 shuningdek, ikkita qo'shni cho'qqiga ega.
Vertex 0 ga tashrif buyurilgan va allaqachon recStack[] da belgilangan.
Shunday qilib, agar birinchi navbatda 0 belgilansa, biz tsikl mavjud degan javobni
olamiz.
Boshqa tomondan, birinchi navbatda 3-vertex belgilansa, tashrif
buyurilgan[] va recStack[] da 3 belgilanadi.
11](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_11.png)
![3 uchun rekursiya chaqiruvidan qaytganingizda, u recStack[] dan belgidan olib
tashlanadi, chunki u hozir kuzatilayotgan yo'lning bir qismi emas.
Endi bizda tekshirish uchun faqat bitta variant bor, u allaqachon recStack[] da
belgilangan 0 vertex. Shunday qilib, biz tsikl mavjud degan xulosaga kelishimiz
mumkin. Agar biz 0 ning o'zidan 2 cho'qqisiga xuddi shu tarzda o'tgan bo'lsak,
tsiklni ham topishimiz mumkin.
// Grafidagi siklni aniqlash uchun C++ dasturi
#include <bits/stdc++.h>
using namespace std;
12](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_12.png)
![class Graph {
// No. of vertices
int V;
// Qo'shni ro'yxatlarni o'z ichiga olgan massivga ko'rsatgich
list<int>* adj;
// isCyclic() tomonidan foydalaniladi
bool isCyclicUtil(int v, bool visited[], bool* rs);
public:
Graph(int V);
void addEdge(int v, int w);
bool isCyclic();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
// v ro'yxatiga w qo'shing.
adj[v].push_back(w);
}
// DFS funktsiyasi tsikl mavjudligini aniqlash uchun
bool Graph::isCyclicUtil(int v, bool visited[],
bool* recStack)
{
if (visited[v] == false) {
// Joriy tugunni tashrif buyurilgan deb belgilang
// va rekursiya stekining bir qismi
visited[v] = true;
recStack[v] = true;
// Bunga qo'shni barcha tepaliklar uchun takrorlash
// cho'qqi
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i]
&& isCyclicUtil(*i, visited, recStack))
return true;
else if (recStack[*i])
13](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_13.png)
![return true;
}
}
// Rekursiya stekidan tepani olib tashlang
recStack[v] = false;
return false;
}
// Agar grafikda sikl bo'lsa, true qiymatini qaytaradi, aks holda noto'g'ri
bool Graph::isCyclic()
{
// Barcha uchlarini tashrif buyurilmagan deb belgilang
// va rekursiya stekining bir qismi emas
bool* visited = new bool[V];
bool* recStack = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
recStack[i] = false;
}
// Rekursiv yordamchi funksiyani chaqirish
// turli DFS daraxtlaridagi tsiklni aniqlash uchun
for (int i = 0; i < V; i++)
if (!visited[i]
&& isCyclicUtil(i, visited, recStack))
return true;
return false;
}
// Driver code
int main()
{
// Create a graph
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
// Function call
14](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_14.png)
![// No. of vertices
int V;
// Qo'shni ro'yxatlarni o'z ichiga olgan massivga ko'rsatgich
list<int>* adj;
// isCyclic() tomonidan foydalaniladi
bool isCyclicUtil(int v, bool visited[], bool* rs);
public:
Graph(int V);
void addEdge(int v, int w);
bool isCyclic();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
// v ro'yxatiga w qo'shing.
adj[v].push_back(w);
}
//DFS funktsiyasi tsikl mavjudligini aniqlash uchun
bool Graph::isCyclicUtil(int v, bool visited[],
bool* recStack)
{
16](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_16.png)
![if (visited[v] == false) {
// Joriy tugunni tashrif buyurilgan deb belgilang
// va rekursiya stekining bir qismi
visited[v] = true;
recStack[v] = true;
// Bunga qo'shni barcha tepaliklar uchun takrorlash
// cho'qqi
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i]
&& isCyclicUtil(*i, visited, recStack))
return true;
else if (recStack[*i])
return true;
}
}
// Rekursiya stekidan tepani olib tashlang
recStack[v] = false;
return false;
}
// Agar grafikda sikl bo'lsa, true qiymatini qaytaradi, aks holda noto'g'ri
bool Graph::isCyclic()
{
// Barcha uchlarini tashrif buyurilmagan deb belgilang
// va rekursiya stekining bir qismi emas
17](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_17.png)
![bool* visited = new bool[V];
bool* recStack = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
recStack[i] = false;
}
// Rekursiv yordamchi funksiyani chaqirish
// turli DFS daraxtlaridagi tsiklni aniqlash uchun
for (int i = 0; i < V; i++)
if (!visited[i]
&& isCyclicUtil(i, visited, recStack))
return true;
return false;
}
// Driver code
int main()
{
// Create a graph
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
18](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_18.png)
![// Function call
if (g.isCyclic())
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
Boshqaruv bo'yicha grafik dasturlashda bog'liq komponentlarni qidirish
uchun algoritmlar mavjud. Misol uchun, quyidagi C++ dasturida DFS (Depth-First
Search) algoritmini ishlatish orqali bog'liq komponentlarni topish mumkin:
#include <iostream>
#include <vector>
using namespace std;
void DFS(vector<vector<int>>& Matrix, vector<bool>& visited, int node) {
visited[node] = true;
for (int i = 0; i < Matrix[node].size(); i++) {
if (Matrix[node][i] == 1 && !visited[i]) {
DFS(Matrix, visited, i);
}
}
}
int findConnectedComponents(vector<vector<int>>& Matrix) {
int n = adjMatrix.size();
vector<bool> visited(n, false);
int componentCount = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
DFS(Matrix, visited, i);
componentCount++;
}
}
return componentCount;
}
int main() {
vector<vector<int>> graph = {
{0, 1, 0, 1},
19](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_19.png)
![#include <bits/stdc++.h>
std nom maydonidan foydalanish;
# MAXN 1000005 ni aniqlang
// grafik tuzing
vektor<int>v[MAXN];
// grafikga chekka qo'shish funksiyasi
void add_edge(int a, int b, int fre[])
{
// a dan b gacha yo'l bor.
v[a].orqaga_surish(b);
bepul[b]++;
}
// topologik tartiblash funksiyasi
vektor<int> topologik_tartiblash(int fre[], int n)
{
navbat<int>q;
// barcha uchlarini kiriting
// ota-onasi yo'q.
uchun (int i = 0; i < n; i++)
agar (!bepul[i])
qpush(i);
vektor<int>l;
// Kan algoritmidan foydalanish
22](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_22.png)
![// topologik tartiblash
while (!q.empty()) {
int u = q.front();
q.pop();
// vektorga navbatning oldingi elementini kiriting
l.push_back(u);
// hamma narsadan o'ting
uchun (int i = 0; i < v[u].size(); i++) {
fre[v[u][i]]--;
// chastota nolga teng bo'lsa, qo'shing
// navbat uchun bu cho'qqi.
agar (!fre[v[u][i]])
q.push(v[u][i]);
}
}
qaytish;
}
// Yo'llar sonini qaytaruvchi funksiya
int soni ofPaths(int source, int destination, int n, int fre[])
{
// topologik tartiblash
vektor<int> s = topologik_tartiblash(fre, n);
// kerakli javobni saqlash uchun.
23](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_23.png)
![int dp[n] = {0};
// manzildan javob
// manzilga - 1.
dp[maqsad] = 1;
// teskari tartibda harakat qilish
uchun (int i = s.size() - 1; i >= 0; i--) {
uchun (int j = 0; j < v[s[i]].size(); j++) {
dp[s[i]] += dp[v[s[i]][j]];
}
}
dpni qaytarish;
}
// Haydovchi kodi
int main()
{
// bu yerda uchlari 0 dan n-1 gacha raqamlangan.
int n = 5;
int manba = 0, maqsad = 4;
// bo'lmagan cho'qqilar sonini hisoblash uchun
// ota-onasi bor.
int fre[n] = {0};
// grafikning barcha qirralarini qo'shish uchun
add_edge(0, 1, fre);
24](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_24.png)
![bekor alltopologicalSortUtil(vektor<int> va res,
bool tashrif buyurdi[]);
ommaviy:
Grafik (int V); // Konstruktor
// grafikga chekka qo'shish funksiyasi
void addEdge(int v, int w);
// Barcha topologik tartiblarni chop etadi
void alltopologicalSort();
};
// Grafik konstruktori
Grafik::Graph(int V)
{
bu->V = V;
adj = yangi ro'yxat<int>[V];
// Barcha indekslarni 0 bilan boshlash
uchun (int i = 0; i < V; i++)
indegree.push_back(0);
}
// Kenar qo'shish uchun yordamchi dastur
void Graph::addEdge(int v, int w)
{
adj[v].orqaga_surish(w); // v ro'yxatiga w qo'shing.
// w ning ichki darajasini 1 ga oshirish
indegree[w]++;
}
// Hammasini chop etish uchun asosiy rekursiv funksiya
// topologik turlar
void Graph::alltopologicalSortUtil(vektor<int>& res,
bool tashrif buyurdi[])
{
// Barcha topologiyalar topilganligini ko'rsatish uchun
// yoki yo'qmi
bool bayrog'i = noto'g'ri;
uchun (int i = 0; i < V; i++)
{
// Agar indeks 0 bo'lsa va hali tashrif buyurmagan bo'lsa
// faqat shu cho'qqini tanlang
agar (indegree[i] == 0 && ! tashrif buyurilgan[i])
{
26](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_26.png)
![// qo'shni cho'qqilar ko'rsatkichini kamaytirish
list<int>:: iterator j;
uchun (j = adj[i].begin(); j != adj[i].end(); j++)
indegree[*j]--;
// natijada, shu jumladan
res.push_back(i);
tashrif buyurilgan[i] = rost;
alltopologicalSortUtil(res, tashrif buyurilgan);
// qayta o'rnatish tashrif buyurilgan, res va indegree uchun
// orqaga qaytish
tashrif buyurilgan[i] = noto'g'ri;
res.erase(res.end() - 1);
uchun (j = adj[i].begin(); j != adj[i].end(); j++)
gradus [*j]++;
bayroq = rost;
}
}
// Agar barcha uchlari tashrif buyurilgan bo'lsa, biz bu erga etib boramiz.
// Shunday qilib, biz bu erda yechimni chop etamiz
agar (!bayroq)
{
uchun (int i = 0; i <res.size(); i++)
cout << res[i] << " ";
cout << endl;
}
}
// Funksiya barcha Topologik saralashni amalga oshiradi.
// U rekursiv alltopologicalSortUtil() dan foydalanadi.
void Graph::alltopologicalSort()
{
// Barcha uchlarini tashrif buyurilmagan deb belgilang
bool *ziyorat qilingan = yangi bool[V];
uchun (int i = 0; i < V; i++)
tashrif buyurilgan[i] = noto'g'ri;
vektor<int> res;
alltopologicalSortUtil(res, tashrif buyurilgan);
}
27](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_27.png)
![Shunday qilib, asl grafikdagi tugunlar soniga teng bo'lgan bir necha bosqichda
algoritmni tugatish kerak.
Qisman to'g'rilik - bu texnik atama: Agar algoritm tugasa, u buni to'g'ri javob bilan
bajaradi.
Ushbu algoritmni axborot tuzilmalari nuqtai nazaridan qanday ifodalashimiz
mumkin? Oddiylik uchun grafik uchun yoylar ro'yxatini ko'rsatamiz. Quyidagi
grafik uchun buni eslang.
vakillik quyidagicha bo'ladi:
[ [1, 2], [2, 3], [2, 4], [4, 5], [6, 3], [4, 6], [5, 6] ]
Avval barg bor yoki yo'qligini aniqlashimiz kerak. Ta'rifga ko'ra, barg - uni tark
etadigan yoylari bo'lmagan tugun.
Anonim funksiya
(Juftlik) => birinchi (Juftlik) == Tugun
Tugun birinchi elementi bo'lgan har qanday juftlik uchun 1ni qaytaradi.
Bu iboraning o'qilishi "Pair argumenti bilan birinchi(Pair) == Tugun natijasini
qaytaradigan funksiya. == tenglik testi.
Tugunning barg ekanligini aniqlaydigan is_leaf funksiyasini berish uchun biz
ushbu anonim funksiyani rex funktsiyasi find chaqiruviga kiritamiz:
is_leaf(tugun, grafik) =
no((Pair) => first(Pair) == Tugun, Grafik);
Bu erda Grafik bizning yoylar ro'yxati. Agar yo'q ga qo'ng'iroq 1 ni qaytarsa, agar
tugun birinchi elementi bo'lsa, yoy bo'lmasa.
Endi bizda barglar testi bor. Shunday qilib, biz bundan keyin foydalanishimiz
kerak.
Faraz qilaylik, bizda tugunlar ro'yxati mavjud.
Ulardan birortasi barg ekanligini tekshirishimiz mumkin va agar shunday bo'lsa,
bargning identifikatorini quyidagicha qaytarishimiz mumkin:
31](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_31.png)
![find_leaf(Grafik) =
find((tugun) => is_leaf(tugun, grafik), tugunlar(grafik));
find_leaf [ ] ni qaytarsa, barg yo'q. Agar u bo'sh bo'lmagan ro'yxatni qaytarsa, bu
ro'yxatdagi birinchi element barg bo'ladi.
Yana bitta tavsiflovchi funksiya yaratishimiz mumkin:
no_leaf(Graph) = find_leaf(Graph) == [ ];
Tugunlar ro'yxatini qanday olish mumkin:
Juftlar ro'yxatini (juda buta) daraxt sifatida tasavvur qiling.
Misol:
Ro'yxat uchun
[ [1, 2], [2, 3], [2, 4], [4, 5], [6, 3], [4, 6], [5, 6] ]
buta daraxti:
Ushbu daraxtda ishlaydigan rex funktsiyasi barcha tugunlar ro'yxatini, ehtimol
dublikatlari bilan qaytaradi. Ushbu ro'yxatga remove_duplicates ni qo'llash
orqali biz tugunlar ro'yxatini olamiz:
tugunlar (Grafik) =
dublikatlarni_olib tashlash(barglar(Grafik));
Diqqat: Bu daraxtning "barglari" faqat asl grafikning barg tugunlari emas; ular
xohlagancha barcha tugunlarni o'z ichiga oladi.
Endi biz algoritmning qadamlarini funktsiyalar bo'yicha chiqarishga tayyormiz.
Boshlash uchun Grafik asl grafik bo'lsin (juftlar ro'yxati sifatida).
1. Grafikda tugunlar bo'lmasa, to'xtating. Asl grafik asiklikdir.
Grafik [ ] ekanligini tekshirish orqali buni tekshirishimiz mumkin. Agar uning
tugunlari bo'lmasa, unda yoylar ham yo'q va aksincha.
2. Grafikda barg bo'lmasa, to'xtating. Grafik siklikdir.
Biz buni no_leaf (Graph) ni hisoblash orqali sinab ko'rishimiz mumkin. Agar natija
[ ] bo'lsa, grafikda barg yo'q.
3. Grafik bargini tanlang. Yangi grafikni olish uchun bu bargni va bargga kiradigan
barcha yoylarni olib tashlang.
Bizga yana bitta funksiya kerak: bargni grafikdan olib tashlash uchun remove_leaf.
32](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_32.png)
![4. 1-ga o'ting.
Funktsional dasturlashning ruhi shundan iboratki, biz ro'yxatdan biror narsani olib
tashlamaymiz; Buning o'rniga biz unda olib tashlanishi kerak bo'lgan narsasiz
yangi ro'yxat tuzamiz.
Aytaylik, Leaf olib tashlanadigan bargdir. Keyin biz faqat ikkinchi element sifatida
Leaf bilan barcha yoylarni tashlashimiz kerak (u hech qachon birinchi element
bo'lmaydi; nega?):
olib_barg (barg, grafik) =
drop((Pair) => second(Pair) == Leaf, Graph);
Doimgidek,
(Juft) => soniya (Juft) == Barg
anonim funksiya bo‘lib, ikkinchi element barg bo‘lgan juftlik uchun 1 ga teng.
Biz bu funktsiyani soddalashtirishimiz mumkin, faqat barg borligini bilsak, uni
chaqiramiz:
olib_barg (Grafik) =
bargni_olib tashlash(birinchi(barg_topish(Grafik)), Grafik);
Va nihoyat, biz ushbu funktsiyalarga qo'ng'iroqlarni iteratsiyaga erishiladigan
tarzda paketlashimiz kerak. Agar shartli iboralardan foydalansak, bu oddiy:
Shakl
P ? T: F
agar P rost bo'lsa T qiymatiga va P noto'g'ri bo'lsa F qiymatiga baholaydi.
Tezlikni tekshirish uchun umumiy funktsiya ikkita shartli ifodadan foydalanadi:
asiklik (Grafik) =
Grafik == [ ] ? 1 // bo'sh grafik asiklikdir
: no_leaf (Grafik) ? 0 // bargsiz grafik siklikdir
: asiklik(bargni_olib tashlash(Grafik)); // qisqartirilgan grafikni sinab ko'ring
Sharhlar va ikkita sinov holati bilan to'liq acyclic.rex fayli acylic.rex sifatida
topilishi mumkin. Buni rex tomonidan ishga tushirish mumkin
rex acyclic.rex
Fayl yuklangandan so'ng, har qanday misolni alohida-alohida sinab ko'rishingiz
mumkin. Bu erda misol sifatida ishlatiladigan ikkita grafik fayldagi graph1 va
graph2 misollaridir.
Rad etish: Biz bu usul eng samarali ekanligi haqida hech qanday bayonot
bermaymiz. Xuddi shu natijaga erishishning boshqa samarali usullari ma'lum.
Ushbu misol bir nechta funktsional dasturlash g'oyalarini va norasmiy
algoritmdan ishlaydigan funktsional dasturga o'tishni ko'rsatish uchun xizmat
qildi.
Yo'naltirilgan grafikning ildizini hisobga olgan holda, vazifa grafikda tsikl bor
yoki yo'qligini tekshirish.
33](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_33.png)
![Misollar:
Kirish: N = 4, E = 6
Grafikga misol
// Tsikl mavjudligini tekshirish uchun C++ dasturi
// BFS yordamida yo'naltirilgan grafik.
#include <bits/stdc++.h>
using namespace std;
// Grafikni ifodalash uchun sinfclass Graph
{
int V;
// Cho'qqilar soni'
// Qo'shnilar ro'yxatini o'z ichiga olgan massivga ko'rsatgich
list<int>* adj;
public:
Graph(int V); // Constructor
// grafga chekka qo'shish funksiyasi
void addEdge(int u, int v);
// Grafda tsikl mavjud bo'lsa, true qiymatini qaytaradi
// boshqa noto'g'ri.
bool isCycle();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int u, int v)
34](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_34.png)
![{
adj[u].push_back(v);
}
// Agar tsikl mavjud bo'lsa, bu funktsiya true qiymatini qaytaradi // yo'naltirilgan
grafikda, aks holda noto'g'ri qaytariladi.
bool Graph::isCycle()
{
// Hammasining indekslarini saqlash uchun vektor yarating // uchlari. Barcha
ko'rsatkichlarni 0 sifatida boshlang.
vector<int> in_degree(V, 0);
// Ko'rsatkichlarni to'ldirish uchun qo'shnilik ro'yxatini aylantiring
// uchlari. Bu qadam O(V+E) vaqtini oladi
for (int u = 0; u < V; u++) {
for (auto v : adj[u])
in_degree[v]++;
}
// Navbat yarating va barcha uchlarini qatorga qo'ying
// 0 gradus
queue<int> q;
for (int i = 0; i < V; i++)
if (in_degree[i] == 0)
q.push(i);
// Tashrif buyurilgan cho'qqilar sonini ishga tushiring
// 1 src tugun uchun
int cnt = 1;
// Natijani saqlash uchun vektor yarating (topologik
// uchlarini tartiblash)
vector<int> top_order;
// Navbat va navbatdan uchlarini birma-bir olib tashlash
// qo'shnilar ko'rsatkichi 0 ga aylansa
35](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_35.png)
![while (!q.empty()) {
// Navbatning oldingi qismini ajratib oling (yoki navbatni bekor qiling)
// va uni topologik tartibda qo'shing
int u = q.front();
q.pop();
top_order.push_back(u);
// Barcha qo'shni tugunlar orqali takrorlash
// dequeued tugunining u va in-darajasini kamaytiring
// 1 tomonidan
list<int>::iterator itr;
for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
// Agar daraja nolga aylansa, uni navbatga qo'shing
if (--in_degree[*itr] == 0)
{
q.push(*itr);
// elementlarni navbatga surayotganimizda, biz cnt ni
oshiramiz cnt++;
}
}
// Tsikl borligini tekshiring
if (cnt != V)
return true;
else
return false;
}
// Yuqoridagi funktsiyalarni sinab ko'rish uchun haydovchi dasturi
int main(){
// Yuqoridagi diagrammada berilgan grafikni yarating
Graph g(6);
36](/data/documents/15396ab0-be4c-4233-a9a6-68f479d676d8/page_36.png)
Grafikda bog’liq kompenentlarini qidirish algaritmlari MUNDARIJA ASOSIY QISM 1. kirish : 2 . Graflar nazariyasining asosiy tushunchalari 3. Grafning umumiy asosiy elementlari. Graf turlari 4. Grafikda bog’liq kompenentlarini qidirish algaritmlar 5. Algaritmlar qiyosiy taxlil qilish 6. Xulosa 7. Foydanilgan adabiyotlar 1
KIRISH Graflar hayotimizning bir qismidir. Ularni tahlil qilish va sikllarni aniqlash bizga aniqlik, sezgirlik va o'tishlarni tushunish imkonini beradi. Grafni asiklikka tekshirish, graflarning ma'nosi va xususiyatlarini tahlil qilish uchun juda muhimdir. Grafni asiklikka tekshirishda, odatda ma'lumotlarning vaqt oralig'ida o'zgarishlarini ko'rishimiz kerak. Bu ma'lumotlardan foydalanib, o'zgaruvchanligi va o'zgarishlarning sifatini aniqlash imkoniyatiga ega bo'lamiz. Grafni asiklikka tekshirish, ma'lumotlar o'rtasida aloqador munosabatlarni aniqlashga yordam beradi. Grafdagi sikllar esa muhim trendlarni aniqlash uchun ishlatiladi. Sikllar, odatda ma'lumotlardagi muhim o'zgarishlarni, sezgirliklarni yoki nazorat xususiyatlarini ko'rsatadi. Sikllar bizga qaysi tomondan o'zgarishlarni kutishimiz va qanday yo'l harakatini prognazlashimiz haqida fikr beradi. Mening kiritishimning natijasida, grafni asiklikka tekshirish va sikllarni aniqlash, ma'lumotlarning tahlili va aniqlovchi o'tishlarni tushunish uchun muhim vosita sifatida ishlatiladi. Bu amaliyotlar orqali biz ma'lumotlardan qanday foydalanishimizni tushunib, maqsadga muvofiqlashimiz va o'sishimizni boshqarish imkoniyatini oshirishimiz mumkin. 1.1. Grafning umumiy asosiy elementlari. Graf turlari Graflarni o rganish bilan shug ullanadigan diskret matematikaning bo limiʻ ʻ ʻ “Graflar nazariyasi” deb ataladi. Graflar nazariyasida ushbu matematik obyektlarning asosiy tushunchalari, xususiyatlari, tasvirlash usullari va qo llanilish ʻ sohalari batafsil ko rib chiqilgan. Bizni faqat dasturlashda muhim bo lgan jihatlari ʻ ʻ qiziqtiradi. Graflar - bu chiziqlar bilan bog langan nuqtalar to plami. Nuqtalar ʻ ʻ uchlar (tugunlar) chiziqlar esa qirralar (yoylar) deb nomlanadi. Grafning ifodalanishi. Grafning to plam nazariya bo yicha ta’rifi. Bizga ʻ ʻ ?????? - bo sh bo lmagan ʻ ʻ to plam berilgan, masalan { ʻ ?????? 1, ?????? 2, ?????? 3, ?????? 4, ?????? 5 }. Uning barcha ikki elementli ?????? (2) ichki to plamlari to plamini yozamiz. Bizning misolimiz uchun ushbu to plam ʻ ʻ ʻ quyidagicha bo ladi: ʻ 2
Ixtiyor ravishda ba ’ zi bir ?????? ⊆ ?????? (2) ni olamiz , masalan : 〈 ?????? , ?????? 〉 juftligi yo naltirilmagan G grafi deb nomlanadi, unda ʻ ?????? - uchlar to plami, ʻ ?????? - qirralarning to plami, ʻ ?????? (2) to plamining ichki to plami hisoblanadi. ʻ ʻ Yuqoridagilardan kelib chiqib, ushbu ta’rif odatda quyidagicha shakllantiriladi: 〈 ?????? , ?????? 〉 oriyentirlanmagan graflar juftligi deb ataladi, agar ?????? uchlar deb ataladigan bo sh bo lmagan elementlar to plami bo lsa va ʻ ʻ ʻ ʻ ?????? – ?????? dagi qirralar deb ataluvchi turli elementlarning tartibsiz juftlari to plami bo lsa. 80 Graflar nazariyasida turli ʻ ʻ xil munosabatlarni yozishda VG yoki V(G) yozuvlari, G graf qirralarining to plami ʻ uchun EG yoki E(G) yozuvlari ishlatiladi. Grafni namoyish qilishning vizual usuli - bu chizmalar (diagramma), unda uchlar nuqta, doiralar yoki boshqa figuralar bilan tasvirlangan va qirralar juft uchlari tasvirlarini bir-biriga bog laydigan ʻ chiziqlar bilan tasvirlangan. Yuqorida tavsiflangan grafni bunday tasvirlash uchun quyidagi variantlar berilgan. 3
Graf turlari Graf - bu abstrakt obyekt bo lib, uchlar to plami (tugunlar) va qirralarningʻ ʻ to plami - uchlar juftliklari orasidagi bog lanishlardan tashkil topadi (ulanishlar). ʻ ʻ Graf mavzusi juda keng. Graflar diskret matematikaning o rganish mavzusidir (bu ʻ yerda graf tushunchasining aniqroq ta’rifi berilgan). Graf murakkab tuzilgan ma’lumotni tavsiflash uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega. Matematikada graflar paydo bo lishiga Eyler asarlari yordam berdi. Graflar ʻ bilan qayerda uchrashamiz? Ehtimol, ular bilan qayerda uchrashmasligimizni aytish osonroq. Ya’ni biz graflarda juda ko p holatda uchratamiz. Misol qilib ʻ quyidagilarni keltirishimiz mumkin: • Lokal yoki global tarmoq modeli • Algoritmlarning blok-sxemasi • Elektr sxemalar 81 • Oila daraxti (Shajara) • Metro xaritasi • Ma’lumotlar bazasi modeli • Aqlli xaritalar va boshqa ko plab sohalarda ʻ qo llanilib kelmoqda. Ushbu darsda butun graflar nazariyasini olish mumkin emas. ʻ Shuning uchun qisqacha ma’lumotlarni keltirib o tamiz. G graf - G: = (V, E) ʻ tartiblangan juftlik, bu yerda V - uchlarning (yoki tugunlarning) bo sh bo lmagan ʻ ʻ to plami, E esa qirralar deb nomlangan uchlarning juftlari to plamidir. Grafning ʻ ʻ uchlari va qirralari (ular graf elementlari deb ataladi), grafdagi uchlar soni | V | - graf tartibi, qirralarning soni | E | - graf hajmi deb ataladi. B) Daraxt - bu bog langan asiklik graf ʻ 4
Graflar nazariyasining asosiy atamalari. Bu yerda graflar nazariyasidan (diskret matematikaning bir bo limi) atamalarning kichik tanlovini qildik, ammo buʻ atamalar boshqa adabiyotlarda boshqacha berilgan bo lishi mumkin. ʻ Graflar nazariyasining boshlang ich terminologiyasi ʻ O zbek ʻ Рус En Tavsif Uch Вершина vortex Grafning elementi Tugun Узел node node Uch tushunchasi bilan bir xil Qirra Ребро edge Ikki qo shni ʻ uchlarning bog lanishi ʻ Yoy Дуга arc Qirra bilan bir xil, lekin orgrafda emas Aloqa, bog lanish, ʻ munosabat Связь link Graf elementi (qirra yoki yoy) Qo shnilik ʻ Смежность adjacent Ikkita uch o rtasida aloqa ʻ mavjud bo lganini ʻ bildiruvchi atama Insidentlik Инцидентность incident on Uchga nisbatan qirra haqida Daraja Степень degree Uchga tutashgan qirralarning soni Graflar nazariyasining asosiy tushunchalari Grafdagi marshrut - bu har bir uch (oxirgisidan tashqari) ketmaketlikdagi keyingi uchga qirra bilan bog langan ʻ 5