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:
    • n*(n-1)/2
  • El nombre d'arestes d'un pseudograf:
    • n*(n+1)/2
  • Lema de les encaixades:
    • La suma de tots els graus dels vèrtexs d'un graf o pseudograf és igual a dues vegades el nombre d'arestes.
  • El nombre de vèrtexs de grau senar d'un graf és parell.

Tipus especials de grafs

  • Graf nul. Nn On n es mes petit o igual a 1. Te n vèrtex i 0 arestes.
    • N4
ExempleGrafNul.png
  • Graf r-regular. Tots els vèrtex amb el mateix grau r
    • 3-regular
ExempleGraf3regular.png
  • Graf complet. Kn on n es mes gran o igual a 2. Te n vèrtexs i totes les aretes possibles.
    • K 3
ExempleGrafK3.png
  • Graf cicle. Cn on n es mes gran o igual a 3 cada vèrtex esta connectat per una aresta formant un cicle.
    • C4
ExempleGrafC4.png

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