La teoría de grafos, tamién llamada teoría de gráfiques, ye una caña de les matemátiques y les ciencies de la computación qu'estudia les propiedaes de los grafos, y que nun tienen de ser confundíos coles gráfiques que tienen una acepción bien amplia. Formalmente, un grafu ye una pareya ordenada na que ye un conxuntu non vacíu de vértices y ye un conxuntu d'arestes. Onde consta de pares ensin ordenar de vértices, tales como {} entós dicimos que y son axacentes; y [nel grafu] representar por aciu una llinia ensin empobinar qu'una dichos vértices. Si'l grafu ye empobináu llámase-y digrafo, se denota , y entós el par ye un par ordenáu, y represéntase con una flecha que va de a , y dicimos que .
La teoría de grafos tien los sos fundamentos nes matemátiques discretes y de les matemátiques aplicaes. Esta teoría que requier de distintos conceutos de diverses árees como combinatoria, álxebra, probabilidá, xeometría de polígonos, aritmética y topoloxía. Anguaño tuvo mayor influencia nel campu de la informática, les ciencies de la computación y telecomunicaciones. Por cuenta de la gran cantidá d'aplicaciones na optimización de percorríos, procesos, fluxos, algoritmos de busques, ente otros, xeneróse toa una nueva teoría que se conoz como analís de redes.CEPAL Charles Sobre Sistemes Complexos Sociales (CCSSCS): Analisis de Redes1: https://www.youtube.com/watch?v=oy8YxTshZhI&list=UUQbp2yá-gyew7Y_tzgOI36A & Analisis de Redes2: https://www.youtube.com/watch?v=1abtP36Wx24&list=UUQbp2yá-gyew7Y_tzgOI36A; Cursu completu en llinia: http://www.martinhilbert.net/CCSSCS.html
Historia thumb|Los 7 pontes del ríu Pregel en Königsberg. L'orixe de la teoría de grafos remontar al sieglu XVIII col problema de les pontes de Königsberg, que consistía n'atopar un camín que percorriera los siete pontes del ríu Pregel () na ciudá de Königsberg, anguaño Kaliningráu, de cuenta que se percorrieren toles pontes pasando una sola vegada per caúnu d'ellos. El trabayu de Leonhard Euler sobre'l problema tituláu Solutio problematis ad geometriam situs pertinentis (La solución d'un problema relativu a la xeometría de la posición) en 1736, ye consideráu la primer resultáu de la teoría de grafos. Tamién se considera unu de les primeres resultaos topolóxiques en xeometría (que nun depende de nenguna midida). Esti exemplu ilustra la fonda rellación ente la teoría de grafos y la topoloxía.
Depués, en 1847, Gustav Kirchhoff utilizó la teoría de grafos pal analís de redes llétrequiers publicando les sos lleis de los circuitos pa calcular el voltaxe y la corriente nos circuitos llétricos, conocíes como lleis de Kirchhoff, consideráu la primer aplicación de la teoría de grafos a un problema d'inxeniería.
En 1852 Francis Guthrie plantegó'l problema de los cuatro colores el cual afirma que ye posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tala forma que dos países vecinos nunca tengan el mesmu color. Esti problema, que nun foi resueltu hasta un sieglu dempués por Kenneth Appel y Wolfgang Haken en 1976, pue ser consideráu como la nacencia de la teoría de grafos. Al tratar de resolvelo, los matemáticos definieron términos y conceutos teóricos fundamentales de los grafos.
En 1857, Arthur Cayley estudió y resolvió el problema de enumeración de los isómeros, compuestos químicos con idéntica composición (fórmula) pero distintu estructura molecular. Pa ello representó cada compuestu, nesti casu hidrocarburos enchíos CnH2n+2, por aciu un grafu árbol onde los vértices representen átomos y les arestes la esistencia d'enllaces químicos.
El términu «grafu», provién de la espresión graphic notation («notación gráfica») usada per primer vegada por Edward Franklandhttp://booklens.com/l-r-foulds/graph-theory-applications páx.7 y darréu adoptada por Alexander Crum Brown en 1884, y faía referencia a la representación gráfica de los enllaces ente los átomos d'una molécula.
El primer llibru sobre teoría de grafos foi escritu por Dénes Kőnig y publicáu en 1936..
Composición d'un grafu Arestes: Son les llinies coles que se xunen los vértices d'un grafu. Arestes axacentes: 2 arestes son axacentes si converxen nel mesmu vértiz. Arestes paraleles: Son dos arista conxuntes si'l vértiz inicial y final son el mesmu. Aresta cícliques: Ye l'aresta que parte d'un vértiz pa entrar en sí mesmu. Encruz: Son 2 arestes que crucien nun mesmu puntu.
Vértices: Los vértices son los elementos que formen un grafu. Cada unu lleva acomuñada una valencia carauterística según la situación, que se correspuende cola cantidá d'arestes que conflúin en dichu vértiz.
Camín: Denominar camín d'un grafu a un conxuntu de vértices interconeutaos por arestes. Dos vértices tán coneutaos si hai un camín ente ellos.
Tipos de grafos Grafu simple: O a cencielles grafu ye aquel qu'acepta una sola aresta xuniendo dos vértices cualesquier. Esto ye equivalente a dicir qu'una aresta cualesquier ye la única que xune dos vértices específicos. Ye la definición estándar d'un grafu. Multigrafo: Ye'l qu'acepta más d'una aresta ente dos vértices. Estes arestes llámense múltiples o llazos (loops n'inglés). Los grafos simples son una subclase d'esta categoría de grafos. Tamién se-yos llama grafos xeneral. Pseudografo: Si inclúi dalgún llazu. Grafu empobináu: grafu empobináu o digrafo. Son grafos nos cualos añadióse una orientación a les arestes, representada gráficamente por una flecha. Grafu etiquetáu: Grafos nos cualos añadióse un pesu a les arestes (númberu enteru xeneralmente) o un etiquetáu a los vértices. Grafu aleatoriu: Grafu que les sos arestes tán acomuñaes a una probabilidá. Hipergrafo: Grafos nos cualos les arestes tienen más de dos estremos, esto ye, les arestes son incidentes a 3 o más vértices. Grafu infinitu: Grafos con conxuntu de vértices y arestes de cardinal infinitu. Grafu planu: Los grafos planos son aquellos que los sos vértices y arestes pueden ser representaos ensin nenguna interseición ente ellos. Podemos establecer qu'un grafu ye planu gracies al Teorema de Kuratowski. Grafu regular: Un grafu ye regular cuando tolos sos vértices tienen el mesmu grau de valencia.
Representación de grafos
Esisten distintes formes de representar un grafu (simple), amás de la xeométrica y munchos métodos p'almacenalos nun ordenador. La estructura de datos usada depende de les carauterístiques del grafu y el algoritmu usáu pa manipolialo. Ente les estructures más sencielles y usaes atópense les llistes y les matrices, anque frecuentemente úsase una combinación de dambes. Les llistes son preferíes en grafos esvalixaos porque tienen un eficiente usu de la memoria. Per otru llau, les matrices aproven accesu rápidu, pero pueden consumir grandes cantidaes de memoria.
Estructura de llista Llista d'incidencia - Les arestes son representaes con un vector de pares (ordenaos, si'l grafu ye empobináu), onde cada par representa una de les arestes.Exemplu d'una llista d'incidencia
Llista d'axacencia - Cada vértiz tien una llista de vértices los cualos son axacentes a él. Esto causa redundancia nun grafu non empobináu (yá que A esiste na llista d'axacencia de B y viceversa), pero les busques son más rápides, al costu d'almacenamientu extra.
Secuencia de graos Llista de graos - Tamién llamada secuencia de graos o socesión gráfica d'un grafu non-empobináu ye una secuencia de númberos, que correspuende a los graos de los vértices del grafu.
Estructures matriciales Matriz d'axacencia - El grafu ta representáu por una matriz cuadrada M de tamañu , onde ye'l númberu de vértices. Si hai una aresta ente un vértiz x y un vértiz y, entós l'elementu ye 1, de lo contrario, ye 0.
Matriz d'incidencia - El grafu ta representáu por una matriz d'A (arestes) por V (vértices), onde [vértiz, aresta] contién la información de l'aresta (1 - conectáu, 0 - non conectáu) Grafu G(V,A) Conxuntos Matriz d'axacenciaMatriz d'incidenciaSecuencia de graos Llista d'Axacencia150px V = { 1, 2, 3, 4, 5, 6 } A = { {1,1}, {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }(3,3,2,3,3,1){ {1,2,5}, {1,3,5}, {2,4}, {3,5,6},{1,2,4},{4} }
Problemes de teoría de grafos
Subgrafos, subgrafos inducíos y menores Un problema común, denomináu problema d'isomorfismu de subgrafos, ye atopar un grafu fixu como subgrafo d'un grafu dau. Una razón pa tar interesáu nesta cuestión ye que munches propiedaes de grafos son heredaes de subgrafos, lo que significa qu'un grafu tien una propiedá si y solu si tolos sos subgrafos de la mesma tener. Desafortunadamente, atopar subgrafos máximos d'un ciertu tipu suel ser un problema NP-completu. Por casu: Atopar el subgrafo completu más grande llámase problema de la clique.
Un problema similar ye atopar subgrafo inducíu nun grafu dau. De nuevu, delles propiedaes importantes son heredaes con al respective de subgrafos inducíos, lo que significa qu'un grafu tien una propiedá si y solu si tolos subgrafos inducíos tener. Atopar subgrafos inducíos máximos d'un determináu tipu ye, de nuevu, un problema NP-completu. Como exemplu: Atopar el subgrafo inducíu más grande ensin cantos o conxuntu independiente denominar problema del conxuntu independiente.
Otru nuevu problema ye'l problema del menor conteníu, que ye atopar un grafu fixu como menor d'un grafu dau. Un menor o subcontración d'un grafu ye cualesquier grafu llográu tomando un subgrafo y contrayendo dellos cantos. Munches propiedaes de grafos son heredaes de menores, lo que significa qu'un grafu tener namái si tolos sos menores tener tamién. Por casu, el teorema de Wagner axusta que: Un grafu ye planu si contién como menor nin el grafu bipartitu completu nin el grafu completu.
Un problema de les mesmes carauterístiques ye'l problema de la subdivisión del conteníu. Una subdivisión o homeomorfismo d'un grafu ye cualesquier grafu llográu subdividiendo dellos cantos. La subdivisión del conteníu ta rellacionada coles propiedaes de los grafos tales como la "planeza". Por casu, el teorema de Kuratowski establez que: Un grafu ye planu si contién una subdivisión nin el grafu bipartitu nin el grafu completu. Otru problema na subdivisión de conteníu ye la conxetura de Kelmans-Seymour: Cada grafu de cinco vértice coneutaos que nun ye planu contién una subdivisión del grafu completu de cinco vértice. Otru problemes de clases tienen que ver col algame pa la cual delles especies y xeneralizaciones de grafos tán determinaes poles sos subgrafos de puntos esaniciaos. Por casu, la conxetura de la reconstrucción.
Ciclos y caminos hamiltonianos
thumb|200px|Exemplu d'un ciclu Hamiltoniano. Un ciclu ye una socesión d'arestes axacentes, onde nun se percuerre dos veces la mesma aresta, y onde se torna al puntu inicial. Un ciclu hamiltoniano tien amás que percorrer tolos vértices esautamente una vegada (sacante'l vértiz del que parte y al cual llega).
Por casu, nun muséu grande (al estilu del Louvre), lo aparente sería percorrer toles sales una sola vegada, esto ye buscar un ciclu hamiltoniano nel grafu que representa'l muséu (los vértices son les sales, y les arestes los corredores o puertes ente elles).
Fálase tamién de Camín hamiltoniano si nun s'impon tornar al puntu de partida, como nun muséu con una única puerta d'entrada. Por casu, un caballu puede percorrer tolos caxellos d'un tableru d'axedrez ensin pasar dos veces pola mesma: ye un camín hamiltoniano. Exemplu d'un ciclu hamiltoniano nel grafu del dodecaedru.
Anguaño, nun se conocen métodos xenerales pa topar un ciclu hamiltoniano en tiempu polinómico, siendo la busca por fuercia bruto de tolos posibles caminos o otros métodos descomanadamente costosos. Esisten, sicasí, métodos pa refugar la esistencia de ciclos o caminos hamiltonianos en grafos pequeños.
El problema de determinar la esistencia de ciclos hamiltonianos, entra nel conxuntu de los NP-completus.
thumb|200px|Un grafu ye planu si puede dibuxase ensin cruces d'arestes. El problema de les tres cases y los trés pozos tien solución sobre'l toru, pero non nel planu.