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 dos arestes formant un cicle.
    • C4
ExempleGrafC4.png
  • Graf trajecte. Tn on n es mes gran o igual a 2 cada vèrtex està connectat per dos arestes menys l'últim i el primer que nomes en tenen una formant un trajecte
    • T3
ExempleGrafT3.png
  • Graf bipartit. Els vèrtex es poden separar en dos subconjunts en les que cada vèrtex d'un grup no esta connectat directament entre si.
  • Graf bipartit complet. Els vèrtex es poden separar en dos subconjunts en les que cada vèrtex d'un grup no esta connectat directament entre si. Te totes les arestes que complexin la norma de l'esmentat anteriorment.
ExempleGrafK33.png

Isomorfisme de grafs

  • Dos grafs són isomorfs si canviant els noms d'un dels grafs els dos es poden representar de la mateixa manera tenint els mateixos vertex i arestes

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