Графи математика

На възлите на графа се съпоставят номера от 1 до n или имена, които лесно се преобразуват в числа. Най – често използваният начин за представяне на граф е матрицата на съседство – двумерен масив с размери n*n с булеви стойности, в които елемент с индекси v и w има стойност true когато има дъга между върховете v и w. При неориентираните графи, на практика, всяка дъга се представя с две стойности, съответстващи на дъга v, w и w, v. Възможно е да се пази само половината матрица, но тъй като в някои езици за програмиране това е трудно за реализиране, то обикновено се използва цялата матрица.

При граф с тегла матрицата може д асъдържа теглото на съответната дъга, т.е. стойността на елемента с индекси v, w е теглото на дъгата от v към w. Ако няма дъга от v към w то съответния елемент на матрицата може да съдържа много голяма или много малка стойност в зависимост от задачата, която се решава.

Въвеждането на граф и създаване на матрица на съседство на ориентиран граф без тегла:

1. Program adjMatrix;

2. Const maxN=100;

3. Var a:array [1..maxN, 1..maxN] of Boolean;

4. j, v, w, n, e:integer;

5. begin

6. readln(n, e);

7. for v:=1 to n do

8. for w:=1 to n do a[v, w]:=false;

9. for j:=1 to E do

10. begin

11. readln(v, w);

12. a[v, w]:=true;

13. end;

14. end.

За неориентиран граф освен дъгата (v, w) трябва да се прибавя и обратната дъга (w, v). За целта ще добавим след ред 12:

a[w, v]:=true;

За графи, които не съдържат много дъги, е удобно представяне в списъци на съседства: За всеки възел да се създава списък от възлите, с които той е свързан.

Въвеждане на граф и създаване на списъци на съседство на ориентиран граф без тегла:

1. Program adjList;

2. Const maxN=100;

3. Type link=^node;

4. node=record v:integer; next:link end;

5. var j, v, w, e, n:integer;

6. t, z:link;

7. adj:array [1..maxN] of link;

8. begin

Други реферати:
Местна система за закрила на детето
Образование в бъдеще време
Модели на социалната патология
Социологически анализ
Различни типове модерни общества-либерален, комунистически, фашистки


Изтегли реферата