Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV

2. Základní pojmy / Reprezentace grafu v počítači

Konkrétní reprezentace grafu se při práci na počítači často liší podle vlastností grafu. Například víme-li, že graf bude mít hodně vrcholů a relativně málo hran, může být matice zbytečné plýtvání pamětí a vyplatí se použít například seznam sousedů.
Speciální kapitolou jsou také dynamické datové struktury, kde se grafy (ještě častěji přímo stromy) za běhu programu velmi mění a celý graf se může několikanásobně zvětšit. Pro používání takovýchto struktur je ale potřeba velmi dobře ovládat práci s pamětí (ukazatele, příkazy jako new (Pascal) či malloc (C)), což výrazně přesahuje rámec této práce.

Graf reprezentovaný maticí

Příklad popisuje graf reprezentovaný maticí sousednosti. Jde o jednoduchý neorientovaný graf bez jakékoliv metriky. Programovací jazyk (prostředí): Pascal (Turbo Pascal 7).

Program přímo žádný algoritmus nepočítá, pouze ukazuje práci s grafem (přidání hrany, odebrání...).

Ukázky programu

Práce s grafem v Pascalu
Obr. č. 2.24 - Turbo Pascal 7 (programovací prostředí)

Práce s grafem v Pascalu
Obr. č. 2.25 - Turbo Pascal 7 (běh programu)

Práce s grafem v Pascalu
Práce s grafem v Pascalu

Poznámky pro programátory

  • Pro matici je použito dvourozměrné pole (typ typ_matice).
  • Rozměry matice jsou určené konstantou velikost_matice. Takovéto využití pole o dopředu naalokované paměti brání zvětšování grafu (přidávání nových vrcholů) - oproti dynamickým datovým strukturám.
  • Matice se předává procedurám odkazem (nikoliv hodnotou) - matice je tak globální proměnnou, do které procedury zasahují a upravují ji.
  • Zaznamenání hrany i odebrání je jednoduché - pouze se změní číslo na souřadnici určené pořadovými čísly vrcholů.

Kód programu - stáhnout program (zdrojový kód, Pascal, 2 kB)

GeSHi © 2004, Nigel McNie
  1. { Jednoduchy ukazkovy program na reprezentaci grafu pomoci matice sousednosti }
  2. { Pouziva pouze 1 (je hrana), 0 neni }
  3. { Z webu http://teorie-grafu.elfineer.cz, Bc. prace z MFF UK, Lukas Jirovsky }
  4. program GRAFMATICE1;
  5.  
  6. const
  7.   velikost_matice = 10;
  8.  
  9. type
  10.   typ_matice = array[1..velikost_matice,1..velikost_matice] of integer;
  11.  
  12. var
  13.   matice1: typ_matice;
  14.  
  15. procedure vycistiMatici(var matice:typ_matice);
  16. var
  17.   i, j: integer;
  18. begin
  19.   for i:=1 to velikost_matice do
  20.     begin
  21.     for j:= 1 to velikost_matice do
  22.       begin
  23.       matice[i,j]:= 0;
  24.       end;
  25.     end;
  26. end;
  27.  
  28. procedure zadejHranu(odkud: integer; kam: integer; var matice:typ_matice);
  29. begin
  30.   matice[odkud,kam]:= 1;
  31.   matice[kam,odkud]:= 1;
  32. end;
  33.  
  34. procedure odeberHranu(odkud: integer; kam: integer; var matice:typ_matice);
  35. begin
  36.   matice[odkud,kam]:= 0;
  37.   matice[kam,odkud]:= 0;
  38. end;
  39.  
  40. function jeHrana(odkud: integer; kam: integer; var matice:typ_matice):boolean;
  41. begin
  42.   if(matice[odkud,kam] = 1) then jeHrana:=true else
  43.                                  jeHrana:=false;
  44. end;
  45.  
  46. procedure vypisMatici(var matice:typ_matice);
  47. var
  48.    i,j: integer;
  49. begin
  50.    writeln('Matice:');
  51.    for i:=1 to velikost_matice do
  52.     begin
  53.      for j:= 1 to velikost_matice do
  54.       begin
  55.       write(matice[i,j]);
  56.       end;
  57.      writeln;
  58.     end;
  59.     writeln('--->KONEC MATICE---->');
  60.     writeln;
  61. end;
  62.  
  63. begin
  64.   {samotny program}
  65.   vycistiMatici(Matice1);
  66.   vypisMatici(Matice1);
  67.  
  68.   {zadani nekolika testovacich hran}
  69.   zadejHranu(1,2,Matice1);
  70.   zadejHranu(2,3,Matice1);
  71.   zadejHranu(2,4,Matice1);
  72.  
  73.   vypisMatici(Matice1);
  74.  
  75.   readln;
  76. end.

Úvod

Základní pojmy

Vybrané problémy

Procvičování

Zdroje a literatura