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

На възлите на графа се съпоставят номера от 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


Други реферати:
Съвкупно търсене
Същност и общи характеристики на брутния продукт
Показатели за измерване на макроикономиката. БНП, БВП, Банки, Пари
Макроикономически проблеми, подходи и теории, политика
Заетост на работната сила


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



Заетост на работната сила - Facebook Image
Сайтът се поддържа от DH Studio | pomagalo1.com © 2012 | Общи условия