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.