Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Presentación Grafos

No description
by

David Brandán

on 9 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Presentación Grafos

Historia de Grafos ¿Qué es un grafo? Grado de un vértice Problema de inicio Grafo etiquetado
o ponderado Grafos completos Isomorfismos Dígrafo Representaciones
gráficas Caminos y ciclos Leonhard Euler (1707 - 1783)
Pionero en esta teoría por
su reflexión sobre el problema de los siete puentes de Königsberg. William Rowan Hamilton (1805-1865) Ideó un juego de recorridos en un poliedro
que años después daría lugar a los circuitos Hamiltonianos
de gran interés por sus aplicaciones. Otros matemáticos que aportaron a la teoría...
Dénes König (1884-1944) - Primero en publicar un libro sobre grafos.
Frank Harary (1921-2005) - Padre de la teoría moderna de los grafos.
Edsger Dijkstra (1930-2002) - Teorema camino más corta. Grafos planos Grafo Poligonal Grafos en informática Grafos en Arquitectura
y Urbanismo Grafos y colores Sistema matemático abstracto representado mediante diagramas. Conjunto de puntos y lineas donde cada linea une un punto con otro. Llamaremos grafo, G, al par ordenado formado por un conjunto finito no vacío, V, y un conjunto, A, de pares no ordenados de elementos del mismo. V es el conjunto de los vértices o nodos del grafo. A será el conjunto de las aristas o arcos del grafo.
Utilizaremos la notación G = (V,A) para designar al grafo cuyos conjuntos de vértices y aristas son, respectivamente, V y A. Multigrafo y Pseudografo Los grafos en los que cualquier par de vértices está conectado por una arista se denominan completos o universales. Un grafo ponderado asocia un valor (costo) a cada
enlace en el grafo.
El peso de un camino en un grafo ponderado, es la suma
de los pesos de todos los enlaces atravesados. Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2, y una función biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo. ¿Puede dotarse a cada casa con los tres servicios, agua, luz y gas, de manera que las conexiones no se crucen y estén en un mismo plano? Mapa de subtes En los primeros mapas de subte cada línea se dibujaba su trazado de manera fiel a la realidad: con sus curvas sinuosas y guardando una proporcionalidad en las distancias entre estaciones: unas se ven más alejadas entre sí que otras, en correspondencia con las distancias reales. Mapa de subtes de la ciudad
de Londres Donde las estaciones son representadas por los nodos o vértices, y las vías intermediarias son las aristas o arcos, este tipo de mapas es una clara presentación de un grafo dirigido, ya que obviamente tenemos un sentido de dirección. Un camino en G es una sucesión donde se alternan vértices y aristas, comenzando y terminando con vértices y en el que cada arista es incidente con los dos vértices que la preceden y la siguen, es decir, es una sucesión de aristas adyacentes distintas. Un ciclo en G es un camino en el que sus extremos coinciden. El ciclo será simple si no hay, además del primero y el último, ningún otro vértice repetido, o sea, es un camino cerrado donde el vértice inicial es igual al vértice final. Existen dos tipos de caminos y ciclos:
EULERIANOS Y HAMILTONIANOS CICLO DE EULER
Un ciclo se dice de Euler si pasa por todos los vértices recorriendo cada arista exactamente una vez.Una condición necesaria para que un grafo tenga ciclo euleriano es que sea conexo y que todos sus vértices sean de grado par. Este grafo es un claro ejemplo de un ciclo euleriano, se puede apreciar que todos los vértices tienen grado par. CAMINO DE EULER
Se dice que un camino de es de Euler si pasa por todos los vértices del mismo, recorriendo cada arista del mismo exactamente una vez.Una condición necesaria para que un grafo tenga un camino euleriano es que el grafo sea conexo y que todos los vértices tengan grado par o a lo sumo dos de grado impar. Este grafo es conexo y tiene exactamente
dos vértices de grado impar, el v1 y el v3
que tienen grado cinco. HAMILTON, DODECAEDRO DEL VIAJERO
Hamilton inventó un juego matemático llamado el “dodecaedro del viajero”. Tal juego consiste en un dodecaedro donde cada uno de sus veinte vértices estaba etiquetado con el nombre de una ciudad de la época. El objetivo del juego era viajar a lo largo de las aristas del dodecaedro, visitando cada ciudad exactamente una vez y volviendo al punto de partida. Tal recorrido se denomina “un viaje alrededor del mundo”. CICLO HAMILTONIANO
Un ciclo se dice que es de Hamilton, si contiene todos los vértices (que pasa por todos los vértices) de G. Para que un grafo sea hamiltoniano obviamente debe contener un ciclo del mismo. CAMINO HAMILTONIANO
Un camino simple en un grafo o multígrafo G que contenga (que pase por) todos los vértices se denomina camino de Hamilton Problema de los seis saltos
Es una hipótesis que intenta probar que cualquiera en la Tierra puede estar conectado a cualquier otra persona del planeta a través de una cadena de conocidos que no tiene más de cinco intermediarios. El concepto está basado en la idea de que el número de conocidos crece exponencialmente con el número de enlaces en la cadena, y sólo un pequeño número de enlaces son necesarios para que el conjunto de conocidos se convierta en la población humana entera. Redes sociales
Una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes. Este gráfico es una representación de la utilización de grafos en internet. Esta aplicación en particular muestra la relación o amistad en Facebook de un usuario con el resto de sus contactos, y las amistades que existen entre ellos (amigos en común). Redes de computadorasOtra de las tantas aplicaciones es para representar redes de computadoras, donde los nodos son las computadoras y los vértices son las redes utilizadas para intercambiar datos. Mapa de sitioUn mapa de sitio web es una lista de las páginas de un sitio web accesibles por parte de los buscadores y los usuarios. Donde las páginas aparecen como nodos y los enlaces entre ellas son los vértices. Mapa de sitio de Google
para los desarrolladores web. La mayoría de los mapas geográficos pueden interpretarse como grafos en lo que los vértices son los puntos de confluencia de tres o más líneas y las aristas son las líneas delimitantes de cada territorio o zona. Un problema de los elaboradoras de mapas ha sido intentar colorearlos siguiendo el criterio de que países o zonas diferentes deben tener colores distintos. Aparece de forma natural, la cuestión: dado un mapa ¿cuál es la mínima cantidad de colores necesaria para colorearlo de forma que zonas con frontera común tengan colores diferentes? Teorema de cuatro colores.
Dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes, de forma que no queden regiones adyacentes (es decir, regiones que compartan no sólo un punto, sino todo un segmento de borde en común) con el mismo color. No es posible colorear cualquier mapa en estas condiciones utilizando sólo tres colores. En cambio, sí es posible hacerlo considerando cinco colores. GRAFO CONEXO
Un grafo se dice que es conexo si cada par de vértices están conectados, es decir cuando existe una conexión o camino para llegar a todos sus vértices. Un comerciante español, que reside en Sant Celoni, compró un auto que funciona a energía solar,
para ahorrar combustible en sus frecuentes viajes laborales a dos ciudades: I’Escala y Ripoll.
Estas tres ciudades están conectadas por rutas como muestra el siguiente mapa: Los kilómetros que muestra el mapa son distancias aproximadas entre ciudades y los círculos numerados indican la cantidad de peajes que hay en cada tramo de ruta que las une. Como al comerciante no le preocupan las distancias, porque no gasta combustible y tampoco le preocupa demasiado el tiempo, pues siempre emprende sus viajes con uno o dos días de anticipación, por lo tanto, lo único que le interesa es gastar la menor cantidad de dinero posible en peajes. Si sale de su ciudad Sant Celoni, ¿qué camino le resultará más económico, para llegar a la ciudad de I’Escala? ¿Cuántos peajes tendrá que pagar, si sigue ese camino? Y, una vez que haya llegado a esa ciudad, ¿Cuál será el camino que más le convendrá, si tiene que viajar a Ripoll? Grafo regular Suma de los Grados de un Grafo
En cualquier grafo se verifica,
(a) La suma de todos sus grados es igual al doble del número de sus aristas.
(b) El n´umero de vértices de grado impar es par Henry Beck cayó en la cuenta de que al viajero no le importan esos detalles, sino sólo saber cuál es el orden de estaciones en cada línea y dónde hay conexiones entre líneas. Exactamente hizo lo mismo que Euler con el problema de los puentes. Y adoptó su misma estrategia: sustituir el mapa geográfico por un grafo simplificado que conserve las posiciones relativas y las conexiones. ¿Se puede construir
un grafo regular
con 10 aristas en el que
cada vértice tenga grado 4? Llamaremos grado o valencia
de un vértice al número de aristas
que incidan en él. Un grafo
se dice que es regular
cuando todos sus vértices
tienen el mismo grado Matrices •de incidencia tiene n filas y k columnas, donde cada fila corresponde a un vértice y cada columna a una arista.

•la matriz de adyacencia de vértices es cuadrada y tiene n filas por n columnas.

•Los lazos aparecen en la diagonal de la matriz •El dígrafo es un grafo en el cual el conjunto de las aristas A está formado por pares ordenados del conjunto de vértices V. Puede llamarse también grafo dirigido.•Esto asigna un orden a los extremos de cada arista.•A las aristas orientadas o direccionadas se las denomina arcos. El arco (a, b) de la figura está dado por un par ordenado (donde el primer elemento es su vértice inicial y el segundo su vértice final) mientras que en los grafos no orientados el arco es descrito por un par no ordenado {a,b}. Un grafo es plano si existe un grafo isomorfo que puede dibujarse en el plano de modo que las aristas sólo se crucen en los vértices. Teorema de KURATOWSKI •Encontró un método eficaz para reconocer la planitud de un grafo, sin recurrir a sus posibles representaciones isomorfas
•Descubrió que existen solamente dos grafos no planos: el correspondiente al problema de las tres casas y las tres utilidades y el grafo de cinco vértices tales que cada vértice está conectado con los restantes. •Estos grafos permiten definir toda una familia de grafos que no son planos.
•La condición necesaria y suficiente para que un grafo sea plano es que no admita subgrafos ni del tipo K3 3 ni del tipo K5. •Un grafo plano conexo que es reunión de ciclos y tal que existe un ciclo mínimo y otro máximo. Intuitivamente, eso significa que un grafo poligonal divide el plano en zonas poligonales.
•El interior de cada ciclo se llama cara, En consecuencia, en todo grafo poligonal se cuenta no solamente el número de vértices V y el de aristas A, sino también el de caras C.
•Se puede comprobar que, entre el número C de caras, el número V de vértices y el número A de aristas, vale la fórmula de Euler: C + V = A + 2. •Un grafo poligonal es regular si en cada vértice concurre igual número de aristas.
•Si, además de ser regular, tiene la propiedad de que cada cara posee el mismo número de aristas limitantes, se dice que el grafo es completamente regular. Mosaicos Regulares Un tipo especial de recubrimiento del plano es el mosaico. Los diferentes tipos de mosaicos se obtienen siguiendo un principio general de repetición de un módulo en dos direcciones, con condiciones restrictivas de acoplamiento y regularidad.
El ángulo interior en cada vértice vale:
[(n-2)/n]*180 Algoritmo de Dijkstra El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. CAMINO EULERIANO EN UN DIGRAFO
Cuando se va a trabajar sobre grafos dirigidos, es necesario definir la adyacencia y la incidencia de un vértice. Se define como adyacencia de un vértice el número de aristas que parten de él, mientras que la incidencia es el número de aristas que llegan a él. Un grafo tendrá un camino euleriano dirigido si cada uno de sus vértices tiene igual número de incidencias que de adyacencias, salvo un vértice que tenga una adyacencia más que incidencias (el comienzo del camino) y otro que tenga una incidencia más que adyacencias (el final del camino). Debe contemplarse también el caso especial del ciclo euleriano dirigido, en el que el vértice de comienzo y final del camino son el mismo, y por tanto en todos los vértices coincide el número de incidencias con el de adyacencias. Trabajar con grafos en un proyecto arquitectónico permite visualizar en forma explícita las conexiones para estudiar y optimizar el edificio que se debe diseñar. Es posible, por ejemplo, utilizarlos en el estudio del vínculo visual, acústico o térmico, y de todo otro tipo de interacción entre los locales. Es factible, además proyectar las instalaciones, su tendido y sus interconexiones. Edificio histórico ampliamente conocido, la Villa Rotonda, obra de Andrea Palladio.
Comparación de niveles acústicos Casa para Hermann Lange, obra del arquitecto Mies van der Rohe.
Se analizan las transferencias de sonidos (ruidos) entre locales y desde el exterior. Con el grosor de línea en cada arista se indica el nivel sonoro (a mayor nivel, mayor grosor).
Grafos de relaciones
entre los elementos perfilados. Estudio de las distribuciones “óptimas” de elementos arquitectónicos que minimizan los problemas de recorrido. Análisis de “rutas usuales”: puede llevar a una reagrupación específica que facilite tales comunicaciones. Grafos de relaciones entre los elementos perfilados
Full transcript