Grafs

Grafs matemātikā ir punktu (kurus sauc par virsotnēm) kopa kopā ar šķautnēm, kas tos savieno. Datorzinātnē grafs ir nelineāra datu struktūra. Tādējādi grafs ir svarīgs diskrētās matemātikas un datorzinātnes jēdziens. Grafus un to īpašības pēta grafu teorija.

 Matemātiskais apraksts 
Par grafu sauc sistēmu (V; E), kur V ir netukša kopa, bet E - divu argumentu funkcija kopā V. E katram pārim
(x; y) no VxV piekārto kādu kopu E(x; y) tā, ka:
 neviena no kopām E(x; y) nešķeļas ar V,
 dažādiem pāriem (x; y); (x1; y1) piekārtotas kopas var šķelties vienīgi tad,
ja šie pāri ir viens otram apgriezti: (x; y) = (y1; x1).

Kopas V elementi ir grafa virsotnes, kopā (x; y) atrodas šķautnes.

 Grafu uzdošana 
Grafu var uzdot ar incidences matricu, incidences sarakstu vai arī kā zīmējumu.

 Grafu veidi 
Matemātikā, grafu teorijā un citur ir svarīgi šādi grafu veidi:
 Sakarīgs grafs. Tas ir tāds grafs, kuram no jebkuras virsotnes var aiziet uz jebkuru citu virsotni, pārvietojoties tikai pa grafa šķautnēm.
 Planārs grafs. Tas ir grafs, ko iespējams attēlot plaknē tā, ka tā šķautnes nekrustojas.
 Orientēts grafs. Tas ir grafs, kura katrai šķautnei ir piekārtots virziens.
 Multigrafs. Tas ir grafs, kuram ir divas virsotnes, kas savienotas ar vairāk nekā vienu šķautni.

 Algoritmi darbam ar grafiem 
Pazīstami vairāki grafa apstaigāšanas algoritmi:
apstaigāšana dziļumā (DFS), apstaigāšana plašumā (BFS).

 Skatīt arī 
 Bellmana-Forda algoritms

 Ārējās saites 
 Eric W. Weisstein, Graph, MathWorld.
 Graph , PlanetMath.
 Paulis Ķikusts, Grafu teorija .
 Jānis Dambītis, Modernā grafu teorija .
 Jānis Cīrulis, Grafu teorija .
 Grafu teorija, lekciju materiāli LU kursam DatZ5031 (lai piekļūtu, jāklikšķina uz "Login as a guest").
 Pēteris Daugulis, Grafu teorija.

Kategorija:Datu struktūras
Kategorija:Diskrētā matemātika
Kategorija:Matemātika
Kategorija:Grafu teorija