Introducció als grafs

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}}

• 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. N_n On n es mes petit o igual a 1. Te n vèrtex i 0 arestes.
  • N₄

• Graf r-regular. Tots els vèrtex amb el mateix grau r
  • 3-regular

• Graf complet. K_n on n es mes gran o igual a 2. Te n vèrtexs i totes les aretes possibles.
  • K ₃