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ú.

  • Published on
    25-Jan-2016

  • View
    236

  • Download
    0

Embed Size (px)

Transcript

  • Teora de Grafos

  • Temario

    GrafosConceptos bsicosProblemas clsicosAlgoritmos en grafosMetaheursticasAlgoritmos GenticosTab SearchColonia de HormigasEjerciciosConclusiones

  • DefinicinEstudia las propiedades de los grafos. Grafo: un grafo es un conjunto, no vaco, de objetos llamados nodos (o vrtices) y una seleccin 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.

  • DefinicinNodos / Vrtices: constituyen los objetos de la situacin 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

  • HistoriaEl problema de los siete puentes de Knigsberg Fue fue planteado y resuelto por Leonhard Euler en 1736, dando origen a la Teora de los grafos. Dos islas en el ro Pregel que cruza Knigsberg 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?

  • HistoriaMapaGrafo de Representacin

    B

    ISLA

    C

    A

  • 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 pases de tal forma que dos pases vecinos nunca tengan el mismo color. Fue resuelto en 1976 por Appel y Haken. Se usaron computadoras en la demostracin.

  • AplicacionesRedes conceptuales

  • AplicacionesRedes de transporte

  • AplicacionesPlano de autopistas

  • AplicacionesCircuitos electricos

  • AplicacionesRed Social

  • AplicacionesOrganigramas

  • AplicacionesPolimeros

  • Atributos CualitativosEs lo que se conoce como variables nominalesEn Nodos: sirve para identificar o describir al objeto que se quiere representarEn Ejes: describe el tipo de relacin que hay entre dos objetos.

  • Atributos CuantitativosCorresponden a variables ordinalesEn Nodos: miden algn aspecto comn entre los distintos objetosEn Ejes: miden la intensidad de la relacin

    7

    10

    12

    5

    6

    10

    7

    12

    5

    6

  • TopologasEstrellaAnillorbol

    D

    I

    B

    C

    F

    E

    H

    G

    A

    D

    I

    B

    C

    F

    E

    H

    G

    A

    D

    I

    B

    C

    F

    E

    H

    G

  • ClasificacinNo orientados o BidireccionalesOrientados o DireccionadosGrafos

    B

    Eje A-B

    B

    A

    Eje B-A

    Eje A-B

    A

  • ClasificacinNo orientados o BidireccionalesOrientados o DireccionadosPseudo-GrafosPseudo-MultigrafosMixtos

    Eje1 A-B

    Eje3 B-A

    B

    Eje3 A-B

    Eje2 A-B

    A

    Eje2 A-A

    B

    Eje4 A-B

    Eje3 A-B

    A

    B

    Eje A-B

    A

    B

    Eje A-B

    A

    Eje B-A

    Eje A-A

  • Definiciones VariassubgrafosGrados de un grafoCaminosCiclosGrafos AutocomplementosNodos CrticosComponentes conexas

  • Grado de un NodoEl grado de un nodo es la cantidad de ejes incidentes al vrtice v.

    Notacin: d(v) = grado de v.

    Teorema: La suma de los grados de los nodos de un grafo es 2 veces el nmero de ejes, o sea: i=1,n d (vi) = 2 m

  • Definiciones en GrafosUn camino en un grafo es una sucesin 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 ms nodos que no pasa dos veces por el mismo nodo.

  • Definiciones en DigrafosUn camino orientado en un grafo orientado es una sucesin 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.

  • Componentes ConexasGrafo 1: 6 componentes conexasGrafo 1: 3 componentes conexas

    Un grafo se dice conexo si existe un camino entre todo par de nodos.

  • Grafos CompletosK3K4K5Se relacionan todos los nodos contra todosSon objeto de estudio y Sirven como cotas mximasUn grafo se dice completo si todos los nodos son adyacentes entre si.

    A

    B

    C

    D

    A

    B

    C

    D

    A

    B

    C

    E

  • Ejemplo 1: calles de una ciudad

    100

    4

    10

    13

    14

    9

    8

    7

    5

    1

    2

    3

    11

    12

    17

    18

    16

    15

    100

    100

    100

    100

    100

    100

    100

    100

    100

    100

    100

    100

    52

    6

    120

    30

    100

    100

    100

    100

    100

    100

    100

    100

    100

    100

    70

    120

    100

  • Ejemplo 2: Cronogramas de Proyectos

  • Isomorfismoun isomorfismo entre dos grafos G y H es una biyeccin f entre los conjuntos de sus vrtices que preserva la relacin de adyacencia. Es decir, cualquier par de vrtices u y v de G son adyacentes si y solo si lo son sus imgenes, f(u) y f(v), en H.A pesar de su diferente aspecto, los dos grafos que se muestran a continuacin son isomorfos:

  • f(a)=1f(b)=6f(c)=8f(d)=3f(g)=5f(h)=2f(i)=4f(j)=7

  • CENTRALIDAD de un vrtice en un grafo determina la importancia relativa de un vrtice en el grafo, la importancia de una persona involucrada en una red social, o, en la teora de la denominada sintaxis del espacio que se estudia lo importante que puede llegar a ser una habitacin en un edificio, as como una carretera en una red urbana.

  • CENTRALIDADGrado=nmero de nodos conectados con un nodo dadoCercana o Closeness= suma de la suma de las distancias de un nodo con respecto a sus vecinosIntermediacin =indica la frecuencia con la que un nodo aparece en el camino ms corto que conecta otros dos nodos, a dicho camino se le suele denominar camino geodsico.

  • Representacin de GrafosMatriz de Adyacencia e IncidenciaLista de Adyacencia

    La representacin vara dependiendo del tipo de grafo elegido.

  • Matrices de Adyacencia e Incidencia

  • Matriz de Distancias Geodsicas

  • rbolesSon una categora particular dentro de grafos.

  • Arbol Generador MnimoAlgoritmo de Prim

  • AlgoritmosEn matemticas y ciencias de la computacin, es una lista bien definida , ordenada y finita de operaciones que permite hallar la solucin a un problema. Se escriben en un lenguaje formal (lenguaje de programacin) que luego es interpretado por una computadoraEn la vida cotidiana se emplean algoritmos en mltiples ocasiones para resolver diversos problemasRecetas de cocinaInstructivos: para el uso de un artefacto, o para el aprendizaje de alguna tareaDiagnstico de enfermedades en pacientesEtc, etc, etc.

  • Ejemplo: Clculo de Races Cuadradas

  • Complejidad AlgortmicaProblemas 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 solucin, puede requerir miles de aos. Por esa razn se realizan estos pro Se los denomina:NP: nondeterministic polinomial

  • Algoritmos, Heursticas y Metaheursticas

    PROBLEMAS P

    ALGORITMOS

    PROBLEMAS NP, NP - HARD

    ALGORITMOSEXACTOS

    ALGORITMOS APROXIMADOS- HEURSTICAS

    META HEURSTICAS

    COLONIA DE HORMIGAS

    TAB SEARCH

    ALGORITMOSGENTICOS

    ETC.

  • HeursticaDado un problema, un algoritmo heurstico es un algoritmo que intenta obtener soluciones para el problema que intenta resolver pero no necesariamente lo hace en todos los casos.

  • Algoritmos GenticosAlgoritmos sometidos a azar y seleccion ( en base a un criterio previo)

  • Tab SearchMetaheurstica muy utilizada en problemas de optimizacin combinatoria. Dichos problemas se caracterizan por ser complejos de modelar, visualizar, tener muchas variables involucradas, no conocrseles buenos algoritmos exactos que los resuelvan en un tiempo razonable, etc.

  • Tab SearchLos rasgos ms relevantes son:Parte de una nica solucin inicial, que luego va modificando hasta obtener el resultadoAcepta 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 (mnimo local)

  • Tab SearchParto de una nica sol. Inicial Lista tabMnimos Locales

  • Arbol de desicin: Tablero de ajedrezVer si da para poner este ejemplo.Ejemplificar algoritmo exacto vs. Aproximado

  • Modelado del GrafoHacer hincapi en que modele la realidad. Un algoritmo resuelve un problema determinado en cualquier grafo, pero cualquier cambio en este, cambia la solucin.Es importante reflejar de manera exacta la realidad

  • A* PathfinderEncuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo.

  • A* PathfinderAs, el algoritmo A* utiliza una funcin de evaluacin , donde representa el valor heurstico del nodo a evaluar desde el actual, n, hasta el final, y , el coste real del camino recorrido para llegar a dicho nodo, n, desde el nodo inicial.

  • Circuitos & Caminos Eulerianos

    B

    ISLA

    C

    A

    4

    5

    8

    3

    2

    7

    6

    1

  • Circuitos & Caminos Eulerianos

  • Circuitos & Caminos EulerianosCircuito Eureliano: hay un circuito que pasa por todos los ejes del grafo una y slo una vez si y slo si cada nodo tiene grado par de ejes incidentes.Camino Eureliano:hay un camino que pasa por todos los ejes del grafo una y slo una vez si y slo si cada nodo tiene grado par de ejes incidentes, y slo dos de ellos tienen grado impar, conformando de esta manera el inicio y el fin del camino.

  • Circuitos Hamiltoneanos

  • DiejkstraCaminos mnimos. 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

  • N-CliquUna clique en un grafo es un conjunto de vrtices dos a dos adyacentes. En el grafo de la derecha, los vrtices 1, 2 y 5 forman una clique porque cada uno tiene un arco que le une a los otros. En cambio, los vrtices 2, 3 y 4 no, dado que 2 y 4 no son adyacentes.

  • N-Cliqu

  • Coloreo de Mapas

  • Coloreo de Mapas

  • Metodologa de trabajoTengo pensado un breve procedimiento de cmo encarar un problema para modelar con grafos. Hacer incapi en que el modelado es estricto, y explicar cmo 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 CabezasBoqueteros.

  • Ejercicio 1El grafo de la siguiente figura representa una red telefnica. Los nodos representan centrales y los ejes lneas telefnicas. Se quiere estudiar la vulnerabilidad de la red ante algn defecto.

  • Ejercicio 2Dados 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 vrtices de los digrafos de la figuraCalcular el grado de cada vrtice, de cada uno de los grafos

  • Ejercicio 3Dadas las siguientes matrices de adyacencia representar el correspondiente grafo o multigrafo (no orientado).

    Representar los siguientes digrafos cuyas matrices de adyacencia son

  • Ejercicio 4Armar las matrices de adyacencia, de incidencia y geodsica de cada uno de los siguientes grafos. Calcular el grado de cada uno de sus nodos.

    E

    D

    C

    B

    A

    10

    6

    4

    3

    7

    7

    1

    6

    5

    4

    3

    2

    15

    10

    7

    10

    5

    10

    0

    5

    5

    4

    5

    7

    3

    751

    1

    6

    5

    4

    3

    2

    9

    7

    0

    8

    707

    150

    610

    2685

    1065

    1688

    1460

    1167

    744

    186

    458

    529

    236

    1765

    359

    849

    1218

    719

    1935

    708

  • Ejercicio 5Determinar cuales de estos pares de grafos son isomorfos.

  • Ejercicio 6Armar un grafo que modele algn comportamiento y/o situacin de la realidad.Fundamentar la definicin de nodos y ejes del grafo.

    Me tienen que ayudar a redactar este ejercicio. La idea es que modelen una sitiacin con un grafo y apliquen conceptos de los que vimos a ese modelo, respondiendo a cuestiones propias de la situacin representada

  • Links Relacionadoshttp://www.antropocaos.com.ar/seminariohttp://www.dc.uba.ar/people/materias/aed3/homepage.htmlhttp://www.dc.uba.ar/aca/materias/

Recommended

View more >