TEORIA DE GRAFOS

Vista previa del material en texto

Grafos
Aplicar los conceptos básicos de grafos para resolver problemas afines al área computacional relacionados con el recorrido, búsqueda y ordenamiento en grafos, árboles y redes.
¿De dónde surge?
Euler y los puentes de Königsberg (antes Prusia Oriental, actualmente se llama Kaliningrado y pertenece a Rusia)
¿Cómo cruzar a pie toda la ciudad, pasando sólo una vez por cada uno de los puentes, y regresando al mismo punto de inicio?
Diagnóstico
Objetivo: identificar qué conocimientos posee el estudiante al iniciar el tema del parcial: grafos.
Indicaciones: coloque V si es Falso o F si es verdadero en cada una de las afirmaciones.
Niveles:
Todos los aciertos.
Entre 8 y 9 aciertos.
Máximo 7 aciertos.
Menos de 7 aciertos.
Todos los aciertos.
Entre 8 y 9 aciertos.
Máximo 7 aciertos.
Menos de 7 aciertos.
Uno de los elementos que forman un grafo se llama ARISTA y es representado por líneas o flechas. __________________
Existen diversos tipos de grafos, por ejemplo: SIMPLES, COMPLETOS, CONEXOS._____________________
Un recorrido es cuando se atraviesa por todos los nodos o vértices del grafo, desde un punto de partida hasta un destino. _____________________
Un camino es ir de un punto de partida hacia uno de destino pero NO necesariamente debe pasar por todos los puntos del grafo. ________________
Un camino simple es aquel por el que se atraviesa de un destino hacia el de partida sin repetir puntos del grafo. ______________
Un árbol es un grafo simple donde existe un solo camino entre un par de vértices. _________________
Los componentes del árbol son: hoja, raíz, padre, hijo, descendientes y ancestros. ______________
Existen árboles con peso y son los que tienen valores en las aristas. ________________
Existen tres recorridos en el árbol: inorden, postorden y preorden _____________
Un ejemplo de grafo puede ser las rutas del camión que va desde el centro de Mérida hasta el paradero de autobuses de Progreso. _____________________
Elementos y características.
Un grafo…
Tiene elementos:
Aristas.- líneas o flechas que unen dos vértices o puntos.
Vértices.- nodos que contienen Información.
Caminos.- conjunto de vértices por las que se pasa para llegar al destino.
Camino simple.- es el conjunto de vértices por los que pasa sin repetirlos.
5
Representación gráfica de circuitos, redes, etc.
Consta de:
Vértices
Aristas
Caminos
Es denominado
Camino simple.
Ciclo
Árbol
Aristas
Vértices
Caminos
Camino simple
Tipos de grafos.
6
Conexo
Todos los vértices se encuentran unidos por aristas
Árbol
Cuando no tiene ciclos.
Completo
Cada par de vértices está unido por una arista.
Ponderado
Cuando las aristas tienen valores.
Planos
Cuando las aristas no se cruzan entre ellas y todos los vértices están conectados.
No dirigido
Sus vértices se unen por líneas.
Dirigido
Sus vértices se unen por flechas.
Tipos de grafos
Etiquetado.
Cuando todos los vértices tienen valor.
Regulares.
Cuando de cada vértice del grafo sale un número igual de aristas.
El número de aristas es el grado del grafo.
Bipartidos
Es cuando el grafo puede particionarse en dos conjuntos de vértices unidos por aristas.
Multígrafo. 
Cuando existe más de un arco conectado al mismo par de nodos.
Simple. 
Cuando cada arco conecta a dos nodos diferentes, no existen arcos que conecten al mismo par de nodos y son aristas no dirigidas.
Algunos otros conceptos.
Ruta o Recorrido: sucesión de aristas dirigidas consecutivas.
Ruta Cerrada [circuito]: nodo inicial = nodo final.
Camino: cuando NO se repite ninguna arista ni vértices.
Camino Simple: NO se repite ningún nodo (salvo cuando es un camino (ruta) cerrada, donde nodo inicial = nodo final).
Camino Hamiltoneano: recorre cada vértice exactamente una vez.
Camino Eulenario: recorre cada arista exactamente una vez.
EJERCICIOS DE TIPOS DE GRAFOS.
Identificar los tipos de grafos de acuerdo a sus características visuales.
Ejercicios: tipos de grafos
Objetivo: Identificar los tipos de grafos de acuerdo a sus características visuales.
Indicaciones: en equipos de máximo 3 personas, observen con atención cada uno de los grafos e identifiquen de qué tipo es. Explique las razones de su respuesta.
Se unió la act 0 con la 1
24 nov 2016
10
Ejercicios: tipos de grafos
a)
b)
c)
d)
e)
f)
24 nov 2016
11
Instrumento de evaluación
	ASPECTOS	EXCELENTE
[16 – 20%]	BIEN
[11– 15%]	SUFICIENTE
[6 – 10%]	DEFICIENTE
[0 – 5%]
	TIPO DE GRAFO	Logró identificar cada uno de los grafos de manera correcta, recurriendo únicamente a sus conocimientos.	Logro identificar todos los grafos de manera correcta pero con cierto apoyo en dudas más no en identificación de los tipos.	Logró identificar máximo 4 grafos pero con cierto apoyo docente o de compañeros pues no demuestra dominio en el tema.	Lograron identificar como máximo dos grafos pero con mucho apoyo docente y de otros compañeros. Requieren de más ejercicios.
	ARGUMENTOS	Explicaron con palabras sencillas las razones de cada uno de los tipos de grafos, demostrando el dominio del tema y su comprensión.	Explicaron cada uno de los tipos de grafos con alginas palabras técnicas sin conocer la profundidad de o que colocaron.	Explicaron máximo 4 tipos de grafos pero recurrieron no solo a poyo de compañeros sino de otros medios para resolver este punto.	Lograron identificar como máximo dos grafos pero con mucho apoyo docente y/o de compañeros de otros equipos y de internet. Necesitan comprender el tema.
	LIMPIEZA	La tarea está perfectamente limpia, clara y en perfecto estado. No hay tachones de ningún tipo.	La tarea está limpia y clara pero posee algunos detalles en su cuanto a: tarea arrugada, impresión mal hecha, etc.	Entregaron la tarea con cierta claridad y limpieza. Muchos detalles en cuanto a hoja en buen estado, ejercicios claros con distinción en color, etc.	Entregaron la tarea pero no cuidaron para nada la limpieza.
	ORTOGRAFÍA	Todos sus argumentos y en general todo su ejercicio está hecho con correcta ortografía.	Todos sus argumentos son los que poseen correcta ortografía.	Se detectaron como máximo 3 faltas de ortografía en todo ejercicio.	No cuidaron la ortografía teniendo un mínimo de 5 fallas en todo el ejercicio.
	ENTREGA	Entregaron el día y en el tipo de entrega acordada, sin contratiempos	Entregaron el día y en el tipo de entrega acordada, con algunos detalles al momento de la entrega.	Entregaron horas después de lo acordado y/o fue el tipo de formato el que no respetaron.	No respetaron nada de lo acordado.
Camino -- Ciclo
Un camino es aquel que se recorre de un punto a otro que es diferente. Por ejemplo: cuando vas de tu casa a la escuela.
Un ciclo es aquel camino que se recorre donde el punto de partida es el mismo punto de llegada. Por ejemplo: cuando sales de tu casa a hacer diligencias y regresas.
Se habla de un camino Euleriano cuando sales de tu origen y llegas a tu destino recorriendo todas las aristas SIN repetir alguna.
Se habla de un camino Hamiltoneano cuando sales de tu origen y llegas a tu destino recorriendo todos los vértices SIN repetir alguno.
Cuando hablamos de un ciclo Euleriano, es porque sales y regresas al origen pasando por cada una de las aristas del grafo SIN repetir alguna.
Cuando hablamos de un ciclo Hamiltoneano, es porque sales y regresas al origen pasando por cada uno de los vértices del grafo SIN repetir alguno.
Videos de ayuda
Euler
hamilton
De clic a cada imagen para acceder a los videos de ayuda.
Reforzamiento
Objetivo: Identificar el tipo de camino o recorrido que se solicita en cada grafo.
Indicaciones:
Observe con atención cada grafo, e identifique el tipo de camino o ciclo que posee cada uno colocando Ciclo de Euler/Ciclo de Hamilton; Camino de Euler/Camino de Hamilton en cada grafo. 
Argumente las razones de cada respuesta.
Explicación y ejercicio 25 nov 2016
15
Reforzamiento
a)
b)
c)
d)
e)
f)
Inicio
Inicio
Inicio
Inicio
Inicio
InicioFin
Fin
Fin
Fin
Fin
Fin
24 nov 2016
16
Reforzamiento
Objetivo: reforzar de manera adicional los conocimientos sobre tipo de grafo y camino o ruta.
Indicaciones:
Observe con atención cada uno de los grafos siguientes e identifique para cada uno: el tipo de grafo y camino o ciclo que se recorre. Es importante que argumente sus respuestas.
Queda opcional para hacer en casa
17
Reforzamiento
De V1 a V5
		Ciclo	Camino
	Euler		
	Hamilton		
	Ninguno		
Representación de los grafos.
Matriz de Incidencia.
Trabaja con Vértices.
Lista de Adyacencia.
Trabaja con Vértices en las filas
Y Aristas en las columnas.
Explicación
19
Grafo con matriz de incidencia y lista de adyacencia.
http://mx.answers.yahoo.com/question/index?qid=20100902194220AAJ1B5h
20
Reforzamiento.- Matriz y Lista
Objetivo: elaborar correctamente la matriz de adyacencia y lista de incidencia para cada uno de los grafos.
Indicaciones:
Observe con atención cada uno de los siguientes grafos y elabore correctamente la matriz de adyacencia y la lista de incidencia para cada uno.
Reforzamiento.-Matriz y Lista
		a	b	c	d	e
	a	0	1	0	0	1
	b	1	0	1	0	0
	c	0	1	0	1	0
	d	0	0	1	0	1
	e	1	0	0	1	0
Matriz Incidencia
a
b
c
e
d
Lista Adyacencia
	a	b	e	/
	b	a	c	/
	c	b	d	/
	d	c	e	/
	e	d	a	/
Camino más corto
Es aquel recorrido de un punto de origen a uno de destino pero tratando de ocupar la cantidad mínima de aristas o el valor mínimo recorrido.
Por ejemplo, cuando sales de tu punto de origen (escuela, trabajo) y vas a tu casa a descansar. Por lo general intentas llegar pronto y por ello decides irte por los “atajos” o tomando los caminos que te permitan llegar pronto.
Cuando tomas el GPS para llegar puntual a la reunión, la aplicación te muestra todos los posibles caminos y te dirige en aquel donde llegarías en menos tiempo.
Por ejemplo:
Para este grafo donde el punto de partida será el vértice A y el destino el vértice G, se tiene que los caminos son:
A – B – G = 9
A – C – E – G = 21
A – H – D – B - G = 38
A – D – B – G = 14
A – C- B- G = 16
-
-
A – C – F – H – B – G = 33
Siendo el ROJO el camino más corto.
NOTA: deberá obtener TODOS los caminos desde el punto de partida hasta el destino para demostrar que en realidad encontró el más corto.
FIN
INICIO
Programando…
Objetivo: crear un programa que permita encontrar el camino más corto según los valores dados por el usuario.
Indicaciones: realizar un programa que permita encontrar el camino más corto según los valores que el usuario introduzca en cada arista y siempre para el mismo grafo.
Requisitos:
Mostrar el grafo al usuario.
Pedir los valores para cada una de las aristas.
Calcular el camino más corto.
Mostrar el camino más corto en el grafo 
 (de acuerdo a los datos dados por el usuario).
Entrega en ejecutable funcionando correctamente
Se explica el 29 nov 2016
25
Programando…
El camino es de V1 hasta V4
INICIO
FIN
26
Fuentes de información.
Johnsonbaugh, R. Matemáticas Discretas. “Representación de un grafo”. Editorial Gandhi. Disponible en: http://books.google.com.mx/
Ejercicios propuestos. http://es.slideshare.net/Amanda_84/grafosejerciciospropuestos
Algoritmos de búsqueda de profundidad y anchura. http://www.dma.fi.upm.es/java/matematicadiscreta/busqueda/
Algoritmos de búsqueda de profundidad y anchura (video). http://www.youtube.com/watch?v=f_52-Obuq5M
Grafos. Estructura de Datos. http://www.itnuevolaredo.edu.mx/maestros/sis_com/takeyas/Apuntes/Estructura%20de%20Datos/Apuntes/grafos/Apuntes_Grafos.pdf
Libro de Matemáticas Discretas.
http://books.google.com.mx/books?id=cJERA7Y04iwC&pg=PA355&lpg=PA355&dq=matriz+de+incidencia+matem%C3%A1ticas+discretas&source=bl&ots=_cNuVhA3u4&sig=dOpAnW24dBXakA3sodWqUZ70_IY&hl=es&sa=X&ei=d2-XUpSnB4bNkAearYGwCw&ved=0CDsQ6AEwAw#v=onepage&q=matriz%20de%20incidencia%20matem%C3%A1ticas%20discretas&f=false
27