Guia N1

Desarrollo guía N1 grafos. 1. Definir Grafo Estructuras de datos más generales que los árboles; un grafo es una colección de vértices o nodos y las conexiones entre ellos, en donde Un grafo G = (V;E) esta formado por un conjunto finito y no vacio V y por un conjunto E de pares no ordenados de elementos distintos de V . Elementos de V : vértices (o nodos). Elementos de E: aristas. Si e = fu; vg (e = uv) es una arista, entonces u y v son adyacentes (u _ v); e es incidente con los vértices u y v.

2. Nombrar cinco aplicaciones que se puedan realizar con grafos -

circuitos lógicos Mapas de rutas Modelar diversas situaciones de la vida diaria o cualquiera en especifico

-

Sistemas de aeropuertos

-

Flujos de trafico

-

Planificación de actividades

-

Redes

-

Representar circuitos eléctricos

-

Circuitos de aguas

3. Realizar consulta sobre Leonard Euler, e indicar y su aporte a la teoría de grafos Euler resolvió el problema conocido como el problema de los puentes de Königsberg, en donde se llega a la conclusión que esta solución representa el primer teorema de teoría de grafos la cual dio origen a la teoría de los grafos. 4. Explicar y representar gráficamente el problema de los siete puentes.

El problema consistía en decidir si era posible seguir un camino que cruzase todos los puentes una sola vez y que finalizase llegando al punto de partida. No lo hay, y Euler logró probarlo matemáticamente demostrando que no existía un ciclo euleriano debido a que el número de puentes en más de dos bloques era impar.

5. Describir el problema de los cuatro colores Fue en 1879 que a un inglés se le ocurrió esta novedosa idea, planteaba que "bastan tan solo 4 colores para iluminar cualquier mapa de manera que no haya dos países vecinos del mismo color". El ingenioso personaje este se llamaba Alfred Kempe, y publicó su demostración en la revista Nature e ingresó a la "Royal Society", pero pocos años más tarde se le descubrieron errores. Casi 100 años mas tarde, en 1976, dos norteamericanos lo demostraron usando una supercomputadora, esta analizó todos los tipos de mapas durante 1,200 horas (es como empezar a descargar un archivo y volver 50 días después).

Muchas personas argumentaron que no era una demostración válida, y no fue hasta 1996 que otros norteamericanos publicaron una demostración definitiva y que hasta ahora nadie ha refutado. 6. Leer las diapositivas curso estructura de datos Nivel 17 proyecto cupi2 http://cupi2.uniandes.edu.co/cursos/datos/docs/presentaciones/N17C1.pdf 7. Realizar un glosario con las definiciones de las diapositivas.

Árboles: un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Vértices: elementos del conjunto. Sucesor: cuando un vértice que esta unido como un arco tiene como origen otro vértice. Predecesor: aquel vértice que se encuentra ubicado como origen de otro que atraviesa un arco. Identiicador: se distingue como único elemento de identificación para los vértices. Información: es aquella que esta asociada con el elemento. Orden: en un grafo el numero de elementos Grafo vacío: grafo de orden cero Fuente: vértice que no tiene predecesores Sumidero: vértice que no tiene sucesores Camino: secuencia de vértices 8. Definir y representar gráficamente Grafo Un grafo es una colección de vértices o nodos y las conexiones entre ellos.

Nodo Un nodo es un punto de intersección o unión de varios elementos que confluyen en el mismo lugar

El grafo mostrado en la imagen, los nodos son identificados ya que estos están identificados con una letra.

Arco Es el enlace que se encuentra entre los nodos.

Grafo dirigido Es un grafo, el cual se identifica por no tener bucles. Un grafo dirigido es aquel en el cual sus nodos poseen un atributo el cual sirve como apuntador; “Los grafos son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas líneas. Si estas líneas son flechas, hablaremos de grafo dirigido”.

Grafo dirigido

Adyacencia Se evalúa más que todo a una matriz de adyacencia en la cual se efectúan operaciones binarias.

Incidencia Matriz de incidencia

Es una matriz binaria (sus elementos sólo pueden ser unos o ceros), que se utiliza como una forma de representar relaciones binarias.

Grafos y dígrafos fuertemente conectados Son aquellos grafos en los cuales hay varios caminos u arcos para recorrer entre los vértices.

Grafos y dígrafos débilmente conectados Son aquellos grafos en los cuales hay simples caminos.

Camino simple Todos los vértices por los cuales pasa son diferentes entre sí y diferentes del origen y del destino.

Grafo regular Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Grafo Planar Aquel grafo en el cual no se cruzan los arcos.

Grafo Euleriano Definimos un grafo euleriano G como un grafo conexo que posee un camino cerrado que incluye todas las aristas de G, a la que llamaremos camino euleriano. Cada arista se recorre una vez y sólo una vez. Definimos que G es semi-euleriano si levantamos la restricción de que el camino euleriano deba ser cerrado.

Grafo Hamiltoniano En la sección anterior se examinaba la posibilidad de crear un camino cerrada que incluyese todas las aristas de un grafo conexo G. Un problema similar es el de si existe un camino cerrado que pasa exactamente una vez a través de cada vértice de G. Si este existe se dice que G es un grafo hamiltoniano. A continuación se muestra el grafo hamiltoniano dodecaedrico.

Grado de un vértice El grado de un vértice en un grafo es el número de caminos que inciden en el vértice— en otras palabras, el número de líneas que pasan por un nudo del grafo. Su utilidad define si una trayectoria por el grafo es o no un camino euleriano.

Diagrama de un grafo con 6 vértices y 7 aristas. Por ejemplo el vértice 1 tiene grado 2, el vértice 5 tiene grado 3.

Arco cíclico Un arco es cíclico si parte de un vértice y llega al mismo vértice.

Grafos simples Un grafo es simple, si no tiene arcos cíclicos y existe un solo arco entre dos vértices.

Grafos completos Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértices que componen el grafo. Por ejemplo los siguientes grafos son completos: