Teoría de grafos

A teoría de grafos é unha rama das matemáticas e as ciencias da computación que estuda as propiedades dos grafos. Formalmente, un grafo ${\displaystyle G=(V,E)}$ é unha parella ordenada na que ${\displaystyle V}$ é un conxunto non baleiro de vértices e ${\displaystyle E}$ é un conxunto de arestas. ${\displaystyle E}$ consta de pares non ordenados de vértices, tales que se {${\displaystyle {x,y}}$}${\displaystyle \in E}$ dise entón que ${\displaystyle x}$ e ${\displaystyle y}$ son adxacentes; no grafo represéntase mediante unha liña non orientada que une os devanditos vértices. Se o grafo é dirixido chámase digrafo, denótase ${\displaystyle D}$ e entón o par ${\displaystyle (x,y)}$ é un par ordenado, e represéntase cunha frecha que vai de ${\displaystyle x}$ a ${\displaystyle y}$, e dise que ${\displaystyle (x,y)\in A}$.^[1]

Os grafos son o obxecto de estudo desta rama das matemáticas. Arriba o grafo peixe, no medio o grafo arco e abaixo o grafo dodecaedro.

A teoría de grafos ten os seus fundamentos na matemática discreta e na matemática aplicada. É unha teoría que require de diferentes conceptos de diversas áreas como combinatoria, álxebra, probabilidade, xeometría de polígonos, aritmética e topoloxía. Actualmente ten maior preponderancia no campo da informática, as ciencias da computación e as telecomunicacións. Debido á gran cantidade de aplicacións na optimización de percorridos, procesos, fluxos e algoritmos de procuras, entre outros, xerouse toda unha nova teoría que se coñece como análise de redes.^[2]

Historia

As 7 pontes do río Pregel en Königsberg.

A orixe da teoría de grafos remóntase ao século XVIII co problema das pontes de Königsberg, que consistía en atopar un camiño que percorrese as sete pontes do río Pregel na cidade de Königsberg, actualmente Kaliningrado, de modo que se percorresen todas as pontes pasando unha soa vez por cada unha delas. O traballo de Leonhard Euler sobre o problema titulado Solutio problematis ad geometriam situs pertinentis^[3] (A solución dun problema relativo á xeometría da posición) en 1736, é considerado o primeiro resultado da teoría de grafos. Tamén se considera un dos primeiros resultados topolóxicos. Este exemplo ilustra a profunda relación entre a teoría de grafos e a topoloxía.

En 1847, Gustav Kirchhoff utilizou a teoría de grafos para a análise das redes eléctricas publicando as súas leis dos circuítos para calcular a voltaxe e a corrente nos circuítos eléctricos, coñecidas como leis de Kirchhoff, consideradas a primeira aplicación da teoría de grafos a un problema de enxeñaría.

En 1852 Francis Guthrie expuxo o problema das catro cores, que afirma que é posible, utilizando soamente catro cores, colorear calquera mapa de países de tal forma que dous países veciños nunca teñan a mesma cor. Este problema, que non foi resolto até un século despois por Kenneth Appel e Wolfgang Haken en 1976, pode ser considerado como o nacemento da teoría de grafos. Ao tratar de resolvelo, os matemáticos definiron vocábulos e conceptos teóricos fundamentais dos grafos.

En 1857, Arthur Cayley estudou e resolveu o problema de enumeración dos isómeros, compostos químicos con idéntica composición (fórmula) pero diferente estrutura molecular. Para iso representou cada composto, nese caso hidrocarburos saturados C_nH_2n+2, mediante un grafo onde os vértices representan átomos e as arestas a existencia de enlaces químicos.

O vocábulo grafo, provén da expresión graphic notation usada por primeira vez por Edward Frankland^[4] e posteriormente adoptada por Alexander Crum Brown en 1884, facía referencia á representación gráfica dos enlaces entre os átomos dunha molécula.

O primeiro libro sobre teoría de grafos foi escrito por Dénes Kőnig e publicado en 1936.^[5]

Aplicacións

Grazas á teoría de grafos pódense resolver diversos problemas por exemplo a síntese de circuítos secuenciais, contadores ou sistemas de apertura. Utilízase para diferentes áreas por exemplo, debuxo computacional, en todas as áreas da enxeñaría.

Os grafos utilízanse tamén para modelar traxectos como o dunha liña de autobús a través das rúas dunha cidade, no que se poden obter camiños óptimos para o traxecto aplicando diversos algoritmos como pode ser o algoritmo de Floyd.

Para a administración de proxectos, utilízanse técnicas como a técnica de revisión e avaliación de programas (PERT) nas que se modelan os mesmos empregando grafos e optimizando os tempos para concretar os mesmos.

A teoría de grafos tamén serviu de inspiración para as ciencias sociais, en especial para desenvolver un concepto non metafórico de rede social que substitúe os nodos polos actores sociais e verifica a posición, centralidade e importancia de cada actor dentro da rede. Esta medida permite cuantificar e abstraer relacións complexas, de xeito que a estrutura social pode representarse graficamente. Por exemplo, unha rede social pode representar a estrutura de poder dentro dunha sociedade ao identificar os vínculos (arestas), a súa dirección e intensidade e dá idea da maneira en que o poder se transmite e a quen.

Emprégase en problemas de control de produción, para proxectar redes de computadores, para deseñar módulos electrónicos modernos e proxectar sistemas físicos con parámetros localizados (mecánicos, acústicos e eléctricos).

Úsase para a solución de problemas de xenética e problemas de automatización da proxección (SAPR), apoio matemático dos sistemas modernos para o procesamiento da información e aparece nas investigacións nucleares (técnica de diagramas de Feynman).^[6]

Os grafos son importantes no estudo da bioloxía e o hábitat. O vértice representa un hábitat e as arestas representan os carreiros dos animais ou as migracións. Con esta información, os científicos poden entender como isto pode cambiar ou afectar as especies no seu hábitat.

• 
  Mapas conceptuais
• 
  Plano das estacións do metro.
• 
  Plano de autoestradas.
• 
  Circuíto eléctrico
• 
  Sociograma dunha red social
• 
  Topoloxía de rede de computadores
• 
  Organigramas
• 
  Isómeros
• 
  Arquitectura de redes de telefonía móbil
• 
  Draws de eliminación directa (por exemplo no tenis)

Tipos de grafos

• Grafo simple. ou simplemente grafo é aquel que acepta unha soa aresta unindo dous vértices calquera. Isto é equivalente a dicir que unha aresta calquera é a única que une dous vértices específicos. É a definición estándar dun grafo.
• Multigrafo. É o que acepta máis dunha aresta entre dous vértices. Estas arestas chámanse múltiples ou lazos (loops en inglés). Os grafos simples son unha subclase desta categoría de grafos. Tamén se lles chama grafos xeral.
• Pseudografo. Se inclúe algún lazo.
• Grafo orientado, dirixido ou digrafo. Son grafos nos cales se engadiu unha orientación ás arestas, representada graficamente por unha frecha.
• Grafo etiquetaxe. Grafos nos cales se engadiu un peso ás arestas (xeralmente un número enteiro) ou unha etiquetaxe aos vértices.
• Grafo aleatorio. Grafo cuxas arestas están asociadas a unha probabilidade.
• Hipergrafo. Grafos nos cales as arestas teñen máis de dous extremos, é dicir, as arestas inciden en tres ou máis vértices.
• Grafo infinito. Grafos con conxunto de vértices e arestas de cardinal infinito.

Representación de grafos

Existen diferentes formas de representar un grafo (simple) e moitos métodos para almacenalos nunha computadora. A estrutura de datos usada depende das características do grafo e o algoritmo usado para manipulalo. Entre as estruturas máis sinxelas e usadas atópanse as listas e as matrices, aínda que frecuentemente se emprega unha combinación de ambas. As listas son preferidas en grafos dispersos porque teñen un uso eficiente da memoria. Doutra banda, as matrices provén acceso rápido, pero poden consumir grandes cantidades de memoria.

Estrutura de lista

• Lista de incidencia - As arestas son representadas cun vector de pares (ordenados, se o grafo é dirixido), onde cada par representa unha das arestas.^[7]
• Lista de adxacencia - Cada vértice ten unha lista de vértices os cales son adxacentes a el. Isto causa redundancia nun grafo non dirixido (xa que A existe na lista de adxacencia de B e viceversa), pero as procuras son máis rápidas, a cambio dun almacenamento extra.
• Lista de graos - Tamén chamada secuencia de graos ou sucesión gráfica dun grafo non-dirixido é unha secuencia de números, que corresponde aos graos dos vértices do grafo.

Estruturas matriciales

• Matriz de adxacencia - O grafo está representado por unha matriz cadrada M de tamaño ${\displaystyle n^{2}}$, onde ${\displaystyle n}$ é o número de vértices. Se hai unha aresta entre un vértice x e un vértice y, entón o elemento ${\displaystyle m_{x,y}}$ é 1, senón, é 0.
• Matriz de incidencia - O grafo está representado por unha matriz de A (arestas) por V (vértices), onde [vértice, aresta] contén a información da aresta (1 - conectado, 0 - non conectado)

Grafo G(V,A)	Conxuntos	Matriz de adxacencia	Matriz de incidencia	Secuencia de graos	Lista de adxacencia
	V = { 1, 2, 3, 4, 5, 6 } A = { {1,1}, {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}$	${\displaystyle {\begin{pmatrix}1&1&1&0&0&0&0&0\\0&1&0&1&1&0&0&0\\0&0&0&1&0&1&0&0\\0&0&0&0&0&1&1&1\\0&0&1&0&1&0&1&0\\0&0&0&0&0&0&0&1\\\end{pmatrix}}}$	(4,3,3,3,2,1)	{ {1,2,5}, {3,5}, {4}, {5,6} }

Notas

1. Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory (en inglés). Nova York: Springer.
2. CEPAL Charlas Sobre Sistemas Complejos Sociales (CCSSCS): Analisis de Redes1: https://www.youtube.com/watch?v=oy8YxTshZhI&list=UUQbp2yA-gyew7E_tzgOI36A & Analisis de Redes2: https://www.youtube.com/watch?v=1abtP36Wx24&list=UUQbp2yA-gyew7E_tzgOI36A; Curso completo en liña: http://www.martinhilbert.net/CCSSCS.html
3. Euler, L. "Solutio problematis ad geometriam situs pertinentis" (PDF). Commentarii Academiae Scientiarum Imperialis Petropolitanae. 128-140.
4. pag 7
5. Tutte, W.T. (2001). Graph Theory. Cambridge University Press. p. 30. ISBN 978-0-521-79489-3..
6. Gorbátov: Fundamentos de la matemática discreta
7. Ejemplo de una lista de incidencia

Véxase tamén

Wikimedia Commons ten máis contidos multimedia na categoría:  Teoría de grafos

Bibliografía

• Czumaj, A., Jansen, K., Meyer auf der Heide, F., & Schiermeyer, I. (2006). Algorithmic Graph Theory. Oberwolfach Reports, 379–460.
• Hinz, A. M. (2012). Graph theory of tower tasks. In Behavioural Neurology (Vol. 25, pp. 13–22).
• Lohmann, G., Margulies, D. S., Horstmann, A., Pleger, B., Lepsien, J., Goldhahn, D., … Turner, R. (2010). Eigenvector centrality mapping for analyzing connectivity patterns in fMRI data of the human brain. PLoS ONE, 5(4). http://doi.org/10.1371/journal.pon.0010232
• Pavlopoulos, G. a, Secrier, M., Moschopoulos, C. N., Soldatos, T. G., Kossida, S., Aerts, J., … Bagos, P. G. (2011). Using graph theory to analyze biological networks. BioData Mining, 4(1), 10. Consultado en http://www.biodatamining.org/content/4/1/10
• Rocca, M. A., Valsasina, P., Meani, A., Falini, A., Comi, G., & Filippi, M. (2014). Impaired functional integration in multiple sclerosis: a graph theory study. Brain Structure and Function, 115–131. http://doi.org/10.1007/s00429-014-0896-4

Outros artigos

• Ciclo hamiltoniano