cyanic-selkie/wikianc huggingface dataset:
Niceto Alcalá-Zamora
La proclamación de la República y el Gobiernu Provisional
El 15 d'abril de 1931, el nuevu Gobiernu republicanu fixo públicu un programa d'actuación basáu nos alcuerdos del Pactu de San Sebastián. Foi anunciada una reforma agraria, llibertá de cultos y creencies, respetu a la propiedá privada, responsabilidaes a los collaboradores de la dictadura, aumentu gradual de les llibertaes individual y sindical, etc.
Apenes aportó al poder, el Gobiernu tuvo qu'enfrentase a la proclamación de la República Catalana y a los sucesos anticlericales del mes de mayu d'esi mesmu añu. Tamién hubo munches dificultaes coles organizaciones anarquistes, que negaron la so collaboración cola nueva República ya inclusive s'enfrentaron abiertamente a ella. thumb|right|Alcalá-Zamora en 1931 El Gobiernu foise inclinando escontra la esquierda, representáu nel republicanismu de Manuel Azaña, postura que claramente se reflexó na redaición de la Constitución de 1931, convocando eleiciones el 28 de xunu. La cuestión clerical enfrentó de nuevu a republicanos conservadores ya izquierdistes, socialistes y radicales, y finalmente tantu Alcalá-Zamora como Maura abandonaron el gobiernu'l 14 d'ochobre de 1931.
Presidente de la República
Tarreciendo que Alcalá-Zamora entamara una campaña revisionista y de desprestixu contra la República, los socialistes y los azañistas convinieron n'ufierta-y la presidencia de la República, cargu pal cual foi escoyíu candidatu únicu'l 2 d'avientu. Xuró'l cargu'l 11 d'avientu de 1931.
La idea del presidente de la República yera incorporar a la direición d'España les nueves fuercies surdíes dempués de la Restauración y conteníes polos postreros Borbones. Esta apertura tenía de faese dende enriba, suprimiendo tou lo que torgara esti pasu y estableciendo les premises esenciales d'un nuevu orde pela vía pacífica y parllamentaria.
Los problemes con Azaña
Les rellaciones col Gobiernu yeren trémboles. Cuando Azaña presentó-y pa la so ratificación la llei de Congregaciones (llei de secularización de la enseñanza) y la llei del Tribunal de Garantíes Constitucionales, que completaben la Constitución republicana de 1931, Alcalá-Zamora aguantar al máximu a roblar dambes lleis, pero nun s'atrevió a vetales. La oposición acusó a Alcalá-Zamora de morosidá.
Más tarde, con ocasión d'un reaxuste gubernamental, les diferencies volvieron surdir y Azaña dimitió col so gabinete. Tres delles consultes fallíes, Alcalá-Zamora volvió nomar como presidente del Conseyu de Ministros a Azaña (12 de xunu), fechu que decepcionó a los conservadores.
Meses más tarde, en setiembre, Azaña dimitió. Alcalá-Zamora eslleió les Cortes Constituyentes y, dempués d'un fugaz mandatu del radical Alejandro Lerroux, encargó-y al tamién radical Diego Martínez Barrio la celebración de nueves eleiciones pal 8 d'ochobre de 1933.
El bieniu radical-cedista
Les fuercies derechiegues ganaron llargamente les eleiciones del 29 de payares de 1933, les primeres de la Historia d'España nes que pudieron votar les muyeres. Alejandro Lerroux formó gobiernu per encargu del presidente y cola avenida de la Confederación Española de Dereches Autónomes (CEDA), dirixida por José María Gil-Robles. Alcalá-Zamora llevóse mal colos radicales y sobremanera con DEXAR, yá que resabiaba del espíritu democráticu del partíu de Gil-Robles, que, magar se declaraba respetuosu col orde establecíu, nun xurara llealtá a la República. Por esta razón buscó siempres soluciones de compromisu, como'l confusu gobiernu del radical Ricardo Samper, que nun gustaron a naide.
thumb|180px|Estandarte presidencial de Niceto Alcalá-Zamora. N'ochobre tuvo que volver recurrir a Lerroux, que formó gobiernu con tres ministros de DEXAR, pero'l llevantamientu independentista del 6 d'ochobre de 1934 en Barcelona, la revolución d'Asturies, la so indecisión y l'escándalu del «estraperlu» torgaron una aición de gobiernu coherente.
Per otra parte, Alcalá-Zamora utilizó tolos sos recursos pa estremar a DEXAR del poder hasta que la crisis de gobiernu del 9 de payares de 1935 ufiertó-y esta oportunidá. Nomó primer ministru al so amigu Manuel Portela Valladares, que presidió un interregno ente payares de 1935 y febreru de 1936. La so intención yera crear una fuercia de centru ente la derecha radical-cedista y l'esquierda social azañista.
Destitución
El Frente Popular ganó les eleiciones de febreru de 1936. Si esto yera una derrota pa la derecha, tamién lo yera pa Alcalá-Zamora y les sos aspiraciones. Azaña foi l'encargáu de formar gobiernu.
Los republicanos d'izquierdes nun escaecieren l'actitú de Alcalá-Zamora dende xunu de 1933. Abrióse un alderique nes Cortes sobre la inconstitucionalidá de la última disolución de les mesmes, yá que según la Constitución de 1931, el presidente taba facultáu pa eslleir cortar dos veces, pero la segunda disolución podía ser sometida al enxuiciamientu de la Cámara, y si una mayoría consideraba que se cometiera dalguna irregularidá, el presidente podría ser destituyíu.
El discutiniu produzse cuando la nueva mayoría de les Cortes, considerando qu'ésta yera la segunda disolución, enxuicien l'actuación del presidente y dictaminen que la disolución produxérase con muncho retrasu, polo que'l presidente tenía de ser destituyíu. Sicasí, había quien cuntaba que ésta yera la primer disolución, una y bones l'anterior (la de 1933) nun tenía de cuntar se al tratase de les Cortes Constituyentes, les qu'ellaboraron la Constitución y por tantu yeren anteriores a ella. Finalmente, el 7 d'abril de 1936, 238 diputaos votaron a favor de la destitución por namái 5 en contra. 174 diputaos abandonaron la cámara o s'atopaben ausentes, polo que'l Presidente foi destituyíu (riquíase mayoría absoluta de los 417 diputaos n'exerciciu, esto ye, 209). Ésti en principiu aguantóse, pero abandonáu por toos tuvo qu'almitir el cese.
Dempués d'unes selmanes nes que se fixo cargu de la Xefatura del Estáu de forma interina Diego Martínez Barrio, na so calidá de presidente de les Cortes, foi sustituyíu por Manuel Azaña el 11 de mayu de 1936.
Guerra y exiliu
L'entamu de la Guerra Civil Española sosprendió-y nun viaxe por Noruega. Decidió nun tornar a España cuando s'enteró, según cuenta nes sos memories, reescritas mientres l'exiliu, de que milicianos del Frente Popular entraren illegalmente na so casa, robándo-y les sos pertenencies y escaláu coles mesmes la so caxa de seguridá (y siquier, otra propiedá d'una de les sos fíes) nel bancu Crédit Lyonnais de Madrid, llevándose'l manuscritu de les sos memories, parte del cual foi publicáu (con cortes de la censura) na prensa republicana mientres la guerra y llargamente comentáu por Manuel Azaña nes sos Memories. Afitó la so residencia en Francia, onde-y sosprendió la Segunda Guerra Mundial.
Dempués de múltiples penalidaes, por cuenta de la ocupación alemana y a l'actitú collaboracionista del Gobiernu de Vichy, salió de Francia y tres un viaxe tresatlánticu de 41 díes en barcu llegó a Arxentina en xineru de 1942, onde vivió de los sos llibros, artículos y conferencies hasta la so muerte. Esta produció'l 18 de febreru de 1949 en Buenos Aires.
Nun quixo volver a España mientres la dictadura franquista, anque, al paecer, fíxose-y dalguna ufierta, una y bones un fíu so taba casáu con una fía del xeneral Queipo de Llano, unu de los protagonistes de la sulevación y a que Niceto Alcalá-Zamora, a pesar de los sos convencimientos republicanos, yera un home de fondes creencies católiques. El so cadabre foi repatriáu a España en 1979 y soterráu nel campusantu de l'Almudena de Madrid.
A mediaos d'avientu de 2008 unos 1200 documentos históricos fueron recuperaos pola Guardia Civil. Ente ellos taben les memories manuscrites del presidente, según cartes y diversos papeles que-y fueron sustraíos en febreru de 1937.
Los diarios
thumb|right|140px|Armes familiares de Niceto Alcalá-Zamora. Un empresariu anónimu ufiertó en venta los pervalibles documentos al escritor César Vidal, quien se punxo en contautu col historiador Jorge Fernández-Coppel, y col Grupu de Patrimoniu de la Guardia Civil, por que'l so colega axuntar col empresariu en Valencia y, asina, pudiera ser prindada la documentación por aciu la intervención d'un axente de incógnito conocida como la Operación Llión.
Los herederos decidieron entamar un procesu que remate cola recuperación de los documentos, tal como manifestó'l so nietu l'historiador y miembru de la Real Academia de la Historia, José Alcalá-Zamora y Queipo de Llano, quien considera necesariu faer públicu'l documentu que más lluz puede refundiar sobre la historia d'España d'aquellos convulsos años. Solamente conociendo los escritos robaos, “podrá faese xusticia al respective de la significación histórica del presidente de la República”.
La publicación de la primer parte de los diarios produz el 15 de payares de 2011, na editorial La esfera de los llibros col títulu Asaltu a la República. Con edición de Jorge Fernández-Coppel, prólogu de Juan Pablo Fusi y epílogu de José Alcalá-Zamora, nesti llibru inclúyense amás numberoses cartes inédites y documentos que ponen en xaque ciertos episodios, como les actes de los votos llograos polos distintos grupos nes eleiciones a Cortes del 16 de febreru de 1936, que demuestren cómo se texó lo que podría calificase de "golpe d'Estáu parllamentariu". "Los documentos robaos al presidente Niceto Alcalá-Zamora mientres la guerra prueben la so negativa a secundar un golpe d'Estáu y el so distanciamientu de Azaña".
Enllaces esternos
{{Socesión de la República Española]] {{Renglóndoble|Juan Bautista Aznar-Cabanes|Presidente del Conseyu de Ministros socesor3 = Manuel Azaña }}
{{NF|1877|1949|Alcala-Zamora Torres, Niceto}}
Teorema de los cuatro colores
thumb|Exemplu de mapa coloriáu con cuatro colores thumb|Mapa del mundu coloriáu de verde, naranxa, azul y moráu
En teoría de grafos, el teorema de los cuatro colores (o teorema de la minimalidad cromática) ye un teorema sobre la coloración de grafos qu'establez lo siguiente:
Trés colores son abondos pa mapes simples, pero en dellos casos ye necesariu un cuartu color adicional, esto ye, cuando una rexón a colorear queda zarrada por un númberu impar de rexones que se toquen formando un ciclu. El teorema de los cinco colores, que la so demostración ye curtia y elemental, establez que cinco colores son abondos pa colorear un mapa y foi probáu nel sieglu XIX por Heawood. Una serie de pruebes falses y falsos contraejemplos apaecieron dende'l primer enunciáu del teorema de los cuatro colores en 1852.
El problema del mapa de cuatro colores foi plantegáu, per primer vegada, pol estudiante Francis Guthrie en 1852, lo que foi comunicáu a Augustus de Morgan. La conxetura fíxose famosa cola declaración d'Arthur Cayley, en 1878, nel sentíu de que la encetara. Foi resueltu, a mediaos de 1970, por Kenneth Appel y Wolfgang Haken.
Formulación precisa del teorema
De primeres, toles esquines y puntos de mancomún que pertenecen a trés o más países, tienen de ser inoraes. Ensin esta restricción, los mapes estraños (utilizando les rexones del área finita pero perímetru infinitu) pueden riquir más de cuatro colores. De segundes, pal propósitu del teorema cada "país" tien que ser una rexón a cencielles conexa o continua. Nel mundu real, esto nun ye ciertu (por casu, Alaska como parte de los Estaos Xuníos, Nakhchivan como parte d'Azerbaixán, y Kaliningráu como parte de Rusia nun son rexones continues). Por cuenta de que el territoriu d'un país en particular tien de ser del mesmu color, si dexárense "países" non continuos, cuatro colores podríen nun ser abondos. Por casu, considérese un mapa simplificáu: Nesti mapa, los dos rexones A pertenecen a un mesmu país, y poro, tienen de ser del mesmu color. Arriendes d'ello, esti mapa rique cinco colores, yá que los dos rexones A son allegantes coles otres cuatro rexones, y cada una d'estes rexones son allegantes ente sigo. Si hai tres rexones A, entós precísense seis o más colores; pueden construyise mapes que riquen un númberu arbitrariamente alzáu de colores. Un escenariu similar tamién puede dase si'l color azul acutar pa l'agua. 400px|thumb|Mapa y [[grafo dual acomuñáu]] Una versión más simple del teorema utiliza la teoría de grafos. El conxuntu de les rexones d'un mapa puede representase de manera más astracta como un grafo simple non empobináu acomuñando un vértiz pa cada rexón y una aresta pa cada par de rexones que comparten un segmentu de cantu. Esta representación del mapa con vértices y arestes ye un grafo dual y el problema de colorear países camudar pola coloración del grafo. Esti grafo ye planu, esto ye, que puede dibuxase nel planu ensin encruz d'arestes por aciu l'allugamientu de cada vértiz nun llugar escoyíu arbitrariamente dientro de la rexón a la que correspuende. Cola terminoloxía de la teoría de grafos, el teorema de cuatro colores establez que:
Esto ye, los vértices de cada grafo planu pueden ser coloriaos con un máximu de cuatro colores de cuenta que nun esistan dos vértices axacentes col mesmu color. χ(G) correspuende al númberu cromáticu.
Historia
El teorema de los cuatro colores surdió como conxetura. En 1852, Francis Guthrie yera un estudiante de Augustus De Morgan y formuló esa conxetura, que nun pudo ser probada por Guthrie, nin pol so hermanu Frederick, que fuera tamién estudiante de De Morgan, nin por sir William Rowan Hamilton, a quien De Morgan escribiólu formulando la conxetura.
En 1879 Alfred Bray Kempe anunció na revista Nature que tenía una demostración pa la conxetura. En 1890, Percy John Heawood atopó un error na demostración de Kempe. Heawood nun pudo demostrar que la conxetura nun yera válida, pero siguió trabayando nel coloreo de mapes, pudiendo probar que con cinco colores podíase colorear cualquier mapa.
En 1976 la conxetura tuvo demostración, gracies a Kenneth Appel y Wolfgang Haken, qu'utilizaron un ordenador pa la demostración, lo cual xeneró múltiples discutinios nel ambiente matemático.
La polémica demostración
El teorema de cuatro colores foi demostráu cola ayuda d'un ordenador. Sicasí, la demostración nun ye aceptada por tolos matemáticos yá que sería impracticable pol so gran cantidá de detalles, de manera que una persona veríase imposibilitada pa verificalo manualmente. Solo queda aceptar la exactitú del programa, del compilador y del ordenador nel cual executóse la prueba.
Na actualidá realizó otra demostración, tamién faciendo usu de cálculos per ordenador, lo cual verifica la prueba orixinal; pero sigue ensin esistir una demostración matemática.
Resume de les idees de la demostración
El siguiente resume ta basáu nel llibru Every Planar Map is Four Colorable de Appel y Haken publicáu en 1989. Anque la prueba del teorema de los cuatro colores dada por Kempe contenía un fallu, apurrió dalgunes de les ferramientes básiques utilizaes darréu pa demostralo. La esplicación que se da equí reformulóse utilizando términos modernos de la teoría de grafos.
L'argumentu de Kempe ye'l siguiente. De primeres, si'l grafo tien rexones o cares planes non triangulares, esto ye, nun tienen tres arista como fronteres, pueden amestase arestes al grafo (ensin introducir nuevos vértices) de manera que cada rexón del grafo sía triangular, incluyida la rexón esterior. Si esti grafo triangular llográu del orixinal almite una coloración con cuatro colores o menos, entós el grafo inicial tamién almite la mesma coloración (o una coloración con menos colores), una y bones la coloración sigue siendo válida si esaníciense les arestes introducíes. Asina que basta demostrar el teorema de los cuatro colores pal casu particular de los grafos triangulares pa probalo a tolos grafos planos, y ensin perda de xeneralidá, suponemos que'l grafo ye triangular.
Supongamos que v, a, y c ye'l númberu de vértices, arestes y rexones. Yá que cada rexón ye triangular y cada aresta ye compartida por dos rexones, tenemos que 2a = 3c. Esto, xunto cola fórmula del teorema de Euler pa poliedros (v - a + c = 2) puede utilizase pa demostrar que 6v - 2a = 12. Agora bien, el grau d'un vértiz ye'l númberu de les arestes incidentes. Si vn ye'l númberu de vértices de grau n, y D ye'l grau máximu d'un vértiz, tiense: Pero 12 > 0, ye un númberu positivu y "6 - i ≤ 0" pa tou "i ≥ 6", esto demuestra qu'esiste siquier un vértiz de grau 5 o menos.
Escarpe
thumb|Escarpe d'una [[cuesta, cortáu por una falla.]] El escarpe o escarpia ye una aguada de roca que corta'l terrén abruptamente. La pendiente ye mayor a 45º, anque seya solamente una parte de l'aguada. Dacuando adopta la forma d'una cornisa, que corona una aguada nuna estensión más o menos llarga, anque calteniendo una altitú sensiblemente constante. Delles cornises pueden sobreponese paralelamente dixebraes pola rimada menos abrupta de los depósitos de derrubios. La paré ye un escarpe próximu a la vertical y abondo llisu.
Tierres Medies Occidentales
Tierres Medies Occidentales (West Midlands n'inglés) ye unu de los cuarenta y siete condaos d'Inglaterra, Reinu Xuníu, con capital en Birmingham. Allugáu na rexón Tierres Medies Occidentales, llinda al oeste y norte con Staffordshire, al este y sureste con Warwickshire y al suroeste con Worcestershire. Creáu en 1974, el condáu inclúi, amás de la capital, les ciudaes de Wolverhampton y Coventry.
Escarpe
Escarpe, de manera xeneral, referir a cualquier tipu de saltu qu'ataya la continuidá d'un paisaxe. Sicasí, el conceutu específicu fai referencia a los escarpes de falla, que correspuenden a los saltos o rimaes visibles en quebrar recién de la corteza terrestre. Ye una forma de relieve inicial, presente tan solo nos primeros estadios del procesu erosivu que siguen al movimientu cortical, porque sume en cuanto la erosión fai esmornia nél o se convierte nuna nueva forma de escarpe, el de llinia de falla. Nesti tipu de escarpe danse los tresformamientos más interesantes dende'l puntu de vista xeolóxicu. Aníciense cuando los materiales que formen los llabios de la falla son diversos y unu de los llabios ye menos resistente a la erosión que l'otru. Esto da llugar a nueves tipoloxíes, como son los escarpes de llinia de falla obsecuentes o resecuentes.
Tierres Medies Occidentales
El nome Tierres Medies Occidentales utilízase dacuando pa referise a tola rexón de les Tierres Medies Occidentales, lo que puede causar tracamundios. De cutiu llámase al área del condáu «área metropolitana de les Tierres Medies Occidentales» o «conurbación de les Tierres Medies Occidentales».
Xeografía
Les Tierres Medies Occidentales parten con el condáu de Warwickshire al este, Worcestershire al sur y Staffordshire al norte.
Son unu de los condaos más fuertemente urbanizaos en tol Reinu Xuníu. Birmingham, Wolverhampton, el Black Country y Solihull formen conjuntamente la mayor conurbación de tol país, cola esceición de Londres, con una población que ronda los 2 300 000 habitantes.
Historia
El condáu crear pola llei de gobiernu llocal de 1972 que se punxo en práutica en 1974.
Les Tierres Medies Occidentales tomaron zones que pertenecíen a los condaos históricos de Warwickshire, Staffordshire y Worcestershire.
Birmingham y Coventry pertenecíen tradicionalmente a Warwickshire; Wolverhampton y gran parte del Black Country a Worcestershire, alministraos como distritos del condáu.
Teorema de los cuatro colores
Resume de les idees de la demostración
Si esiste un grafo que rique 5 colores, entós esiste un grafo minimal, onde la eliminación de cualesquier vértiz facer cuatro colorable. Llamemos a esti grafo G. El grafo G nun puede tener un vértiz de grau 3 o menos, porque si g(v) ≤ 3, podemos esaniciar v de G, y colorear con cuatro colores el grafo modificáu más pequeñu, y de siguío, añedir de nuevu'l vértiz v y colorearlo con un color distintu al de los sos vecinos.
Kempe tamién demostró que G nun puede tener nengún vértiz de grau 4. Como antes esaníciase'l vértiz v, y cuatro colores de los vértices restantes. Si los cuatro vecinos de v son de distintos colores, por casu coloráu, verde, azul y mariellu en sentíu horariu, buscamos una ruta alterna de vértices de color coloráu y azul qu'una los vecinos colorao y azul. Tal camín llámase una cadena de Kempe. Puede haber una cadena de Kempe xuniendo a los vecinos de color coloráu y azul, y puede haber una cadena de Kempe xuniendo a los vecinos verdes y mariellos, pero non dambos, una y bones estos dos caminos necesariamente crúciense, y el vértiz onde s'intercepten nun puede ser coloriáu. Supongamos que se trata a los vecinos coloraes y azules que nun tán encadenaos ente sigo. Esplora tolos vértices coneutaos al vecín coloráu pol colloráu-azul caminos alternos, y depués invertir los colores coloráu y azul en toos estos vértices. La resultancia sigue siendo un válidu de cuatro colores, y agora v puede amestase de nuevu y de color coloráu.
Esto dexa namái'l casu en que G tien un vértiz de grau 5; pero l'argumentu de Kempe yera defectuosu pa esti casu particular. Heawood notó l'error de Kempe y tamién alvirtió que si se taba satisfechu con probar que namái cinco colores son necesarios, podría usase l'argumentu anterior (camudando'l contraejemplo por unu que rique 6 colores) y usar les cadenes de Kempe nel vértiz de grau 5 pa demostrar el teorema de los cinco colores:
Xeneralizaciones
thumb|300px|Xuniendo les fleches simples y les fleches dobles, llógrase un toru con siete rexones colindantes, colo que son necesarios siete colores. 480px|thumb|Esta construcción amuesa un toru estremáu nel máximu de siete rexones, caúna de les cualos toca a les otres.
Estudióse tamién el problema de colorear otres superficies que nun sían equivalentes a un planu. Para superficies zarraes (orientables o non orientables) con xéneru positivu, el númberu máximu de colores p que se precisen depende de la carauterística de Euler χ, daos pola siguiente fórmula:
onde los paréntesis esternos determinen la función parte entera.
Alternativamente, pa una superficie orientable, la fórmula puede ser dada en términos del xéneru de la superficie, g:
Esta fórmula, conocida como conxetura de Heawood, foi conxeturada por P. J. Heawood en 1890 y demostrada pa los casos de superficies orientables (y non orientables) non acutaes por Gerhard Ringel y J. T. W. Youngs en 1968. La única esceición a la fórmula ye la Botella de Klein, que tien una carauterística de Euler 0 (d'ende la fórmula da p=7) y rique 6 colores, como lo demostró P. Franklin en 1934 (Weisstein). (Una Banda de Möbius, que la so carauterística de Euler χ = 0, tamién rique 6 colores, pero nesti casu la fórmula nun ye aplicable, yá que ye una superficie acutada. (Weisstein))
El toru tien una carauterística de Euler χ = 0 (y xéneru g = 1) y polo tanto p = 7, de manera que non más de 7 colores son riquíos pa colorear cualquier mapa sobre un toru. El Poliedru de Szilassi ye otru exemplu que rique 7 colores.
Nun hai estensión obvia del problema de coloreo de rexones de sólidos tridimensionales. Usando un conxuntu de n banielles flexibles, unu puede faer que cada baniella toque a caúna de les otres. El conxuntu depués va riquir n colores, o n+1 si considérase que l'espaciu vacíu tamién toca cada baniella. Pal númberu n puede tomase un enteru tan grande como se quiera. tales exemplos fueron propuestos por Fredrick Gurthrie en 1880.
Montreuil-des-Landes
Montreuil-des-Landes ye una comuña francesa del departamentu d'Ille y Vilaine, na rexón de Bretaña. Llenda con.
Teoría de grafos
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 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.
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 (54.70333°N, 20.51556°W) 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 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 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 C<SUB>n</SUB>H2n+2, por aciu un grafo árbol onde los vértices representen átomos y les arestes la esistencia d'enllaces químicos.
El términu «grafo», provién de la espresión graphic notation («notación gráfica») usada per primer vegada por Edward Frankland 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.
Representación de grafos
Esisten distintes formes de representar un grafo (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 grafo 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.
Subgrafos, subgrafos inducíos y menores
Un problema común, denomináu problema d'isomorfismu de subgrafos, ye atopar un grafo fixu como subgrafo d'un grafo 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 grafo 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:
Un problema similar ye atopar subgrafo inducíu nun grafo dau. De nuevu, delles propiedaes importantes son heredaes con al respective de subgrafos inducíos, lo que significa qu'un grafo 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:
Otru nuevu problema ye'l problema del menor conteníu, que ye atopar un grafo fixu como menor d'un grafo dau. Un menor o subcontración d'un grafo ye cualesquier grafo llográu tomando un subgrafo y contrayendo dellos cantos. Munches propiedaes de grafos son heredaes de menores, lo que significa qu'un grafo tener namái si tolos sos menores tener tamién. Por casu, el teorema de Wagner axusta que:
Un problema de les mesmes carauterístiques ye'l problema de la subdivisión del conteníu. Una subdivisión o homeomorfismo d'un grafo ye cualesquier grafo 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: Otru problema na subdivisión de conteníu ye la conxetura de Kelmans-Seymour: 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 grafo 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 grafo del dodecaedru.
El problema de determinar la esistencia de ciclos hamiltonianos, entra nel conxuntu de los NP-completus.
thumb|200px|Un grafo 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
Cuando un grafo o multigrafo puede dibuxase nun planu ensin que dos segmentos se corten, dizse que ye planu.
Cualquier disposición de les cases, los pozos y los caminos implica la presencia de siquier un encruz.
Sía Kn el grafo completu con n vértices, Kn, p ye'l grafo bipartitu de n y p vértices.
Establecer qué grafos son planos nun ye obviu, y ye un problema que tien que ver con topoloxía.
Coloración de grafos
Si G=(V, Y) ye un grafo 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 grafo 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 G=(V, Y) ye un grafo conexu y y pertenez a Ε, entós: P (G,λ)=P (G+y,λ)+P (G/y,λ), onde G/y ye el grafo llograr por contraición d'arestes.
Pa cualesquier grafo G, el términu constante en P (G,λ) ye 0
Sía G=(V, Y), 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 grafo que se llogra de G al añedir 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
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 grafo 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á.
Grafo simple
Un grafo 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 grafo que nun ye simple denominar multigrafo.
Grafos conexos
Un grafo 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 grafo 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 grafo resultante sía disconexo.
Ye posible determinar si un grafo ye conexu usando un algoritmu Busca n'anchor (BFS) o Busca en fondura (DFS).
En términos matemáticos la propiedá d'un grafo (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 grafo, que son (fuertemente) conexes cuando se consideren como grafos aisllaos. Esta propiedá ye importante pa munches demostraciones en teoría de grafos. 400px|thumb|center|Grafo conexu y non conexu
Grafos completos
Un grafo 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 \mathbb{K}, siendo el grafo completu de n vértices.
Un, esto ye, grafo completu de n vértices tien esautamente arestes.
La representación gráfica de los como los vértices d'un polígonu regular da cuenta de la so peculiar estructura.
Grafos bipartitos
Un grafo G ye bipartitu si puede espresar como (esto ye, los sos vértices son la unión de dos grupos de vértices), so les siguientes condiciones:
So estes condiciones, el grafo considérase bipartitu, y puede describise informalmente como'l grafo 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
Dos grafos G_1 y G_2 son homeomorfos si dambos pueden llograse a partir del mesmu grafo con una socesión de subdivisiones elementales d'arestes.
Árboles
thumb|263px|Exemplu d'árbol. Un grafo que nun tien ciclos y que coneuta a tolos puntos, llámase un árbol. Nun grafo con n vértices, los árboles tienen esautamente n - 1 arestes, y hai nn-2 á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 grafo valuáu.
Formalmente, ye un grafo con una función v: A → R+.
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 grafo correspondiente va tener como vértices les ciudaes, como arestes les carreteres y la valuación va ser la distancia ente elles.
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
thumb|263px|Na figura nótase que K4 ye planu (esviando l'aresta ab al esterior del cuadráu), que K5 nun lo ye, y que K3,2 ser tamién (esviadures en gris). Nun grafo, 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 grafo, ye la mayor distancia d'ente tolos pares de puntos de la mesma.
El diámetru de los Kn ye 1, y el de los Kn,p ye 2. Un diámetru infinitu puede significar que'l grafo 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 grafo 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.
Aplicaciones
Gracies a la teoría de grafos pueden resolvese diversos problemes como por casu la síntesis de 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 algoritmos como pue ser l'algoritmu de 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 grafo con determinaos pesos nos sos vértices.
Dientro d'esti campu, un grafo 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).
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.
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 costo 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á.
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
• 3
Referencies
Czumaj, A., Jansen, K., Meyer auf der Heide, F., & Schiermeyer, I. (2006). Algorithmic Graph Theory. Oberwolfach Reports, 379–460.