Nivel Principiantes
Que es un grafo
Un Grafo G consiste en dos conjuntos finitos. Un conjunto V llamado Vértices o Nodos y de otro conjunto E llamado aristas o lados
Que tipos de grafos existen
Simples, completos, conexos, bipartita
Que es un grafo simple
Un Grafo Simple es un grafo que no tiene ciclos ni lados paralelos. Es decir 1 arista une dos vértices cualesquiera
Que es un grafo completo
Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une
Que es un grafo conexo
Un grafo es conexo si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b
Un Grafo bipartita en (n,m) vértices es un grafo simple con vértices v1, v2, . . . ,vn, w1, w2, . . . ,wm tal que los únicos lados son los lados que conectan todos los vértices vi con todos los vértices wj : Kn,m
Como calculamos el grado de un grafo y de sus vértices
Sea G un grafo y V un vértice de G. El grado de V es el número de aristas que indicen en V (Los ciclos cuentan doble). Se simboliza por deg (V). El grado total de G es la suma de los grados de todos los vértices de G.
Que es un camino
Secuencia de vértices <v1, v2,…., vn> tal que (vi, vi+1) son adyacentes.
Que es un Camino simple
Todos los vértices son distintos
Que es un camino compuesto
Es el camino que permite repetir vértices
Cual es la longitud de un camino
Es el número de aristas del camino
Que es un Ciclo
Es un camino simple que tiene el mismo vértice inicial y final
Cuando esta etiquetado un grafo
Un grafo está etiquetado si asociamos a cada arista un peso o valor
Que es la ruta de un grafo
Trayectoria determinada que va de un sitio a otro definiendo un camino.
¿Qué es un circuito o ciclo de un grafo?
Un circuito o un ciclo en un grafo consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino
¿Cómo identificamos si los siguientes grafos son Isomorfos?
Dos grafos son isomorfos si:
Tienen la misma cantidad de aristas y vértices
El grado de los vértices en ambos grafos es el mismo
Poseen la misma matriz de adyacencia de vértices
¿Que es la matriz de adyacencia?
Representa una lista de adyacencia de vértices V: secuencia de vértices adyacentes a V
¿Que es un circuito euleriano?
Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez y para comprobarlo existe un Teorema:
Teorema
Sea G un grafo. G contiene un circuito euleriano sí y sólo sí:
G es conexo.
Cada vértice de G es de grado par.
¿Que es un circuito Hamiltoniano?
Un ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G, su trayectoria empieza y termina en el mismo vértice y pasa por cada vértice una sola vez
¿Cuales son las operaciones que se pueden realizar en una tabla de Hash?
Inserción (llave, valor)
Búsqueda (llave) que devuelve el valor o viceversa
Borrar
¿Que es una tabla de hash?
Una tabla hash es una estructura de datos que pretende la inserción, búsqueda y borrado de elementos en tiempo constante.
¿Cuando se produce una colisión en una tabla Hash?
Una colisión se produce cuando objetos diferentes dan lugar al mismo índice hash
¿Cuales son las formas de resolver colisiones?
Resolución mediante exploración
Exploración lineal
Exploración cuadrática
encadenamiento enlazado
¿En que consiste la Exploración cuadrática en las tablas de Hash?
Visita la casilla i² posiciones más allá de la que causó la i-esima colisión. Si esta libre, inserta. Si no, repite el proceso hasta encontrar una libre.
¿En que consiste el encadenamiento enlazado en las tablas de Hash?
En cada posición de la tabla se mantiene una lista enlazada en la que se van insertando los elementos cuyo valor hash les asigna la misma posición.