Introducción a los grafos

¿Qué es un grafo?

• Estructura dinámica lineal que relaciona información.

• Estructura dinámica no lineal que permite modelar relaciones entre objetos.

• TDA dinámica que relaciona información de forma jerarquica.

Partes de un grafo

• Nodos, ramas, peso

• Vértices, lineas

• Vértices, aristas, peso

Un grafo se representa por:

• G=(V,A) V=Vértices A=Aristas

• G=(1,2,3,4)

• (a,b) (b,c) (c,b)

Ejemplos de grafos:

• red de transporte, red de carreteras, intranet, internet, sistema de navegabilidad....

• árbol genealógico, circuitos eléctricos, matrimonio, estados de ánimo...

• decisiones, teléfonos, red de agua potable, enfermedades...

¿Qué es un digrafo?

• Un grafo que tiene definido el origen y destino de cada una de las relaciones.

• Un grafo que no tiene dirección

• Un grafo con 2 vértices

Identifica el siguiente grafo:

• V = {C, D, E, F, H}, A = {(C, D,), (D, F), (E, H), (H, E), (E, C), (C,E)}

• V = {C, D, E, F, H}, A = {(C, D,), (D, F), (E, H), (H, E), (E, C)}

• V ={C, D, E, F, H} A = {(C, D,), (D, F), (E, H), (H, E), (E, C), (F,D}

Magnitud especifica de la relación entre vértices:

• nodo

• peso

• vértice

Un grafo que contiene pesos en sus aristas se denomina:

• dirigido

• convexo

• ponderado

Empieza y termina en el mismo nodo, debe tener más de un arco.

• vuelta

• bidireccional

• ciclo

¿Qué es un grafo conexo?

• Un grafo no dirigido donde existe un camino entre cualquier par de nodos.

• Un grafo donde existe al menos un par de nodos sin relación con los demás.

• Grafo que tiene un arco para cualquier par de vértice.