Grafos

Question 1

¿Qué es un grafo?

Answer 1

Colección de relaciones entre cosas.

Question 2

¿Qué es el mapeo?

Answer 2

Relacionar el conjunto de nodos con si mismo, es decir, unir los nodos que tengan una relación entre si.

Question 3

¿Qué es un grafo simple?

Answer 3

Se dice un grafo es simple si para cualquier par de nodos se cumple que no están relacionados consigo mismos y tienen solo un enlace entre ellos.

Question 4

¿Qué es un grafo isomorfo?

Answer 4

Un grafo es isomorfo a otro si se puede asignar una función biyectiva que relacione a cada nodo del primer grafo con algún otro del segundo y tal que para cualquier par de nodos relacionados en el primer grafo, sus imágenes también lo estarán en el segundo.

Question 5

¿Qué beneficios tiene resolver un problema con grafos?

Answer 5

Los problemas se pueden reducir a un problema de grafos, eso es útil ya que lo reducimos a lo más esencial y puede ser más fácil de resolver.

Question 6

Describa un grafo Hamiltoneano

Answer 6

Un ciclo Hamiltoneano es un grafo que contiene un ciclo Hamiltoneano, lo que significa que existe un camino tal que se pasa por todos los nodos y se termina en el nodo en el que se empezó, pero sin pasar dos veces por el mismo nodo.

Question 7

Describa un grafo Euclidiano

Answer 7

Cuando un grafo contiene un ciclo Euleriano se le llama grafo euleriano, significa que el grafo se puede encontrar un camino tal que pase por todos los nodos sin pasar dos veces pro el mismo camino.

Question 8

¿Cuándo se admite una operación?

Answer 8

Decimos que una implementación admite una operación si y solo si la operación toma como máximo un tiempo polilogaritmico y la implementación usa cómo máximo un espacio lineal.

Question 9

¿Hay estructuras predefinidas que admitan operaciones?

Answer 9

Hay diferentes tipos de estructuras que admiten ciertas operaciones de manera que no son costosas.

Question 10

¿Qué es una estructura de prioridad?

Answer 10

Si una estructura tiene una función “Obtener” relacionada con la importancia del elemento entonces es una estructura de prioridad.

Question 11

Describa una cola fusionable

Answer 11

Si una estructura admite Crear, Insertar, Fusionar y Expandir entonces se llama colas fisionables

Question 12

Describa una partición

Answer 12

Una estructura que admita Crear, Encontrar estructura y Unión es una partición

Question 13

¿Qué significa comprimir en grafos?

Answer 13

Comprimir significa encontrar la raíz de la estructura y hacer que todos los nodos que pertenecen a ella apunten a la raíz

Question 14

¿Qué es un grafo conexo?

Answer 14

Se dice que un grafo es conexo si tomando cualesquiera 2 nodos de él, se pueden conectar siguiendo los caminos entre los mismos nodos del grafo

Question 15

¿Qué es un dígrafo?

Answer 15

Un grafo donde las conexiones entre nodos tienen una dirección, se llama dígrafo.

Question 16

Definición de grado de un nodo

Answer 16

El grado de un nodo es el número de conexiones que van hacia él.

Question 17

Definición de ciclo

Answer 17

Un ciclo es un grafo conectado en el que cada nodo tiene grado 2.

Question 18

Propiedades de los dígrafos

Answer 18

En un dígrafo un nodo puede tener más de un padre, además de que un dígrafo puede tener más de una raíz y se dice que un nodo es raíz si tiene grado 0.

Question 19

Describa la exploración a profundidad

Answer 19

Para una exploración por profunidad de un grafo lo que se hace es elegir cualquiera de los hijos del nodo que tomamos mientras no este visitado y hacer lo mismo hasta que lleguemos a una raiz o todos los hijos del nodo esten visitados, después de eso iremos al nodo más viejo que tenia otra opción para elegir y hacemos lo mismo y así hasta acabar con todos los nodos.

Question 20

Describa la exploración por anchura

Answer 20

Un grafo se explora por anchura si primero guardamos todos los hijos del nodo que elegimos, luego vamos hijo por hijo haciendo el mismo proceso hasta acabarnos los hijos del nodo, luego hacemos el mismo proceso con el primer hijo del nodo y así hasta acabarnos todos los nodos.

Question 21

¿Qué es un árbol de expansión minima?

Answer 21

El árbol de expansión mínima es un subgrafo que conecta todos los nodos sin que haya bucles, es decir, sin que partiendo de algún nodo se pueda llegar al mismo nodo sin pasar por las mismas conexiones.

Question 22

Describa el proceso para encontrar un árbol de expansión mínima

Answer 22

Para encontrar el arból de expansión minima de un grafo lo que se debe de hacer es tomar cualquier nodo como inicio y tomar el camino menos costoso hacia otro nodo, luego tomar en cuenta todas las conexiones que tienen los nodos ya recorrido e irse por el que tenga menos costo y así sucesivamente.

Question 23

Describa el algoritmo de Dijkstra

Answer 23

Se empieza por un nodo y se elige el nodo que tenga el camino con menos peso, luego del nodo que elegimos sumamos el peso que nos cuesta llegar a cada uno de sus hijos con el que nos costo llegar a él, luego se elige el camino con el menor peso acumulado y así hasta llegar al nodo final