Texnologiyalari ha’m kommunikatsiyani rawajlandiriw ministirligi muxammed al-xorezmiy atindag’i tashkent informatsiyaliq texnologiyalari universiteti

2. Graflarni ańlatıw usılları
Yo'naltirilmagan, jóneltirilgen hám o'girlikka iye bolǵan graflarni kompyuter programmalastırıw tilleri yadsında ańlatıw, yaǵnıy yadta shólkemlestiriw ushın statikalıq strukturası matritsadan yamasa dinamikalıq strukturası dizimlerden paydalanıw múmkin. Hár qanday máselelerinde hár bir usılınıń óziniń abzallıǵı hám kemshiliklerine iye esaplanadı. Yo'naltirilmagan, jóneltirilgen hám o'girlikka iye bolǵan graflarni ańlatıw ushın hár usılınıń óziniń qaǵıyda tiykarında qáliplesedi. Sonday tórtew usıllarǵa toqtalıp ótemiz:
• Qospa matritsa (adjacency matrix);
• Intsidientlik matritsa (incidence matrix);
• Qońsılıq dizimi (adjacency list);
• Qırlar dizimi (edges list).
G grafning qospa matritsasi bul n-ólshemli A kvadrat matritsa bolıp,
graf ushın :
Aij = 1 agar i hám j túyinler qır menen birlestirilgen bolsa
Aij = 0 agar i hám j túyinler ortasında qır ámeldegi bolmasa
orgraf ushın :
Aij = 1 agar i túyinnen j túyinge ayqulaq ámeldegi bolsa
Aij = 0 agar i hám j túyinlerde ayqulaq tamamlanmagan bolsa
vaznga iye graf ushın :
Aij = Wij agar i hám j túyinler qır (ayqulaq) menen birlestirilgen bolsa
Aij = ∞ agar i hám j túyinler qır (ayqulaq) ámeldegi bolmasa
Qospa matritsa tiykarǵı qiyiqiga semmitrik boladı, eger yo'naltirilmagan grafni ańlatpalasa, orgraflarda bolsa simmetrik bolmaǵan boladı.
Qospa matritsaning qolaylıq tárepleri tómendegilerde:
 Qır (ayqulaq) qushish hám óshiriw ańsat;
 Túyinler qońsılaslıǵın tekseriw.
Qospa matritsaning qolaysızlıqları bolsa tómendegishe:
 Túyinlerdi kirgiziw yamasa óshiriw;
 Siyrek graflar menen islew.
Tómendegi suwretde grafik hám oǵan teń keletuǵın qońsılas matritsa kórsetilgen.

#include
using namespace std;
class Graph {
private:
bool** adjMatrix;
int numvertices;
public:
Graph (int numvertices) {
this->numvertices = numvertices;
adjMatrix = new bool*[numvertices];
for (int i = 0; i < numvertices; i++) {
adjMatrix[i] = new bool[numvertices];
for (int j = 0; j < numvertices; j++)
adjMatrix[i][j] = false;}}
void addEdge (int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;}
void removeEdge (int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;}
void toString () {
for (int i = 0; i < numvertices; i++) {
cout << i << " : ";
for (int j = 0; j < numvertices; j++)
cout << adjMatrix[i][j] << " ";
cout << " \n";}}
~Graph () {
for (int i = 0; i < numvertices; i++)
delete[] adjMatrix[i];
delete[] adjMatrix;}};
int main () {
Graph g (4);
g. addEdge (0, 1);
g. addEdge (0, 2);
g. addEdge (1, 2);
g. addEdge (2, 0);
g. addEdge (2, 3);
g. toString ();
}
Nátiyje:
0:0 1 1 0
1:1 0 1 0
2:1 1 0 1
3:0 0 1 0

G grafning intsidientlik matritsasi bul n-qatar (túyinler) hám m-ústinler (qırlar ) den shólkemlesken B matritsa bolıp, ol jaǵdayda:

graf ushın :
Bij = 1 agar i túyin j qır menen dúgisken bolsa
Bij = 0 agar i túyin j qır menen to'qnashmagan bolsa
orgraf ushın :
Bij = -1 agar i túyin j doǵanıń bası bolsa
Bij = 0 agar i túyin j ayqulaq menen to'qnashmagan bolsa
Bij = 1 agar i túyin j doǵanıń aqırı bolsa
vaznga iye graf ushın :
Bij = ±Wij agar i túyin ayqulaq bası (aqırı ) bolsa
Bij = 0 agar i túyin j ayqulaq menen to'qnashmagan bolsa
Intsidientlik matritsaning qolaylıq tárepleri tómendegilerde:
 Qır (ayqulaq) ólshemin yamasa baǵdarın ózgertiw;
 Qır (ayqulaq) larni qushish yamasa óshiriw;
 Dúgilisiw (intsidientlik) ni tekseriw.
Intsidientlik matritsaning qolaysızlıqları bolsa tómendegishe:
 Túyinlerdi qushish yamasa óshiriw;
 Siyrek graflar menen islew.
Adjacency Matrix
• Incidene matritsasi wákili ol esaplanayotganda O (vx E) bos jaydı aladı. Tolıq grafik ushın qırlardıń sanı v (v-1) / 2 boladı. Sonday etip, Incidene matritsasi yadta úlken jay iyeleydi
Kirisiw


Chiqish