GRAFOS
Conceptos matemáticos :
Grafo. Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. 

• Los grafos son estructuras de datos
• Representan relaciones entre objetos
• Relaciones arbitrarias, es decir
• No jerárquicas
• Son aplicables en
• Química
• Geografía
• Ing. Eléctrica e Industrial, etc.
• Modelado de Redes
• Eléctricas
• Etc.

 












DEFINICION

Un grafo G = (V,A)

V, el conjunto de vértices o nodos

Representan los objetos

A, el conjunto de arcos

Representan las relacione

 

 

Terminología:

Etiquetado. Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto, es decir, asignarle a cada vértice o arista un nombre.

Adyacencia. Se dice que dos vértices son adyacentes si hay una arista que los conecte entre ellos. 

Grado de un vértice. El grado de un vértice es un número natural de 0 al infinito que designa el número de aristas le conectan con otros vértices.

  

Incidencia. Una arista es incidente a un vértice si ésta lo une a otro. 

Ponderación. Corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. 

Camino. Un camino es una secuencia de aristas que comienzan en un vértice del grafo y recorren parte o la totalidad del grafo conectando vértices adyacentes.

Circuito. Cuando existe un camino que empieza y acaba en el mismo vértice.

Isomorfismo. Si dos grafos son isomorfos sólo varía la apariencia, es decir, que se mantienen las adyacencias, estructura, caminos, ciclos, número de vértices y número de aristas.

Conexo. Un grafo es conexo si tiene una única componente conexa, es decir, todos los vértices del grafo están relacionados. 

Familias de grafos simples:

Grafo regular: 

  

Grafo bipartito: 

Grafo bipartito completo: 

TIPOS DE GRAFOS

 

Grafos no dirigidos

Si los pares de nodos de los arcos

No son ordenados Ej.: u-v

 OTROS CONCEPTOS

Arista

Es un arco de un grafo no dirigido

Vertices adyacente

Vertices unidos por un arco

Factor de Peso

Valor que se puede asociar con un arco

Depende de lo que el grafo represente

Si los arcos de un grafo tienen F.P.

Grafo valorado