NEW
Font size
WorksheetsIntroducción a los grafos
Total questions: 13
Worksheet time: 3hrs 15mins
¿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.
Un grafo se puede representar a través de una matriz o lista de adyacencia.
Verdadero
Falso
¿Qué representan los ceros en una matriz de adyacencia?
carece de relación
relaciones simples
bidireccionales
Ventaja de las listas de adyacencias:
Es más fácil ver si es bidireccional
No desperdicia espacio en la representación de relaciones.
Faltan los ceros
