Type a search term to find related articles by LIMS subject matter experts gathered from the most trusted and dynamic collaboration tools in the laboratory informatics industry.
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 é unha parella ordenada na que é un conxunto non baleiro de vértices (ou nós) e é un conxunto de arestas. consta de pares non ordenados de vértices, tales que se {} dise entón que e 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 e entón o par é un par ordenado, e represéntase cunha frecha que vai de a , e dise que .[1]
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]
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 CnH2n+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]
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.
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.
| 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} } |
(4,3,3,3,2,1) | { {1,2,5}, {3,5}, {4}, {5,6} } |
LIMS forum content by LIMS forum members is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Based on a work at www.limsforum.com.
