Teoría de Grafos
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
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.
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).
Ejemlos
Teoría de Grafos
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?
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
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
AplicacionesRedes conceptuales
Teoría de Grafos
AplicacionesRedes de transporte
Teoría de Grafos
AplicacionesPlano de autopistas
Teoría de Grafos
AplicacionesCircuitos electricos
Teoría de Grafos
AplicacionesRed Social
Teoría de Grafos
AplicacionesOrganigramas
Teoría de Grafos
AplicacionesPolimeros
Teoría de Grafos
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
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
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
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
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
Definiciones Varias
• subgrafos
• Grados de un grafo
• Caminos
• Ciclos
• Grafos Autocomplementos
• Nodos Críticos
• Componentes conexas
Teoría de Grafos
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
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
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
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.
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.
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
Ejemplo 2: Cronogramas de Proyectos
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
f(a)=1f(b)=6f(c)=8f(d)=3f(g)=5f(h)=2f(i)=4f(j)=7
Teoría de Grafos
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
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
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
Teoría de Grafos
Matrices de Adyacencia e Incidencia
Teoría de Grafos
Matriz de Distancias Geodésicas
Árboles• Son una categoría particular dentro de
grafos.
Teoría de Grafos
Arbol Generador Mínimo
• Algoritmo de Prim
Teoría de Grafos
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
Algoritmos
Ejemplo: Cálculo de Raíces Cuadradas
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
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
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
Algoritmos Genéticos
Algoritmos sometidos a azar y seleccion ( en base a un criterio previo)
Meta-Heurísticas
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
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
Tabú Search
Algoritmos
• Parto de una única sol. Inicial • Lista tabú• Mínimos Locales
Algoritmos
• Arbol de desición: Tablero de ajedrez
• Ver si da para poner este ejemplo.
• Ejemplificar algoritmo exacto vs. Aproximado
Algoritmos
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
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
Circuitos & Caminos Eulerianos
Teoría de Grafos
B
ISLA C
A
2
61
4
5
8
3
7
Circuitos & Caminos Eulerianos
Teoría de Grafos
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.
Circuitos Hamiltoneanos
Teoría de Grafos
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
Problema del Viajante de comercio
Teoría de Grafos
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
N-Cliqué
Teoría de Grafos
Coloreo de Mapas
Teoría de Grafos
Coloreo de Mapas
Teoría de Grafos
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.
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.
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
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
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
Ejercicio 5
Teoría de Grafos
Determinar cuales de estos pares de grafos son isomorfos.
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
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/
