Grafs ir matemātiskais objekts, kas sastav no divām kopām: tā saucamā virsotņu kopa V un loku kopa Q.
G(V,Q).
Grafs varbūt ar cilpām. Piemēram:<1;1><2;2><3;3>.
Loku sarakstu veido virsotņu pāri, kas nosaka lokus. Katras virsotnes ir divas lokālas pakāpes: ieejošie loki un izejošie loki.
Piemēram:
A - (1,3) (2,4) (2,5) , kur 1, 2 – ieejošie loki un 3, 4, 5 – izejošie loki.
AM – atslēgas sistēma (ir tik elementi , cik ir virknes).
Blakus virsotņu matrica ir kvadrātveida matrica un tas ir viens no veidiem uzdot grafu. Blakus virsotņu matricas izmērs ir n n (ir tik liels,
cik ir virsotnes). Matricas elementi ir bināri (1,0).
A(i,j) = 1, ja (i,j) pieder Q un
0, ja (i,j) nepieder Q.…