View
244
Download
7
Category
Preview:
Citation preview
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 1
El programa arquitectónico Uno de los problemas más significativos que enfrenta todo arquitecto en la reconstrucción
compleja de su objeto final, es la de trazar una serie de rutas con la cual constituir un camino
desde el programa arquitectónico hasta el objeto deseado. Éste se definiría como la búsqueda
previa e intencional del arquitecto, de todos los elementos, relaciones y sistemas que
aseguren alcanzar su finalidad en la producción de los espacios habitables, permitiendo la
plena satisfacción de los niveles de vida de la sociedad y de la optimización de los recursos
disponibles.
Muchos arquitectos han utilizado y aplicado la teoría de conjuntos y sistemas, así como la de
grafos. Desarrollaron técnicas especiales en la elaboración de croquis, diagramas y cuadros
de interrelaciones. Este es un método de "estructuración" en el que el dato se excluye de toda
teoría o carga ideológica y sensible para fijar su atención en su componente lógico-matemático
y procesarla mediante métodos electrónicos o estadísticos.
Este método utilizado se basa fundamentalmente en la observación del comportamiento para
llegar a una síntesis formal, esto es a conclusiones objetivas a partir de estas observaciones.
Actualmente, la preocupación esencial pasa por el desarrollo de nuevos aspectos teóricos a
los cuales se pueda recurrir eventualmente en demanda de los instrumentos idóneos para
resolver problemas puntuales y determinados.
En este trabajo, dentro de este contexto, intentaremos armar métodos de resolución
satisfactorios que nos permitan alcanzar nuestro fin de la manera más óptima y con la mejor
calidad.
Aplicación de la teoría de grafos Con su aplicación, clarificaremos las ventajas, puntos críticos y desventajas que puede
presentar la obra arquitectónica, en lo referente a sus sistemas y sub-sistemas (por ejemplo el
funcional-circulatorio, el de relaciones, las conexiones visuales, las acústicas o de adyacencia
y vecindad).
“Esta metodología puede ser aplicada a todo tipo de edificios. Usando este sistema de
análisis, en las primeras instancias del proyecto, podrían evitarse situaciones indeseables
generadas por una falta de sistematización clarificadora en el proceso de diseño, que se torna
más necesaria, cuanto más elevada es la complejidad del edificio en desarrollo." Vera
Spinadel y otros.
Hacia una formalización de conceptos En Matemática se describen las condiciones topológicas como aquéllas que no varían si se
deforma una figura o cuerpo elástico, estirándolo y doblándolo pero sin hacerle cortes, ni
agujeros ni pegar sus partes entre sí. Estas condiciones dan lugar a una compleja teoría. En el
Recopilación Teórica 1 Grafos
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 2
caso de los espacios arquitectónicos, las cualidades topológicas se corresponden con las
condiciones de poseer límites comunes, de ser o no exteriores, la cantidad de espacios con
que limita o se comunica un lugar, las posiciones relativas de perimetralidad o centralización y
la interposición de un espacio con respecto a otros. Así, por ejemplo, si se solicitara la
construcción de dos locales (A y B) en la planta baja de un edificio que tuvieran comunicación
con el hall (H) del mismo y entre sí, la representación de estas condiciones topológicas podría
ser la que se indica en el recuadro de la derecha. El gráfico de la izquierda muestra el croquis
del hall y los locales.
A, B y H son puntos (vértices) que
representan a cada uno de los espacios
y r, m y s son líneas (aristas) que los
unen y representan las comunicaciones
entre ellos.
Este tipo de representación se denomina GRAFO y está formada por un conjunto finito de
vértices y un conjunto finito de aristas de modo tal que existe una determinada condición que
determina la presencia de cada arista uniendo a un par de vértices.
La Teoría de Grafos, constituye un modelo matemático apropiado y accesible para el estudio
de los problemas de organización de espacios arquitectónicos o urbanos; en especial se
adapta muy eficazmente al análisis de las cualidades referentes a la función mecánica
elemental (adaptándose muy especialmente a la investigación de los problemas topológicos y
circulatorios), tanto en la formulación de un marco teórico que acreciente su comprensión
como en la resolución de problemas concretos del diseño y en el desarrollo de técnicas
analíticas aplicables en los campos de crítica y de la historia.
El objetivo de este texto es que ustedes dispongan de los conceptos básicos de la teoría de
grafos, que se consideran de utilidad para diversas situaciones arquitectónicas. La práctica
arquitectónica futura determinará si es necesario profundizar en el estudio de esta teoría. Para
ello, encontrarán al final datos de bibliografía específica.
Veamos entonces, dichos conceptos.
El grafo y sus elementos
Definición de Grafo: Se llama grafo G a una terna (V , A , φ) en la que V es un conjunto finito de puntos (vértices), A es un conjunto finito de líneas (aristas) y φ es una aplicación que asocia a cada elemento de A un par de elementos de V.
Para nuestro ejemplo del croquis: V = { A , B , H } y A = { r , m , s } , siendo φ la aplicación
que determina que dos vértices están unidos por una arista si hay una puerta entre los
ambientes que los vértices representan.
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 3
Formas de representación de un grafo
Hay muchas maneras de representar un grafo. Son ellas: matrices, rejillas, diagramas de
puntos vinculados por líneas -usualmente conocido como diagrama de vértices- y diagramas
de regiones. Vértices y aristas tienen, en cada caso, distinto modo de representación.
Tomemos como ejemplo el grafo de la página anterior:
Diagrama de vértices y aristas (no
tienen por qué ser rectilíneas)
Diagrama de regiones: suelen indicar
vecindad.
Matrices de adyacencia es una matriz
binaria (sus elementos son unos y ceros)
y cuadrada (filas y columnas representan
a los vértices). Los ceros indican que no
hay arista entre esos vértices y los unos
que sí la hay. Para nuestro ejemplo sería:
A B H
0 1 1 A
1 0 1 B
1 1 0 H
Matrices de incidencia es una matriz
binaria (sus elementos son unos y ceros).
Sus columnas representan a los vértices y
sus filas a las aristas. Los unos indican que
la arista incide en ese vértice. No tienen por
qué ser cuadradas
A B H
1 1 0 m
1 0 1 r
0 1 1 s
Rejilla de adyacencia: es una tabla de
doble entrada. En lugar de unos y ceros,
las relaciones se señalan con x. Es
siempre cuadrada, las cruces señalan
aristas
A B H
X X A
X X B
X X H
Rejilla de incidencia es una tabla de doble
entrada. En lugar de unos y ceros, las
relaciones se señalan con x. No tiene por
qué ser cuadrada, las cruces señalan vértice
y aristas incidentes.
A B H
X X m
X X r
X X s
Casi un Glosario
Es necesario que, antes de avanzar con los tipos de representaciones, nos pongamos de
acuerdo en algunas cuestiones relacionadas con los grafos.
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 4
En principio, acordemos en nombrar los vértices con letras mayúsculas y las aristas con
minúsculas.
Sobre características y denominaciones especiales de sus elementos
Un vértice y una arista se dicen incidentes si el vértice es uno de los extremos de la arista.
Dos vértices son adyacentes si son extremos de una arista.
Dos aristas son adyacentes si tienen un vértice en común.
Grado de un vértice: es el número de aristas que inciden en él.
Un vértice es aislado si su grado es cero.
Un vértice es pendiente si su grado es uno.
Arista simple: es la única unión entre un par de vértices.
Aristas múltiples: son aquellas que tienen por extremos a los mismos vértices.
Lazos: son aristas cuyos extremos coinciden en un mismo vértice.
Cadena o camino: es una sucesión de aristas adyacentes. Su longitud está dada por la
cantidad de aristas que contiene.
Ciclo: es una cadena en la que el vértice inicial coincide con el vértice final y no se repite
ningún vértice intermedio. Su longitud está dada por la cantidad de aristas que contiene.
Un ciclo es máximo cuando contiene la mayor cantidad posible de aristas y es mínimo si su
longitud es la menor posible.
Así, por ejemplo, para el siguiente grafo:
Recordá que las letras mayúsculas denotan vértices y las minúsculas, aristas.
- F y d son incidentes.
- Los vértices B y C son adyacentes.
- Las aristas a, p y q también son adyacentes.
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 5
- A tiene grado 6; B, D y E tienen grado 5; F es un vértice pendiente y G es un vértice aislado.
- a, b, c, d y e son aristas simples. - m, n y o forman una arista triple o 3-múltiple y p y q constituyen una arista doble o
2-múltiple. - t es un lazo y r y s constituyen un lazo múltiple. - La sucesión de aristas d a b es una cadena de longitud 3. - La sucesión de aristas c b p es un ciclo de longitud 3.
Sobre los tipos de grafos
Grafo vacío: es el que no tiene aristas pero sí vértices. Es decir, todos sus vértices son aislados.
Grafo sencillo: es aquél que no tiene
aristas múltiples ni lazos.
Grafo k-regular: es aquel en el que todos sus vértices tienen el mismo grado k.
Grafo completo de n vértices: es un grafo sencillo de n vértices en el que todo par de vértices determina una arista.
En los grafos completos, todos los vértices son de grado n – 1 y el número de aristas
del grafo es 2
)1n(nn
(Verificarlo con
un ejemplo).
Grafo complemento de G: es un grafo CG
tal que tiene los mismos vértices que G y sus aristas son las que le faltan a G para ser un grafo completo (que todo par de vértices determine una arista).
Grafo 2-regular
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 6
Subgrafo de G: es todo grafo S cuyos vértices y aristas están incluidas en los conjuntos de vértices y aristas de A y la aplicación φ´ de S es una restricción de la aplicación φ de G. En especial se distinguen tres tipos de subgrafos:
Fig. b. Subgrafo restante respecto de un vértice (se elimina el vértice y las aristas que en él inciden). En este ejemplo es restante respecto del vértice T.
Fig. c. Subgrafo restante respecto de una arista (se elimina la arista). En este ejemplo es restante respecto de la arista ST.
Fig.d. Subgrafo generado por un subconjunto cualquiera de V(G) con las aristas que inciden en esos vértices en G.
Grafos isomorfos: son aquellos en los
que existe correspondencia biunívoca entre sus vértices y sus aristas y además en ambos se mantiene la misma aplicación φ.
Tienen igual cantidad de vértices y de aristas y se conservan las relaciones de adyacencia entre aristas como en los grafos de las figuras de al lado.
Grafo conexo: es aquel en el que se
puede pasar de un vértice a otro cualquiera del grafo recorriendo un camino.
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 7
Grafo plano: es aquél para el que existe una representación bidimensional en el que no haya aristas que se crucen obligadamente. Un grafo aparentemente no plano tiene al menos una representación isomorfa en la que se confirma que es plano.
Grafo no plano: en estos grafos siempre hay al menos un par de aristas que se cruzan cuando se intenta una representación bidimensional.
En la fig. a se muestra el grafo de 5 vértices en el que cada uno de ellos está vinculado con los restantes. Es un grafo regular, no plano que se denomina K 5.
En la fig. b se muestra el correspondiente al problema de las tres casas y las tres utilidades. Es regular y no plano.
Ambos fueron usados por Kuratovski, matemático polaco que en 1930 enunció el teorema sobre grafos no planos.
Grafo dirigido o dígrafo: es un grafo en el que las aristas se definen por un par ordenado de vértices. Conceptualmente esto significa que la aplicación que define al grafo es un subconjunto del producto cartesiano V x V, siendo V el conjunto de vértices.
Grafo poligonal: Es un grafo plano conexo que es reunión de ciclos y tal que existe un ciclo máximo y un ciclo mínimo.
Sobre los grafos poligonales
En los grafos poligonales, el interior de cada ciclo se llama cara y se supone que la parte
infinita exterior que rodea al grafo es una cara, la cara del infinito y tiene como limitante el ciclo
máximo también llamado polígono envolvente.
En todos los grafos poligonales, es posible verificar la Fórmula de Euler:
Fig. a - K5 Fig. b - K3.3
Ciclo máximo: ABCDEA
Ciclo mínimo: ABEA
Si no existiera la arista BE, el ciclo máximo y el mínimo coincidirían.
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 8
C + V – A = 2
Donde C es el número de caras (incluyendo la del infinito); V es el número de vértices y A es
el número de aristas.
Para verificar si un grafo es poligonal se cuentan sus vértices, sus aristas y sus caras,
incluyendo la del infinito y se aplica la fórmula de Euler.
Ejemplo:
Con respecto al uso de los grafos en situaciones arquitectónicas
Imaginemos un tema cualquiera de diseño arquitectónico para el cual han sido definidos un
conjunto de lugares o áreas de uso y un conjunto de relaciones de vecindad entre pares de
esos lugares. Un conjunto de objetos y relaciones entre pares de objetos como el descrito
coincide con el concepto matemático de grafo que acabamos de ver. Los vértices
representarán lugares, y la aplicación de incidencia será la relación de vecindad señalada que
se pondrá de manifiesto en las aristas que vinculan a los vértices. Si la aplicación fuera “que
se pueda transitar entre los locales”, cada arista representaría una comunicación entre lugares
Las restricciones que pudieran hacerse como, por ejemplo, relaciones de no-vecindad entre
determinados lugares podría definir otro tipo de grafo adonde los vértices serían los mismos
pero las aristas representarían vecindades no-deseables o indeseables. Incluso podría
hablarse de vecindades indiferentes. De considerar estas tres condiciones se obtendrían tres
grafos complementarios ya que su superposición daría lugar a un grafo completo.
Aplicación de los Diagramas de vértices y de regiones
Básicamente, los grafos pueden aplicarse de dos maneras diferentes en la representación
arquitectónica sencilla:
1. Diagramas de vértices: en los cuales los vértices del grafo representan espacios o áreas
de uso y las aristas indican vínculos (por ejemplo, fronteras o comunicaciones) entre esas
áreas.
2. Diagramas de regiones: en los cuales las regiones del grafo se corresponden con
regiones del proyecto, las aristas son límites o fronteras y los vértices son puntos de
confluencia de fronteras.
Caras: C = 5
Vértices: V = 6
Aristas: A = 9
Entonces: 5 + 6 – 9 = 2
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 9
Los diagramas de vértices se corresponden aproximadamente, con los organigramas que
utilizan los arquitectos en las primeras etapas del proyecto y los diagramas de regiones no
difieren demasiado de las plantas de los edificios dibujadas con muy poca definición y algo
deformes. El diagrama de regiones de un edificio es isomorfo a su planta.
Ejemplo:
En la planta se señalan la cocina (K); el comedor (C); los dormitorios (D1 y D2), el baño (B) y el
paso (P).
Construyamos el diagrama de vértices que muestra las adyacencias y el diagrama de
regiones.
Diagrama de vértices
Los vértices representan espacios y
las aristas vecindad o adyacencia.
Este grafo es poligonal pues en él se verifica la fórmula de Euler:
C = 5 ; V = 7 ; A = 10 5 + 7 – 10 = 2
Un esquema posible para el diagrama de regiones es el siguiente:
Diagrama de regiones
Las aristas representan muros
entre los espacios, los vértices
indican confluencia de muros y las
caras representan a los espacios.
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 10
Grafos Eulerianos y Hamiltonianos
La Teoría de Grafos permite el abordaje de problemas relativos a recorridos en los que se
intenta recorrer todas las aristas de un grafo sin repetirlas o, en otros casos, conectar todos los
vértices.
Grafos eulerianos
El primero de los casos corresponde a los grafos eulerianos. Estos son grafos en los que es
posible recorrer todas las aristas de un solo trazo sin pasar más de una vez por ninguna de
ellas.
El nombre de este tipo de grafos proviene del famoso matemático Euler, quien fue el primero
en estudiarlos para resolver el siguiente problema:
Los puentes de Königsberg: La ciudad alemana de Königsberg fue famosa por sus siete
puentes sobre el río Pregel que unen las dos orillas del río con dos islas y conectaban las islas
entre sí, como muestra la figura:
Cuentan que el alcalde del lugar propuso un desafío: recorrer los siete puentes sin pasar más
de una vez por el mismo puente. Cuentan también que el desafío resultaba interesante porque
el alcalde ofreció como recompensa a quien lo lograra: la mano de su hija.
Euler enfocó el problema representando cada parte de tierra por un punto y cada puente por
una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede
trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las líneas?
Euler demostró que no era posible puesto que el
número de líneas que inciden en cada punto no es
par (condición necesaria para entrar y salir de cada
punto, y para regresar al punto de partida, por
caminos distintos en todo momento).
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 11
En teoría de grafos esta idea se corresponde con la posibilidad de encontrar un ciclo euleriano
en un grafo, llamado así en su honor ya que fue él quien demostró que encontrar este tipo de
recorridos, consistentes en pasar por todas las aristas del grafo sin repetir ninguna de ellas,
sólo es posible en dos casos:
(I) Cuando el grafo tiene todos los vértices de grado par. En este caso el grafo se denomina
grafo euleriano general y el vértice de llegada coincide con el de salida.
(II) Cuando el grafo tiene dos vértices de grado impar. En este caso el grafo se denomina
grafo euleriano restringido y el vértice de llegada y el de salida son los de grado impar.
Por lo tanto, como el grafo que representa la situación de los puentes de Königsberg tiene más
de dos vértices de grado impar, es imposible realizar el recorrido propuesto.
Seguramente, este tipo de desafíos nos resultan conocidos, aunque nunca hubieras
sospechado que su resolución estuviera relacionada con modelos matemáticos. Este tipo de
recorridos es el que deben seguir por ejemplo los camiones de la compañía de limpieza de
calles de una ciudad.
Grafos hamiltonianos
Se llaman hamiltonianos aquellos grafos en los que es posible recorrer todos sus vértices, sin
pasar más de una vez por cada uno, aunque queden aristas sin recorrer. Se llaman generales
si finaliza en el vértice inicial y restringido cuando no finaliza en el vértice inicial.
Este tipo de recorridos resulta de interés, por ejemplo, para planificar el reparto de bebidas en
comercios o para un viajante que debe recorrer distintos pueblos, entre otros casos, utilizando
recorridos mínimos, por eso la necesidad de “recorrer” cada artista sólo una vez.
Por ejemplo, en un museo grande (al estilo del Louvre sería óptimo recorrer todas las salas
una sola vez. Diseñar un recorrido así implica es buscar un ciclo hamiltoniano en el grafo que
representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre
ellas).
A veces se habla de camino o recorrido hamiltoniano a dicho recorrido.
008-00-APU-A_Grafos.doc 24/09/1515
Taller Vertical de Matemática Nº 2 “Enrich-Creus-Carnicero” Autoría y recopilación: Ing. Rosa Enrich, Arq. Gustavo Fornari, Arq. Andrea Carnicero.
FAU-UNLP 12
Recorrido hamiltoniano general: 1, 2, 3, 4, 5, 9, 8, 7, 6, 1
Recorrido hamiltoniano restringido: 1, 2, 3, 4, 5, 6, 7, 8, 9
La figura que sigue, muestra un camino o recorrido hamiltoniano en el grafo del dodecaedro
¿Qué tipo de camino es? ¿Es el único?
Bibliografía:
Biggs, N. Matemática Discreta. Vicens Vives. Madrid. 1994.
Harary, F. Teoría de Grafos. Addison –Wesley Iberoamericana. México. 1969.
Notoli, H. Grafos. Aplicación a la Arquitectura y el Diseño. Editorial de Belgrano. Buenos Aires 1997.
Spinadel, V. y otros. Notas de Matemática EUDEBA. Buenos Aires. 1995.
Recommended