Teoría de grafos

Fish graph.svg
Dart graph.svg
Dodecahedral graph.neato.svg
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 é 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 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]

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 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]

Other Languages
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論