Introducció als grafs

De FFAWiki

Grafs

Definicions

  • Un Graf G(V,A) esta format per vèrtexs (V) i les connexions entre vèrtexs, les arestes (A).
  • V = {1, 2, 3, 4, 5}
  • A = {{1, 2}, {5, 1}, {5, 4}, {4, 2}, {3, 4}, {3, 5}, {2, 3}}
ExempleGraf.png
  • Un graf com a tal no te multiplicitat d'arestes ni vèrtexs que connecten amb si mateix.
  • Els graf amb multiplicitat d'arestes s'anomenen Multigrafs.
  • Les arestes que connecten un vèrtex amb si mateix s'anomenen llaços i el graf passa a anomenar-se pseudograf.

Propietats

  • El nombre d'arestes d'un graf:
  • <nowiki>n*(n-1)/2<nowiki>

Tipus especials de grafs

Isomorfisme de grafs

Operacions amb grafs

La seqüència de graus d’un graf

Variants de grafs

Grafs dirigits

Multigrafs

Grafs ponderats

Connexió i components

Connexió en el cas de grafs

Connexió en el cas de digrafs

Grafs plans

Propietats

Coloració d'un graf

Propietats

Emmagatzematge d'un graf en memòria

Matriu d'adjacència

Llistes d'adjacència