WorksheetsGrafos
Total questions: 20
Worksheet time: 10mins
¿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:
Ninguno de los anteriores
V = {C, D, E, F, H}, A = {(C, D,), (D, F), (E, H), (H, E), (E, C)}
V ={1,4,5,7,9} A = {(1,4), (4,1), (5,1), (1, 5), (7,9), (9,7), (7,5), (5,7), (4,9),(9,4)}
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
La codificación de un vertice contiene los siguientes elementos:
Int Dato, Vertice *Sig, Arista *Adyacencia
Char Dato, int Peso, Vertice *Sig
Char Peso, Arista *Sig, Vertice Dato
¿Qué clase tiene los siguientes atributos?
int peso;
Arista *siguiente;
Vertice *adyacente;
Vertice
Arista
Grafo
¿Qué clase tiene los siguientes métodos?
Vertice(char);
~Vertice();
friend class Grafo;
friend class Arista;
Arista
Nodos
Vertice
A qué clase pertenecen los siguientes atributos:
Vertice *inicio;
Vertice *fin;
Grafo
Vertice
Arista
¿Qué significa el siguiente código?
origen->adyacente=nueva;
nueva->adyacente=destino;
Creación de la primer arista
Creación y enlazado de aristas
Creación de vertices
¿Qué parámetros necesita la función de insertar_aristas?
Char Dato, int peso, int *Vertice
Char Dato
Vertice *origen, Vertice *destino, int peso
¿Qué significa el siguiente código?
if(inicio==NULL)
{
return true;
}
else
{
return false;
}
grafo vacío
No hay vértices
No hay aristas
