Grafs
Vikipēdijas raksts
- Šis raksts ir par matemātikas terminu. Lai lasītu informāciju par latviešu basketbolistu, skat. rakstu Raitis Grafs.
Grafs — viens no grafu teorijas pamatjēdzieniem. Grafs ir nelineāra datu struktūra.
[izmainīt šo sadaļu] Matemātiskais modelis
Par grafu sauc matemātisku sistēmu (V; E), kur V ir netukša kopa, bet E - 2 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.
[izmainīt šo sadaļu] Grafu uzdošana
Grafu var uzdot ar incidences matricu, incidences sarakstu vai arī kā zīmējumu.
[izmainīt šo sadaļu] Algoritmi darbam ar grafiem
Pazīstami vairāki grafa apstaigāšanas algoritmi: apstaigāšana dziļumā (DFS), apstaigāšana plašumā (BFS).
