Teoria de Grafos I

Standard

Hola a todos espero y tengan un buen día, el día de hoy en esta primera parte de este blog vamos a empaparnos un poco acerca de a teoría grafos, espero y les sea útil, bien pues comencemos.

¿Que es un grafo?

Pues un grafo es una colección finita de vértices o nodos(nodes) y aristas (edges).Seguramente se preguntaran, ¿lo usamos en nuestra vida diaria?. Vamos a poner un ejemplo: Facebook. La inmensa red social que seguramente usamos casi a diario, es considerada un grafo social (social graph). En este grafo, cada persona es considerada un nodo del grafo y cada arista es la encargada de relacionar a dos personas. En facebook un amigo tuyo es una relación bi-direccional. Ejemplo A es amigo de B => B es amigo de A, entonces estamos hablando de un grafo no­-dirigido.

Cada arista de un grafo es representado como un par ordenado (u,v) donde (u,v) indica que existe una arista del vértice u al vértice v. Las aristas es posible que contengan un costo(cost), un peso (weight) o longitud (length). La valencia de un vértice es es el numero de aristas que conectan a este mismo.

Existen dos tipos de grafos:

No­Dirigido: Un grafo no-­dirigido es un aquel en el cual todas las aristas son bi­direccionales, esencialmente la arista no apunta a ninguna dirección.

NODIRIGIDO

Dirigido: Un grafo dirigido es un tipo de grafo el cual las aristas son unidireccionales.

DIRIGOS

Un grafo ponderado es un grafo al cual a las aristas se les asigna un peso o costo. Considere un grafo como el mostrado en el siguiente diagrama. Como pueden ver cada arista tiene un peso asignado. Supongamos que queremos ir del vértice 1 al 3. Existen tres caminos:

1­ => 2 =­> 3

1­ => 3

1­ => 4 =­> 3

El costo total de 1­ => 2 =­> 3 seria (1+2) = 3 unidades.

El costo total de 1­ => 3 seriia 1 unidad

El costo total de 1­ => 4­ => 3 seria (4+3) = 7 unidades.

GRAFOPONDERADO

Bueno en esta primera parte seria todo, el continuación de este blog les mostraré las formas en que se pueden representar este tipo de grafos, espero y tengan un excelente día y hasta la próxima.

Leave a Reply

Your email address will not be published. Required fields are marked *