Grafs

Šis raksts ir par matemātikas un datorzinātnes jēdzienu. Par citām jēdzienagrafsnozīmēm skatītnozīmju atdalīšanas lapu.

Grafa ar 6 virsotnēm un 7 šķautnēm vizuāls attēlojums

Grafsmatemātikāir punktu (kurus sauc parvirsotnēm) kopa kopā aršķautnēm,kas tos savieno.Datorzinātnēgrafs ir nelineāradatu 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ētagrafu teorija.

Matemātiskais apraksts

Par grafu sauc sistēmu (V;E), kurVir netukša kopa, betE- divu argumentu funkcija kopāV.Ekatram pārim (x; y) no VxV piekārto kādu kopu E(x; y) tā, ka:

1. neviena no kopām E(x; y) nešķeļas arV,
2. dažādiem pāriem (x; y); (x₁;y₁) piekārtotas kopas var šķelties vienīgi tad,

ja šie pāri ir viens otram apgriezti: (x; y) = (y₁;x₁).

KopasVelementi ir grafavirsotnes,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ēlotplaknē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.
• GraphArhivēts2010. gada 20. jūnijā,Wayback Machinevietnē., PlanetMath.
• Paulis Ķikusts,Grafu teorija.
• Jānis Dambītis,Modernā grafu teorija.
• Jānis Cīrulis,Grafu teorija.
• Grafu teorija^{[novecojusi saite]},lekciju materiāli LU kursam DatZ5031 (lai piekļūtu, jāklikšķina uz "Login as a guest" ).
• Pēteris Daugulis,Grafu teorija^{[novecojusi saite]}.