Anar al contingut

Grafo (tipo de senya abstracta)

De L'Enciclopèdia, la wikipedia en valencià
Grafo (tipo de senya abstracta)
Un grafo de 6 vèrtiços i 7 arestes.

Un grafo en l'àmbit de les ciències de la computació és un tipo abstracte de senyes (TAD), que consistix en un conjunt de nodos (també cridats vèrtiços) i un conjunt d'arcs (arestes) que establixen relacions entre els nodos. El concepte de grafo TAD descendix directament del concepte matemàtic de grafo.

Formalment, un grafo es definix com G=(V,A), sent V un conjunt els elements del qual són els vèrtiços del grafo i A un conjunt els elements del qual són les arestes, les quals són parells (ordenats si el grafo és dirigit) d'elements en V.

Formes de representació

Existixen diferents implementacions del tipo grafo: en una matriu de adyacencies (forma acotada) i en llistes i multilistas de adyacencia (no acotades).

  • Matriu de adjacències: s'associa cada fila i cada columna a cada nodo del grafo, sent els elements de la matriu la relació entre els mateixos, prenent els valors d'1 si existix l'aresta i 0 en cas contrari.

  • Llista de adjacències: s'associa a cada nodo del grafo una llista que continga tots aquells nodos que siguen adjacents a ell.

Especificació dels tipos abstractes de senyes d'un grafo no dirigit

Generadors

Crear un grafo buit: Torna un grafo buit.

  • op crearGrafo : -> Grafo [ctor] .

Afegir una aresta: Donat un grafo, afig una relació entre dos nodos de dit grafo.

  • op añadirArista : Grafo Nodo Nodo -> [Grafo] [ctor] .

Afegir un nodo: Donat un grafo, inclou un nodo en ell, en cas en el que no existixca prèviament.

  • op añadirNodo : Grafo Nodo -> Grafo [ctor] .

Constructors

Borrar nodo: Torna un grafo sense un nodo i les arestes relacionades en ell. Si dit nodo no existix es torna el grafo inicial.

  • op borrarNodo : Grafo Nodo -> Grafo .

Borrar aresta: Torna un grafo sense l'aresta indicada. En cas que l'aresta no existixca torna el grafo inicial.

  • op borrarArista : Grafo Nodo Nodo -> Grafo .

Selectores

Grafo Buit: Comprova si un grafo no té cap nodo.

  • op esVacio : Grafo -> Bool .

Contindre Nodo: Comprova si un nodo pertany a un grafo.

  • op conté : Grafo Nodo -> Bool .

Adjacents: Comprova si dos nodos tenen una aresta que els relacione.

  • op adjacents : Grafo Nodo Nodo -> Bool .

Per a l'especificació d'un grafo dirigit tenim que modificar algunes de les equacions de les operacions borrarArista i añadirArista per a que no es considere el cas d'arestes bidireccionals.

I substituir l'operació adjacents per:

  • op predecessor : Grafo Nodo Nodo -> Bool .
  • op successor : Grafo Nodo Nodo -> Bool .