Juego Fabi Flashcards
¿Que es un grafo?
es una estructura de datos no lineal usada en Computacion y Matemáticas
El grafo también es conocido como
multigrafo
Muchos problemas pueden ser expresados de forma de
grafos
¿Como pueden ser resueltos los grafos?
usando algoritmos de busqueda y manipulacion correspondientes
¿Cuales son las aplicaciones de los grafos?
Realizar planificaciones de actividades, tareas del computador, planificar operaciones en lenguaje de maquinas para minimizar el tiempo de ejecucion
¿Como puede ser visto un grafo?
como un conjunto de vertices y arcos que conectan a esos vértices
sinónimos de vertices
nodos
¿Cual es la formula de los grafos?
G = (V,E)
Si u y v son elementos de V entonces un arco se puede
representar por (u,v)
Cuál es la clasificacion de los grafos?
No dirigido y dirigidos
¿Con que otro nombre se le conoce a los grafos dirigidos?
Digrafos
¿Qué es un grafo no dirigido?
Los arcos no tienen una direccion y por lo tanto, (u,v) y (v,u) representan el mismo arco
¿Qué es un grafo dirigido?
Los arcos tienen una direccion definida asi (u,v) y (v,u) representan arcos diferentes
¿Que significa E?
conjunto de aristas que representan una relacion binaria
¿Como se representa una relacion binaria?
E: V -> V
¿Qué significa cuando es incidente dirigido?
cuando sale del vértice u y es incidente a o entra al vertice v
Dos vértices se dicen adyacentes porque
existe un arco que une a esos dos vértices
Si el grafo es no dirigido, entonces como es la relacion de adyacencia
simétrica
¿Qué es un camino?
una secuencia de vértices
¿Con que otro nombre se le conoce al camino?
ruta
¿Qué es la longitud de un camino?
la cantidad de aarcos que éste contiene
¿Qué es un camino simple?
es aquel donde todos sus vertices son distintos. Solo el primero y el último pueden coincidir (cliclo)
¿Qué es un ciclo en un grafo dirigido?
es el camino de longitud mayor o igual a 1 donde u1 = un
¿Que es un ciclo?
un camino simplre y cerrado
¿Como se le llama a una arista a = uu
bucle
¿Como se le llama a una arista que aparece repetida en E?
arista múltiple
¿Por qué un grafo es conexo?
porque desde cualquier vértice existen un camino hasta cualquier otro vértice del grafo
que es un grafo no conexo?
cuando no hay un camino de un vértice a otro
por que se dice que un grafo es fuertemente conexo?
si para todo par de vertices u y v existe un camino dirigido que va de u a v
por que se dice que un grafo es completo?
porque es un grafo simple en el que todo par de vértices está unido por una arista
como se representa al grafo completo?
Kn donde n es el número de vértices
Que es un grafo ponderado?
grafo en el que las aristas se les asigna un numero especifico
¿Como se le llama al numero especifico?
coste
como se le conoce tambien al grafo ponderado?
grafo etiquetado
que es un vértice aislado
cuando no tiene otros vertices adyacentes
cuando se dice que dos grafos son isomorfos?
cuando tienen una biyeccion que conserva la adyacencia
¿Que es un grado de un vértice?
el numero de aristas que lo tienen como extremo
Cuantas formas existen de mantener un grafo G en la memoria de una computadora?
2
¿Cuales son las dos maneras de mantener un grafo G en la memoria de una computadoras?
representacion secuencial de G y representacion enlazada de G
que es la representacion secuencial de G
se basa en la matriz de adyacencia
que es la representacion enlazada de G
se basa en listas enlazadas de vecinos
cual es la definicion formal de un grafo?
un conjunto de nodos y un conjunto de aristas
que regla sigue la matriz de adyacencia?
ma [i,j] = -1, si i es adyacente a j, 1 si i es el detino de la adyacencia con j, y 0 en caso contrario
Que es necesario para que sea posible remodelar un grafo en tiempo de ejecucion?
la utilizacion dinamica de su representacion
con que se hace la representacion de adyacencias entre vertices
listas lineales
cual es la forma de representacion mas flexible para la representacion de grafos?
la lista de adyacencia
