Ver la fonte de Teoría de grafos

{{ficha xenérica}}
{{Imaxe múltiple |
 posición_tabla = right
 | direición = vertical
 | anchu = 200
 | testu = Los ''grafos'' son l'oxetu d'estudiu d'esta caña de les matemátiques. Enriba'l [[grafu pez]], en mediu'l [[grafu arcu]] y embaxo'l [[grafu dodecaedru]].
 | semeya1 = Fish graph.svg
 | semeya2 = Dart graph.svg
| semeya3 = Dodecahedral graph.neato.svg
}}

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áfica|gráfiques]] que tienen una acepción bien amplia. Formalmente, ''un grafu'' <math>G=(V,E)</math> ye una pareya ordenada na que <math>V</math> ye un conxuntu non vacíu de vértices y <math>E</math> ye un conxuntu d'arestes. Onde <math>V</math> consta de pares ensin ordenar de vértices, tales como {<math>{x,y}</math>}<math>\in E</math> entós dicimos que <math>x</math> y <math>y</math> 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 <math>D</math>, y entós el par <math>(x,y)</math> ye un par ordenáu, y represéntase con una flecha que va de <math>x</math> a <math>y</math>, y dicimos que <math>(x,y)\in E</math>.<ref>{{cita llibru |apellíos=Godsil, Chris and Royle, Gordon|nome=|enllaceautor=|títulu=Algebraic Graph Theory|url=|fechaaccesu=|añu=2001|editorial=Springer|isbn=|editor=|ubicación=New York|páxina=|idioma=|capítulu=}}</ref> 

La teoría de grafos tien los sos fundamentos nes [[matemátiques discretes]] y de les [[matemátiques aplicaes]]. Esta teoría que rique 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 [[Telecomunicación|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]].<ref>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</ref>

== Historia ==
[[Ficheru:7 bridges.svg|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 Pregolya|ríu Pregel]] ({{coord|54|42|12|N|20|30|56|E|region:RU_source:nlwiki}}) 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''<ref>{{cita publicación |autor = Euler, L. |títulu = Solutio problematis ad geometriam situs pertinentis |añu = 1736 |revista = Commentarii Academiae Scientiarum Imperialis Petropolitanae |volume = 8 |númberu = |id = 128-140 |url = http://math.dartmouth.edu/~euler/docs/originals/Y053.pdf}}</ref> (''La solución d'un problema relativu a la xeometría de la posición'') en [[1736]], ye consideráu la primer resultancia de la teoría de grafos. Tamién se considera unu de les primeres resultancies 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étriques 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 [[Teorema de los cuatro colores|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 química|fórmula]]) pero distintu [[estructura molecular]]. Pa ello representó cada [[Compuestu químicu|compuestu]], nesti casu [[hidrocarburos enchíos]] C<SUB>n</SUB>H<sub>2n+2</sub>, por aciu un grafu [[Árbol (teoría de grafos)|árbol]] onde los vértices representen [[átomu|á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 Frankland]]<ref>http://booklens.com/l-r-foulds/graph-theory-applications páx.7</ref> 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]].<ref>{{citation|last1=Tutte|first1=W.T.|authorlink=W. T. Tutte|títulu=Graph Theory |publicación=[[Cambridge University Press]]|añu=2001|isbn=978-0-521-79489-3 |páxina=30|url=https://books.google.com/books?id=uTGhooU37h4C&pg=PA30}}.</ref>

== 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 interconectaos 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'[[idioma inglés|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 ''[[Infinitu|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 ==
{{AP|Grafu (estructura de datos)}}
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 [[grafu esvalixáu|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.<ref>[//upload.wikimedia.org/wikipedia/commons/thumb/1/18/Incidence_list_2.svg/500px-Incidence_list_2.svg.png Exemplu d'una llista d'incidencia]</ref>

* '''[[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.
<!-- Nesta estructura de datos la idea ye acomuñar a cada vértiz i del grafu una llista que contenga toos aquellos vértices j que sían axacentes a él. D'esta forma namái va acutar memoria pa los arcos axacentes a i y non pa tolos posibles arcos que pudieren tener como orixe i. El grafu, por tanto, represéntase per mediu d'un vector de n componentes (si |V|=n) onde cada componente va ser una llista d'axacencia correspondiente a cada unu de los vértices del grafu. Cada elementu de la llista consta d'un campu indicando'l vértiz axacente. En casu de que'l grafu sía etiquetáu, va haber qu'añader un segundu campu p'amosar el valor de la etiqueta. -->

=== Estructures matriciales ===
* '''[[Matriz d'axacencia]]''' - El grafu ta representáu por una matriz cuadrada M de tamañu <math>n^2</math>, onde <math>n</math> 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 <math>m_{x, y}</math> ye 1, de lo contrario, ye 0.

* '''[[Matriz d'incidencia]]''' - El grafu ta representáu por una [[matriz (matemática)|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)
<center>
{| {{tablaguapa}}
! Grafu G(V,A)
! Conxuntos
! Matriz d'axacencia
!Matriz d'incidencia
!Secuencia de graos
! Llista d'Axacencia
|- 
|[[Ficheru:6n-graph2.svg|150px]]
| V = { 1, 2, 3, 4, 5, 6 }
A = { {1,1}, {1,2}, {1,5},<br /> {2,3}, {2,5}, {3,4},<br /> {4,5}, {4,6} }
|<math>\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}</math>
|<math>\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}</math>
|(3,3,2,3,3,1)
|{ {1,2,5}, {1,3,5}, {2,4}, {3,5,6},{1,2,4},{4} }
|}
</center>

== 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 ===
{{AP|Ciclu hamiltoniano}}
[[Ficheru:Hamiltonian path.svg|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-completu]]s.

[[Ficheru:Grafo ejemplo 6.png|thumb|200px|Un grafu ye '''planu''' si puede dibuxase ensin cruces d'arestes. El ''problema de los trés cases y los trés pozos'' tien solución sobre'l [[Toru (matemátiques)|toru]], pero non nel planu.]]

=== Grafos planos ===
{{AP|Grafu planu}}
Cuando un grafu o multigrafo puede dibuxase nun planu ensin que dos segmentos se corten, dizse que ye planu.

Un xuegu bien conocíu ye'l siguiente: Dibúxense trés cases y tres pozos. Tolos vecinos de les cases tienen el derechu d'utilizar los trés pozos. Como nun se lleven bien n'absolutu, nun quieren cruciase enxamás. ¿Ye posible trazar los nueve caminos que xunten los trés cases colos trés pozos ensin qu'haya cruces?

Cualquier disposición de les cases, los pozos y los caminos implica la presencia de siquier un encruz.

Sía K<sub>n</sub> el [[grafu completu]] con ''n'' vértices, K<sub>n, p</sub> ye'l [[grafu bipartitu]] de ''n'' y ''p'' vértices.

El xuegu anterior equival a afayar si'l [[grafu bipartitu completu]] K<sub>3,3</sub> ye '''planu''', esto ye, si puede dibuxase nun planu ensin qu'haya cruces, siendo la respuesta que non. Polo xeneral, puede determinase qu'un grafu ''non'' ye planu, si nel so diseñu puede atopara una estructura análoga (conocida como ''menor'') a K<sub>5</sub> o a K<sub>3,3</sub>.

Establecer qué grafos son planos nun ye obviu, y ye un problema que tien que ver con [[topoloxía]].

=== Coloración de grafos ===
{{AP|Coloración de grafos}}
Si <math>G=(V,E)</math> ye un grafu non empobináu, una coloración propia de G, asocede cuando coloreamos los vértices de G de cuenta que si {a, b} ye una aresta en G entós a y b tienen distintos colores. (Poro, los vértices axacentes tienen colores distintos). El númberu mínimu de colores necesarios pa una coloración propia de G ye'l númberu cromáticu de G y escríbese como C (G).
Sía G un grafu non empobináu sía λ el númberu de colores disponibles pa la coloración propia de los vértices de G. El nuesu oxetivu ye atopar una función polinomial P (G,λ), na variable λ, llamada <o>polinomiu cromáticu de G</o>, que nos indique'l númberu de coloraciones mesmes distintes de los vértices de G, usando un máximu de λ colores.

Descomposición de polinomios cromáticos. Si <math>G=(V,E)</math> ye un grafu conexu y y pertenez a Ε, entós: P (G,λ)=P (G+y,λ)+P (G/y,λ), onde G/y ye'l grafu llograr por [[contraición d'arestes]].

Pa cualesquier grafu G, el términu constante en P (G,λ) ye 0

Sía <math>G=(V,E)</math> con |Y|>0 entós, la suma de los coeficientes de P (G,λ) ye 0.

Sía <math>G=(V,E)</math>, con ''a'', ''b'' pertenecientes al conxuntu de vértices ''V'' pero {a, b}=y, non perteneciente a al conxuntu d'arestes Y. Escribimos G+y pal grafu que se llogra de G al añader l'aresta y={a, b}. Al identificar los vértices a y b en G, llogramos el subgrafo G++y de G.0000

==== Teorema de los cuatro colores ====
{{AP|Teorema de los cuatro colores}}
{{Imaxe múltiple |
 posición_tabla = right
 | direición = horizontal
 | anchu = 200
 | semeya2 = Grafu ejemplo 5 conecsi.png
 | testu1 = Mapa coloriáu con 4-colores.
 | semeya1 = Grafu ejemplo 5 países.png
| testu2 = [[Grafu dual]] acomuñáu al mapa con una [[Coloración de grafos|4-vértice coloración]].
}}
Otru problema famosu relativu a los grafos: ¿Cuántos colores son necesarios pa dibuxar un mapa políticu, cola condición obvia que dos países axacentes nun puedan tener el mesmu color? Supónse que los países son d'un solu cachu, y que'l mundu ye esféricu o planu. Nun mundu en forma de toroide; el teorema siguiente nun ye válidu:

Cuatro colores son siempres abondos pa colorear un mapa.

El mapa siguiente amuesa que trés colores nun basten: Si empezar pol país central '''a''' y esfórciase unu n'utilizar el menor númberu de colores, entós na corona alredor de '''a''' alternen dos colores. Llegando al país '''h''' tiense qu'introducir un cuartu color. Lo mesmo asocede en '''i''' si emplega'l mesmu métodu.

La forma precisa de cada país nun importa; lo único relevante ye saber qué país toca a qué otru. Estos datos tán incluyíos nel grafu onde los vértices son los países y les arestes conecten los que xustamente son axacentes. Entós la cuestión equival a atribuyir a cada vértiz un color distintu del de los sos vecinos.

Vimos que trés colores nun son abondos, y demostrar que con cinco siempres se llega, ye abondo fácil. Pero'l teorema de los cuatro colores nun ye nada obviu.
Prueba d'ello ye que se tuvieron qu'emplegar ordenadores p'acabar la demostración (fíxose un programa que dexó verificar un ensame de casos, lo qu'aforró bien de tiempu a los matemáticos). Foi la primer vegada que la comunidá matemática aceptó una demostración asistida por ordenador, lo que creó nel so día una ciertu discutiniu dientro de dicha comunidá.

== Carauterización de grafos ==

=== Grafu simple ===
Un grafu ye ''simple'' si a lo sumo esiste una 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.

Un grafu que nun ye simple denominar [[multigrafo]].

=== Grafos conexos ===
Un grafu ye conexu si cada par de vértices ta conectáu per un camín; esto ye, si pa cualquier par de vértices (a, b), esiste siquier un camín posible dende ''a'' escontra ''b''.

Un grafu ye doblemente conexu si cada par de vértices ta conectáu por siquier dos caminos dixuntos; esto ye, ye conexu y nun esiste un vértiz tal que al sacalo'l grafu resultante sía disconexo.

Ye posible determinar si un grafu ye conexu usando un algoritmu [[Busca n'anchor]] (BFS) o [[Busca en fondura]] (DFS).

En términos matemáticos la propiedá d'un grafu (fuertemente) conexu dexa establecer una [[rellación d'equivalencia]] pa los sos vértices, que lleva a una partición d'estos en "componentes (fuertemente) conexos", esto ye, porciones del grafu, que son (fuertemente) conexes cuando se consideren como grafos aisllaos. Esta propiedá ye importante pa munches demostraciones en teoría de grafos.
[[Ficheru:Connexe et pas connexe.svg|400px|thumb|center|Grafu conexu y non conexu]]

=== Grafos completos ===
{{AP|Grafu completo}}
Un grafu ye ''completu'' si esisten arestes xuniendo ''tolos'' pares posibles de vértices. Esto ye, tou par de vértices (a, b) tien de tener una aresta ''y'' que los xune.

El conxuntu de los grafos completos ye denomináu usualmente <math>\mathbb{K}</math>, siendo <math>\mathbb{K}_n</math> el grafu completu de ''n'' vértices.

Un <math>\mathbb{K}_n</math>, esto ye, grafu completu de <math>n</math> vértices tien esautamente <math>\frac{n(n-1)}{2}</math> arestes.

La representación gráfica de los <math>\mathbb{K}_n</math> como los vértices d'un polígonu regular da cuenta de la so peculiar estructura.

=== Grafos bipartitos ===
{{AP|Grafu bipartitu}}
Un grafu G ye bipartitu si puede espresar como <math>G = \{V_1 \cup V_2, A\}</math> (esto ye, los sos vértices son la unión de dos grupos de vértices), so les siguientes condiciones:
* <math>V_1</math> y <math>V_2</math> son dixuntos y non vacíos.
* Cada aresta d'A xune un vértiz de V<sub>1</sub> con unu de V<sub>2</sub>.
* Nun esisten arestes xuniendo dos elementos de V<sub>1</sub>; análogamente pa V<sub>2</sub>.

So estes condiciones, el grafu considérase bipartitu, y puede describise informalmente como'l grafu que xune o rellaciona dos conxuntos d'elementos distintos, como aquellos resultantes de los exercicios y puzzles nos que tien de xunise un elementu de la columna A con un elementu de la columna B.

=== Homeomorfismo de grafos ===
{{AP|Homeomorfismo de grafos}}
Dos grafos <math>G_1</math> y <math>G_2</math> son homeomorfos si dambos pueden llograse a partir del mesmu grafu con una socesión de [[subdivisiones elementales]] d'arestes.

=== Árboles ===
{{AP|Árbol (teoría de grafos)}}
[[Ficheru:Grafo ejemplo 3 árbol.png|thumb|263px|Exemplu d'árbol.]]
Un grafu que nun tien ciclos y que coneuta a tolos puntos, llámase un '''árbol'''. Nun grafu con '''n''' vértices, los árboles tienen esautamente '''n - 1''' arestes, y hai '''n<sup>n-2</sup>''' árboles posibles. La so importancia anicia en que los árboles son grafos que conecten tolos vértices utilizando'l menor númberu posible d'arestes. Un importante campu d'aplicación del so estudiu atopar nel [[analís filoxenéticu]], el de la filiación d'entidaes que deriven unes d'otres nun procesu evolutivu, que s'aplica sobremanera a l'averiguación del parentescu ente especies; anque s'usó tamién, por casu, nel estudiu del parentescu ente llingües.

=== Grafos ponderaos o etiquetaos ===
En munchos casos, ye precisu atribuyir a cada aresta un númberu específicu, llamáu ''valuación'', ''ponderación'' o ''costu'' según el contestu, y llógrase asina un '''grafu valuáu'''.<br />
Formalmente, ye un grafu con una función v: A → '''R<sub>+</sub>'''.

Por casu, un representante comercial tien que visitar ''n'' ciudaes coneutaes ente sigo per carreteres; el so interés previsible va ser embrivir la distancia percorrida (o'l tiempu, si pueden prevese atascos). El grafu correspondiente va tener como vértices les ciudaes, como arestes les carreteres y la valuación va ser la distancia ente elles.<br />
Y, pel momento, nun se conocen métodos xenerales pa topar un ciclu de valuación mínima, pero sí pa los caminos dende ''a'' hasta ''b'', ensin más condición.

=== Diámetru ===
[[Ficheru:Grafo ejemplo 7.png|thumb|263px|Na figura nótase que K<sub>4</sub> ye planu (esviando l'aresta ''ab'' al esterior del cuadráu), que K<sub>5</sub> nun lo ye, y que K<sub>3</sub>,<sub>2</sub> ser tamién (esviadures en gris).]]
Nun grafu, la distancia ente dos vértices ye'l menor númberu d'arestes d'un percorríu ente ellos. El '''diámetru''', nuna figura como nun grafu, ye la mayor distancia d'ente tolos pares de puntos de la mesma.

El diámetru de los K<sub>n</sub> ye 1, y el de los K<sub>n</sub>,<sub>p</sub> ye 2. Un diámetru infinitu puede significar que'l grafu tien una infinidá de vértices o a cencielles que nun ye '''conexu'''. Tamién puede considerase el '''diámetru permediu''', como'l permediu de les distancies ente dos vértices.

Una aplicación d'esti conceutu ye la hipótesis conocida como los [[seis graos de separación]], que plantega que, si cada unu de los habitantes de la Tierra representar por un vértiz y dos persones tán coneutaes por una aresta si conócense personalmente, la distancia ente dos persones escoyíes al azar ente tolos habitantes de la Tierra ye de seis arista o menos.

El mundu d'Internet punxo de moda esa idea del diámetru: Si refugamos los sitios que nun tienen enllaces, y escoyemos dos páxina ''web'' al [[azar]]: ¿En cuántos ''clics'' puede pasase de la primera a la segunda? La resultancia ye'l diámetru de la Rede, vista como un grafu que los sos vértices son los sitios, y que les sos arestes son lóxicamente los enllaces.

Esti conceutu reflexa meyor la complexidá d'una rede que'l númberu de los sos elementos.

{{VT|Glosariu en teoría de grafos}}

== Aplicaciones ==
Gracies a la teoría de grafos pueden resolvese diversos problemes como por casu la síntesis de [[circuitu|circuitos]] secuenciales, contadores o sistemes d'apertura. Utilizar pa distintes árees por casu, Dibuxu computacional, en toa les árees d'Inxeniería.

Los grafos utilícense tamién pa modelar trayectos como'l d'una llinia d'autobús al traviés de les cais d'una ciudá, nel que podemos llograr caminos óptimos pal trayeutu aplicando diversos [[algoritmu|algoritmos]] como pue ser l'algoritmu de [[Robert W. Floyd|Floyd]].

Pa l'alministración de proyeutos, utilizamos téuniques como [[téunica de revisión y evaluación de programes]] (PERT) nes que se modelen los mesmos utilizando grafos y optimizando los tiempos pa concretar los mesmos.

Una importante aplicación de la teoría de grafos ye nel campu de la informática, yá que sirvió pal resolución d'importantes y complexos algoritmos. Un claru exemplu ye l'[[Algoritmu de Dijkstra]], utilizáu pa la determinación del camín más curtiu nel percorríu d'un grafu con determinaos pesos nos sos vértices.

Dientro d'esti campu, un grafu ye consideráu un tipu de datu astractu [[TAD]].

El científicu d'Estaos Xuníos Donald Knuth estableció los grafos planos como base de determinaos estudios y descubrimientos realizaos por él.

Per otra parte, destaca'l [[Algoritmu de Kruskal]], que déxanos buscar un subconxuntu d'arestes qu'inclúi tolos vértices, estableciendo a lo menos el valor de les arestes.

La teoría de grafos tamién sirvió d'inspiración pa les ciencies sociales, cuantimás pa desenvolver un conceutu non metafóricu de [[rede social]] que sustitúi los nodos polos actores sociales y verifica la posición, centralidad ya importancia de cada actor dientro de la rede. Esta midida dexa cuantificar y abstraer rellaciones complexes, de manera que la estructura social puede representase gráficamente. Por casu, una rede social puede representar la estructura de poder dientro d'una sociedá al identificar los venceyos (arestes), la so direición ya intensidá y da idea de la manera en que'l poder tresmítese y a quién.

Emplegar en problemes de control de producción, pa proyeutar redes d'ordenadores, pa diseñar módulos electrónicos modernos y proyeutar sistemes físicos con parámetros alcontraos (mecánicos, acústicos y llétricos).

Usar pa la solución de problemes de xenética y problemes d'automatización de la proyeición (SAPR). Sofitu matemáticu de los sistemes modernos pal procesamientu de la información. Allega nes investigaciones nucleares (téunica de diagrames de Feynman).<ref>Gorbátov:«Fundamentos de la matemática discreta»</ref>

Los grafos son importantes nel estudiu de la [[bioloxía]] y hábitat. El vértiz representa un hábitat y les arestes (o "edges" n'inglés) representa los senderos de los animales o les migraciones. Con esta información, los científicos pueden entender cómo esto puede camudar o afectar a les especies nel so hábitat.
<center>
<gallery>
Ficheru:Diagrama Conceptual ejemplo.png|[[Mapa conceptual|Mapes conceptuales]]
Ficheru:Madrid Metro Map.svg|Planu d'estaciones del [[Metro (sistema de tresporte)|metro]].
Ficheru:West Midlands UK location map.svg|Planu d'[[autopista|autopistes]].
Ficheru:CircuitoDosMallas.png|[[Circuitu llétricu]]
Ficheru:Social-network.svg|[[Sociograma]] d'una [[rede social]]
Ficheru:Fully topology.png|[[Topoloxía de rede]] d'[[Ordenador electrónicu|ordenador]]es Ficheru:Ministry
Ministry of Defence Guatemala organisation chart.svg|[[Organigrama|Organigrames]]
Ficheru:Monocrotophos isomers.png|[[Isomeros]]
Ficheru:Gsm network architecture.png|[[Rede de celdes|Arquiteutura de redes]] de [[telefonía móvil]]
Ficheru:Mitbat-2007-bracket-large.png|Draws d'[[eliminación direuta]] (ej: [[tenis]])
</gallery></center>

Ente les aplicaciones de la Teoría de gráfiques que se volvieron importantes na actualidá podemos atopar l'estudiu de les redes sociales, que la so importancia anicia nel fayadizu almacenamientu de datos, yá que el costu del tiempu de busca de la información de cada miembru que pertenez a esta rede puede tornase demasiáu altu debíu al númberu d'usuarios. Por casu, el númberu d'usuarios qu'hai anguaño nuna importante rede social tan solo en Méxicu ye de 49 millones -cifra reportada pol periódicu L'economista en 2014-, si esti númberu multiplicar por 194 que ye'l númberu averáu de países qu'hai nel mundu, percíbese la posibilidá d'un grave problema d'almacenamientu pa los servidores qu'hai destinaos pa ello y pa la busca d'información. Este mesmu fenómenu pasa n'otres redes de fotografíes, mensaxes, etc. El modeláu d'esti tipu de problemes foi encetáu principalmente por estudiantes de doctoráu d'universidaes como Stanford, Massachusetts Institute of Technology (MIT), Berkeley, Oxford, Rice y tamién pola NASA; en Méxicu, tantu l'Institutu Politéunicu Nacional (IPN) como la Universidá Nacional Autónoma de Méxicu (UNAM) son los principales promotores nestes árees al traviés de los grupos académicos de combinatoria y de computación científica. Podemos considerar qu'esti tipu de problemes son trataos por espertos en matemátiques y ciencies de la computación, por cuenta del so altu grau de complexidá.

El celebru humanu ye una rede complexa que interactúa en rexones coneutaes por tractos de sustancia blanco. La carauterización de carauterístiques estructurales y funcionales d'una rede tal en suxetos sanos y persones enfermes tien la posibilidá d'ameyorar la nuesa comprensión de la fisiopatoloxía y les manifestaciones neurolóxiques y condiciones psiquiátriques. Esto llevó al usu de nueves ferramientes pal analís de sistemes complexos pa faer frente enfermedaes cerebrales. Ente estos, la teoría de grafos ye un marcu matemáticu que dexa describir una rede en forma d'una gráfica, que consiste nuna coleición de los nodos (esto ye, rexones del celebru) y los cantos (esto ye, estructurales y conexones funcionales) .L'usu de la teoría de grafos, distintu cambeos de la topoloxía de red cerebro fueron identificaos mientres el desenvolvimientu y l'avieyamientu normal, y rompiéronse conectividades funcionales y estructurales fueron acomuñáu con dellos trestornos neurolóxicu y psiquiátricu, incluyendo llocura, esclerosis llateral amiotrófica, y l'esquizofrenia. Nesti últimu enfoque contribuyóse a probar la teoría d'esta condición como un síndrome de desconexón. Na esclerosis múltiple (MS), l'escurrimientu de la desconexón foi acotada por estudios de resonancia magnética estructural de topoloxía de la rede cerebral qu'amosó un amenorgamientu de la conectividad estructural de les rexones de los lóbulos fronto-temporal.

Otra aplicación de les gráfiques consiste en tomar datos de resonancia magnética del celebru adquiríos en condición ausente ( '' estáu de reposu '') riquen nuevos analises de datos téuniques que nun dependen d'un modelu d'activación, una alternativa son los métodos llibre de parámetru sobre la base d'una forma particular de la centralidad del vector propiu asociáu a un nodo llamáu de centralidad; la centralidad del vector propiu asigna atributos d'un valor a cada voxel nel celebru de manera que un voxel recibe un valor grande si ta fuertemente correlacionada con munchos otros nodos que son centrales dientro de la rede; l'algoritmu PageRank de Google ye una variante del vector propiu centralidad el cual ye utilizáu nes busques que s'efectúen n'internet. Hasta'l momentu, otres midíes de centralidad - en particular '' centralidad d'intermediación '' - aplicáronse a datos de la fMRI usando un conxuntu pre-escoyíu de nodos que consisten en dellos cientos d'elementos. Centralidad del Vector Propiu ye computacionalmente muncho más eficiente que centralidad d'intermediación y nun riquir d'estragales de valores de semeyanza de cuenta que puede aplicase a miles de voxels nuna rexón d'interés que cubren la totalidá del celebru que sería invidable l'usu de centralidad d'intermediación. Centralidad del Vector Propiu puede utilizase nuna variedá de distintes midíes de semeyanza. (Lohmann et al., 2010).
“La teoría de redes complexes xuega un papel importante nuna amplia variedá de disciplines, que van
dende la informática, socioloxía, inxeniería y física, pa molecular
y la bioloxía de la población. Dientro de los campos de la bioloxía y la medicina, el potencial d'aplicaciones
d'analises de redes inclúin, por casu, la identificación oxetivu de drogues, determinando una función del xen de la proteína, o diseñar estratexes eficaces pal tratamientu de diverses enfermedaes o apurrir el diagnósticu precoz de trestornos. “ (Pavlopoulos et al., 2011)
La teoría de gráfiques, ye afecha por que los informáticos modelen problemes, pero tamién ye afechu pa los matemáticos que tienen interés na complexidá computacional. La mayoría de los conceutos clásicos de la teoría de grafos teórica y aplicada (árboles d'espansión, conectividad, xéneru, colorabilidad, flúi nes redes, los apareyamientos y percorríos). Usar na solución de problemes.(Czumaj, Jansen, Meyer auf der Heide, & Schiermeyer, 2006)

== Algoritmos importantes ==
{{columns-list|3|
* [[Busca n'anchura|Algoritmo de busca n'anchor (BFS)]]
* [[Busca en profundidad|Algoritmo de busca en fondura (DFS)]]
* [[Algoritmu de busca A*]]
* [[Algoritmu del vecín más cercanu]]
* [[Ordenación topolóxica|Ordenación topolóxica d'un grafu]]
* [[Algoritmu de cálculu de los componentes fuertemente conexos d'un grafu]]
* [[Algoritmu de Dijkstra]]
* [[Algoritmu de Bellman-Ford]]
* [[Algoritmu de Prim]]
* [[Algoritmu de Ford-Fulkerson]]
* [[Algoritmu de Kruskal]]
* [[Algoritmu de Floyd-Warshall]]
}}

== Investigadores relevantes en teoría de grafos ==
{{llista de columnes|3|
* [[Noga Alon|Alon, Noga]]
* [[Claude Berge|Berge, Claude]]
* [[Béla Bollobás|Bollobás, Béla]]
* [[Graham Brightwell|Brightwell, Graham]]
* [[Fan Chung|Chung, Fan]]
* [[Gabriel Andrew Dirac|Dirac, Gabriel Andrew]]
* [[Edsger Dijkstra|Dijkstra, Edsger]]
* [[Jack Edmonds|Edmonds, Jack]]
* [[Paul Erdős|Erdős, Paul]]
* [[Leonhard Euler|Euler, Leonhard]]
* [[Ralph Faudree|Faudree, Ralph]]
* [[Martin Charles Golumbic|Golumbic, Martin]]
* [[Ronald Graham|Graham, Ronald]]
* [[Frank Harary|Harary, Frank]]
* [[Percy John Heawood|Heawood, Percy John]]

* * [[Dénes Kőnig|Kőnig, Dénes]]
* [[Kazimierz Kuratowski|Kuratowski, Kazimierz]]
* [[László Lovász|Lovász, László]]
* [[Jaroslav Nešetřil|Nešetřil, Jaroslav]]
* [[Alfréd Rényi|Rényi, Alfréd]]
* [[Gerhard Ringel|Ringel, Gerhard]]
* [[Neil Robertson (mathematician)|Robertson, Neil]]
* [[Paul Seymour (mathematician)|Seymour, Paul]]
* [[Endre Szemerédi|Szemerédi, Endre]]
* [[Robin Thomas (mathematician)|Thomas, Robin]]
* [[Carsten Thomassen|Thomassen, Carsten]]
* [[Pál Turán|Turán, Pál]]
* [[W. T. Tutte|Tutte, W. T.]]
* [[Hassler Whitney|Whitney, Hassler]]
}}

== Ver tamién ==
* [[Grafu]]
* [[Galería de grafos]]
* [[Teorema de König (teoría de grafos)]]

== Referencies ==
{{llistaref}}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, páxs. 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). <nowiki>http://doi.org/10.1371/journal.pone.0010232</nowiki>

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. Retrieved from <nowiki>http://www.biodatamining.org/content/4/1/10</nowiki>

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. <nowiki>http://doi.org/10.1007/s00429-014-0896-4</nowiki>

== Enllaces esternos ==
{{commonscat|Graph theory}}
* [http://sedici.unlp.edu.ar/handle/10915/36487 Sobre los grafos VPT y los grafos EPT]. Mazzoleni, María Pía. 30 de mayu de 2014.
{{EL}}

{{Tradubot|Teoría de grafos}}

[[htp://en.wikipedia.org/wiki/Walter_Kaufmann_(philosopher)|Kaufmann, Walter Arnold]]

{{control d'autoridaes}}
[[Categoría:Teoría de grafos]]