Grafs

Vikipēdijas raksts

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

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:

  1. neviena no kopām E(x; y) nešķeļas ar V,
  2. dažādiem pāriem (x; y); (x1; y1) piekārtotas kopas var škelties 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 škautnes.

[izmainīt šo sadaļu] Grafu attēlošana

Grafu var uzdot ar incidences matricu, incidences sarakstu, ...

[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).