teoría de grafos. temario teoría de grafos grafos conceptos básicos problemas clásicos...
TRANSCRIPT
![Page 1: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/1.jpg)
Teoría de Grafos
![Page 2: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/2.jpg)
Temario
Teoría de Grafos
• GrafosConceptos básicos
Problemas clásicos
Algoritmos en grafos
• MetaheurísticasAlgoritmos Genéticos
Tabú Search
Colonia de Hormigas
• Ejercicios
• Conclusiones
![Page 3: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/3.jpg)
Definición
Teoría de Grafos
Estudia las propiedades de los grafos.
Grafo: un grafo es un conjunto, no vacío, de objetos llamados nodos (o vértices) y una selección de pares de nodos, llamados ejes (o aristas) donde estos pueden ser orientados o no.
Un grafo G = (V,X), donde V es un conjunto nodos y X es un subconjunto del conjunto de pares no ordenados de elementos distintos de V.
![Page 4: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/4.jpg)
Definición
Teoría de Grafos
• Nodos / Vértices: constituyen los objetos de la situación a representar. Ejemplo: V = {A,B,C,D,E}
• Ejes / Aristas /Arcos: conforman las relaciones entre un par de objetos representados por los nodos.
Ejemplo: X = {(A,B),(A,C),(B,C),(B,E),(C,D),(D,E)}
Tanto los nodos como ejes, pueden tener atributos cuantitativos y/o cualitativos (variables de cualquier tipo).
![Page 5: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/5.jpg)
Ejemlos
Teoría de Grafos
![Page 6: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/6.jpg)
HistoriaEl problema de los siete puentes de Königsberg Fue fue planteado y resuelto por Leonhard Euler en 1736, dando
origen a la Teoría de los grafos.
Teoría de Grafos
Dos islas en el río Pregel que cruza Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?
![Page 7: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/7.jpg)
Historia
Teoría de Grafos
B
ISLA C
A
Mapa
Grafo de Representación
4 5
2 3
1
Más adelante vamos a analizar este problema, y vamos a ver que es similar al de los 7 puentes
![Page 8: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/8.jpg)
HistoriaEl problema de los cuatro coloresFue introducido en 1852 por Francis
Guthrie, donde plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color.
Fue resuelto en 1976 por Appel y Haken. Se usaron computadoras en la demostración.
Teoría de Grafos
![Page 9: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/9.jpg)
AplicacionesRedes conceptuales
Teoría de Grafos
![Page 10: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/10.jpg)
AplicacionesRedes de transporte
Teoría de Grafos
![Page 11: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/11.jpg)
AplicacionesPlano de autopistas
Teoría de Grafos
![Page 12: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/12.jpg)
AplicacionesCircuitos electricos
Teoría de Grafos
![Page 13: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/13.jpg)
AplicacionesRed Social
Teoría de Grafos
![Page 14: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/14.jpg)
AplicacionesOrganigramas
Teoría de Grafos
![Page 15: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/15.jpg)
AplicacionesPolimeros
Teoría de Grafos
![Page 16: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/16.jpg)
Atributos CualitativosEs lo que se conoce como variables nominales
• En Nodos: sirve para identificar o describir al objeto que se quiere representar
• En Ejes: describe el tipo de relación que hay entre dos objetos.
Teoría de Grafos
![Page 17: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/17.jpg)
Atributos CuantitativosCorresponden a variables ordinales
• En Nodos: miden algún aspecto común entre los distintos objetos
• En Ejes: miden la intensidad de la relación
Teoría de Grafos
71012
56
107
12
5
6
![Page 18: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/18.jpg)
Topologías
Teoría de Grafos
D
IB
C
FE
H
GA
D
IB
C
FE
H
G A
D
I
B
CF
E
H
GEstrella
Anillo
Árbol
![Page 19: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/19.jpg)
BEje A-BA
BEje A-B
AEje B-A
Clasificación
Teoría de Grafos
No orientados o Bidireccionales
Orientados o Direccionados
Grafos
Eje1 A-B
Eje3 B-A
BEje3 A-B
Eje2 A-B
Eje1 B-A
A
Eje2 A-B
BEje4 A-B
Eje3 A-B
Eje1 B-A
A
Multigrafos
Es el caso más general
![Page 20: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/20.jpg)
Eje1 A-B
Eje3 B-A
BEje3 A-B
Eje2 A-B
A
Eje2 A-A
BEje4 A-B
Eje3 A-BABEje A-BA
BEje A-B
AEje B-A
Eje A-A
Clasificación
Teoría de Grafos
No orientados o Bidireccionales
Orientados o Direccionados
Pseudo-Grafos
Es el caso más particular
Pseudo-Multigrafos
Mixtos
![Page 21: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/21.jpg)
Definiciones Varias
• subgrafos
• Grados de un grafo
• Caminos
• Ciclos
• Grafos Autocomplementos
• Nodos Críticos
• Componentes conexas
Teoría de Grafos
![Page 22: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/22.jpg)
Grado de un Nodo• El grado de un nodo es la cantidad de ejes
incidentes al vértice v.
• Notación: d(v) = grado de v.
• Teorema: La suma de los grados de los nodos de un grafo es 2 veces el número de ejes, o sea:
i=1,n d (vi) = 2 m
Teoría de Grafos
![Page 23: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/23.jpg)
Definiciones en Grafos• Un camino en un grafo es una sucesión de ejes e1 e2.......ek tal que un extremo de ei coincide con
uno de ei-1 y el otro con uno de ei+1.
• Un camino simple es un camino que no pasa dos veces por el mismo nodo.
• Un circuito es un camino que empieza y termina en el mismo nodo.
• Un circuito simple es un circuito de 3 o más nodos que no pasa dos veces por el mismo nodo.
Teoría de Grafos
![Page 24: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/24.jpg)
Definiciones en Digrafos• Un camino orientado en un grafo orientado es una sucesión de ejes e1 e2.......ek tal que el primer
elemento del par ei coincide con el segundo de ei-1 y el segundo elemento de ei con el primero de ei+1.
• Un circuito orientado en un grafo orientado es un camino orientado que empieza y termina en el mismo nodo.
• Un digrafo se dice fuertemente conexo si entre para cualquier par de nodos (v,u) hay un camino orientado de v a u.
Teoría de Grafos
![Page 25: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/25.jpg)
Componentes Conexas
Teoría de Grafos
Grafo 1: 6 componentes conexas
Grafo 1: 3 componentes
conexas
Un grafo se dice conexo si existe un camino entre todo par de nodos.
![Page 26: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/26.jpg)
Grafos Completos
Teoría de Grafos
AB
C D
AB
C
D
AB
C E
K3 K4 K5
• Se relacionan todos los nodos contra todos• Son objeto de estudio y Sirven como cotas máximas
•Un grafo se dice completo si todos los nodos son adyacentes entre si.
![Page 27: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/27.jpg)
Ejemplo 1: calles de una ciudad
100
4
10
13
14
987
5
1 23
11 12
17 18
1615100
100100
100
100
100
100100
100
100
100
100
526
120
30
100
100 100
100
100
100100
100
100 100
70
120100
Teoría de Grafos
![Page 28: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/28.jpg)
Ejemplo 2: Cronogramas de Proyectos
![Page 29: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/29.jpg)
Isomorfismo
• un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.
• A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:
Teoría de Grafos
![Page 30: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/30.jpg)
f(a)=1f(b)=6f(c)=8f(d)=3f(g)=5f(h)=2f(i)=4f(j)=7
Teoría de Grafos
![Page 31: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/31.jpg)
CENTRALIDAD de un vértice en un grafo determina la importancia relativa de un vértice en el grafo, la importancia de una persona involucrada en una red social, o, en la teoría de la denominada sintaxis del
espacio que se estudia lo importante que puede llegar a ser una habitación en un edificio, así como una
carretera en una red urbana.
Teoría de Grafos
![Page 32: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/32.jpg)
CENTRALIDADGrado=número de nodos conectados con un nodo dadoCercanía o Closeness= suma de la suma de las distancias de un nodo con respecto a sus vecinosIntermediación =indica la frecuencia con la que un nodo aparece en el camino más corto que conecta otros dos nodos, a dicho camino se le suele denominar camino geodésico.
Teoría de Grafos
![Page 33: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/33.jpg)
Representación de Grafos
• Matriz de Adyacencia e Incidencia
• Lista de Adyacencia
• La representación varía dependiendo del tipo de grafo elegido.
Teoría de Grafos
![Page 34: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/34.jpg)
Teoría de Grafos
Matrices de Adyacencia e Incidencia
![Page 35: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/35.jpg)
Teoría de Grafos
Matriz de Distancias Geodésicas
![Page 36: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/36.jpg)
Árboles• Son una categoría particular dentro de
grafos.
Teoría de Grafos
![Page 37: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/37.jpg)
Arbol Generador Mínimo
• Algoritmo de Prim
Teoría de Grafos
![Page 38: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/38.jpg)
AlgoritmosEn matemáticas y ciencias de la computación, es una lista bien
definida , ordenada y finita de operaciones que permite hallar la solución a un problema.
Se escriben en un lenguaje formal (lenguaje de programación) que luego es interpretado por una computadora
En la vida cotidiana se emplean algoritmos en múltiples ocasiones para resolver diversos problemas
• Recetas de cocina• Instructivos: para el uso de un artefacto, o para el aprendizaje
de alguna tarea• Diagnóstico de enfermedades en pacientes• Etc, etc, etc.
Algoritmos
![Page 39: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/39.jpg)
Algoritmos
Ejemplo: Cálculo de Raíces Cuadradas
![Page 40: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/40.jpg)
Algoritmos
Complejidad AlgorítmicaProblemas Sencillos: por su naturaleza, para esta clase
de problemas existe un algoritmo que lo resuelve en un tiempo razonable. Se los denomina:
P: polinomialProblemas Complejos: contrario al los anteriores, son
problemas que admiten una cantidad exponencial de posibilidades. Explorar a todas para obtener la mejor solución, puede requerir miles de años. Por esa razón se realizan estos pro Se los denomina:
NP: nondeterministic polinomial
![Page 41: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/41.jpg)
METAHEURÍSTICAS
COLONIA DEHORMIGAS
TABÚ SEARCH
ALGORITMOSGENÉTICOS
ETC.
ALGORITMOS
ALGORITMOSAPROXIMADOS- HEURÍSTICAS
PROBLEMAS PPROBLEMAS
NP, NP - HARD
ALGORITMOSEXACTOS
Algoritmos, Heurísticas y Metaheurísticas
Meta-Heurísticas
![Page 42: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/42.jpg)
Heurística
Dado un problema, un algoritmo heurístico es un algoritmo que intenta obtener soluciones para el problema que intenta resolver pero no necesariamente lo hace en todos los casos.
Heurísticas
![Page 43: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/43.jpg)
Algoritmos Genéticos
Algoritmos sometidos a azar y seleccion ( en base a un criterio previo)
Meta-Heurísticas
![Page 44: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/44.jpg)
Tabú SearchMetaheurística muy utilizada en problemas de
optimización combinatoria. Dichos problemas se caracterizan por ser complejos de modelar, visualizar, tener muchas variables involucradas, no conocérseles buenos algoritmos exactos que los resuelvan en un tiempo razonable, etc.
Algoritmos
![Page 45: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/45.jpg)
Tabú SearchLos rasgos más relevantes son:
• Parte de una única solución inicial, que luego va modificando hasta obtener el resultado
• Acepta peores soluciones que la mejor encontrada hasta el momento
• Utiliza una lista tabú de soluciones, o fragmentos de estas, con el objeto de forzar al algoritmo a explorar nuevas soluciones, y evitar de esta manera que el algoritmo caiga en un ciclo repetitivo (mínimo local)
Algoritmos
![Page 46: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/46.jpg)
Tabú Search
Algoritmos
• Parto de una única sol. Inicial • Lista tabú• Mínimos Locales
![Page 47: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/47.jpg)
Algoritmos
![Page 48: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/48.jpg)
• Arbol de desición: Tablero de ajedrez
• Ver si da para poner este ejemplo.
• Ejemplificar algoritmo exacto vs. Aproximado
Algoritmos
![Page 49: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/49.jpg)
Modelado del Grafo
• Hacer hincapié en que modele la realidad. Un algoritmo resuelve un problema determinado en cualquier grafo, pero cualquier cambio en este, cambia la solución.
• Es importante reflejar de manera exacta la realidad
Algoritmos
![Page 50: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/50.jpg)
A* Pathfinder
• Encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo.
Teoría de Grafos
![Page 51: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/51.jpg)
Circuitos & Caminos Eulerianos
Teoría de Grafos
B
ISLA C
A
2
61
4
5
8
3
7
![Page 52: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/52.jpg)
Circuitos & Caminos Eulerianos
Teoría de Grafos
![Page 53: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/53.jpg)
Circuitos & Caminos Eulerianos
Teoría de Grafos
• Circuito Eureliano: hay un circuito que pasa por todos los ejes del grafo una y sólo una vez si y sólo si cada nodo tiene grado par de ejes incidentes.
• Camino Eureliano:hay un camino que pasa por todos los ejes del grafo una y sólo una vez si y sólo si cada nodo tiene grado par de ejes incidentes, y sólo dos de ellos tienen grado impar, conformando de esta manera el inicio y el fin del camino.
![Page 54: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/54.jpg)
Circuitos Hamiltoneanos
Teoría de Grafos
![Page 55: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/55.jpg)
Diejkstra
Teoría de Grafos
• Caminos mínimos. Determina el camino mas corto entre los nodos de un grafo.
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
![Page 56: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/56.jpg)
Problema del Viajante de comercio
Teoría de Grafos
![Page 57: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/57.jpg)
N-Cliqué• Una clique en un grafo es un conjunto de
vértices dos a dos adyacentes. En el grafo de la derecha, los vértices 1, 2 y 5 forman una clique porque cada uno tiene un arco que le une a los otros. En cambio, los vértices 2, 3 y 4 no, dado que 2 y 4 no son adyacentes.
Teoría de Grafos
![Page 58: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/58.jpg)
N-Cliqué
Teoría de Grafos
![Page 59: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/59.jpg)
Coloreo de Mapas
Teoría de Grafos
![Page 60: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/60.jpg)
Coloreo de Mapas
Teoría de Grafos
![Page 61: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/61.jpg)
Metodología de trabajo
Teoría de Grafos
• Tengo pensado un breve procedimiento de cómo encarar un problema para modelar con grafos. Hacer incapié en que el modelado es estricto, y explicar cómo trabajan los algoritmos en grafos.
• Mencionar el ejemplo de la ciudad, cartero chino, recolector de basura.
• Mencionar la tesis de recolector de basura zona zur.
• Mencionar Caso Cabezas• Boqueteros.
![Page 62: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/62.jpg)
Ejercicio 1
Teoría de Grafos
El grafo de la siguiente figura representa una red telefónica. Los nodos representan centrales y los ejes líneas telefónicas. Se quiere estudiar la vulnerabilidad de la red ante algún defecto.
![Page 63: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/63.jpg)
Ejercicio 2
Teoría de Grafos
Dados los grafos y digrafos de la figura:
• Escribir las matrices de adyacencia e incidencia.
• Representar mediante listas de aristas y listas de adyacencias.
• Calcular los conjuntos de sucesores y de predecesores de los vértices de los digrafos de la figura
• Calcular el grado de cada vértice, de cada uno de los grafos
![Page 64: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/64.jpg)
Ejercicio 3
Teoría de Grafos
Dadas las siguientes matrices de adyacencia representar el correspondiente grafo o multigrafo (no orientado).
Representar los siguientes digrafos cuyas matrices de adyacencia son
![Page 65: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/65.jpg)
Ejercicio 4
Teoría de Grafos
Armar las matrices de adyacencia, de incidencia y geodésica de cada uno de los siguientes grafos. Calcular el grado de cada uno de sus nodos.
E
D
C
BA 10
64
37
1
6
5 432
10
7
0
15
7
10
5
10
55
4
5
7
3
1
6
5
4
32
7
0 707
9
8
751
150
6102685
10651688
1460
1167
744
186458
529
2361765
359
849
1218
719
1935
708
![Page 66: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/66.jpg)
Ejercicio 5
Teoría de Grafos
Determinar cuales de estos pares de grafos son isomorfos.
![Page 67: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/67.jpg)
Ejercicio 6
Teoría de Grafos
• Armar un grafo que modele algún comportamiento y/o situación de la realidad.
• Fundamentar la definición de nodos y ejes del grafo.
Me tienen que ayudar a redactar este ejercicio. La idea es que modelen una sitiación con un grafo y apliquen conceptos de los que vimos a ese modelo, respondiendo a cuestiones propias de la situación representada
![Page 68: Teoría de Grafos. Temario Teoría de Grafos Grafos Conceptos básicos Problemas clásicos Algoritmos en grafos Metaheurísticas Algoritmos Genéticos Tabú](https://reader033.vdocumento.com/reader033/viewer/2022061417/5665b4e91a28abb57c94b3c1/html5/thumbnails/68.jpg)
Links Relacionados
Teoría de Grafos
• http://www.antropocaos.com.ar/seminario
• http://www.dc.uba.ar/people/materias/aed3/homepage.html
• http://www.dc.uba.ar/aca/materias/