Aplicacions de la teoria de gràfics
Gràfics plans
Es diu que un gràfic G és planer si es pot representar en un pla de tal manera que els vèrtexs són punts diferents, les vores són corbes simples i no hi ha dues vores que no es troben cap als altres terminals. Per exemple, K 4, el gràfic complet en quatre vèrtexs, és pla, com mostra la figura 4A.
Es diu que de dues gràfiques són homeomòrfiques si ambdues es poden obtenir de la mateixa gràfica mitjançant les subdivisions de vores. Per exemple, els gràfics de la figura 4A i la figura 4B són homeomorfs.
El gràfic K m, n és un gràfic pel qual el conjunt de vèrtex es pot dividir en dos subconjunts, un amb vèrtexs m i l’altre amb n vèrtexs. Els dos vèrtexs del mateix subconjunt no són adjacents, mentre que els dos vèrtexs de subconjunts diferents són adjacents. El matemàtic polonès Kazimierz Kuratowski el 1930 va demostrar el següent teorema famós:
Una condició necessària i suficient perquè un gràfic G sigui planer és que no contingui un subgraf homeomòrfic ni K 5 o K 3,3 que es mostra a la figura 5.
Una contracció elemental d'un gràfic G és una transformació de G a un nou gràfic G 1, de manera que dos vèrtexs adjacents u i υ de G se substitueixen per un nou vèrtex w a G 1 i w és adjacent a G 1 a tots els vèrtexs a que o o υ és contigua a G. Es diu que el gràfic G * és una contracció de G si G * es pot obtenir de G mitjançant una seqüència de contraccions elementals. A continuació, es mostra una altra caracterització d’un gràfic pla a causa del matemàtic alemany K. Wagner el 1937.
Un gràfic és planer si i només si no és contractible a K 5 o K 3,3.
El problema del mapa a quatre colors
Durant més d’un segle la solució del problema del mapa en quatre colors va evadir tots els analistes que ho van intentar. Pot ser que el problema hagi cridat l'atenció de Möbius, però la primera referència escrita a ella sembla ser una carta d'un Francis Guthrie al seu germà, un estudiant d'August De Morgan, el 1852.
El problema es refereix a mapes plans, és a dir, subdivisions del pla en regions no superposades delimitades per simples corbes tancades. Als mapes geogràfics s’ha observat empíricament, en tants casos especials que s’han provat, que, com a màxim, es necessiten quatre colors per tal de acolorir les regions de manera que dues regions que comparteixen un límit comú siguin sempre de color diferent, i determinats casos que són com a mínim quatre colors. (Les regions que només es reuneixen en un moment determinat, com els estats de Colorado i Arizona dels Estats Units, no es consideren que tenen un límit comú). Una formalització d'aquesta observació empírica constitueix el que s'anomena "el teorema de quatre colors". El problema és demostrar o rebutjar l’afirmació que aquest és el cas de tots els mapes plans. Que no n’hi ha prou amb tres colors, es demostra fàcilment, mentre que el matemàtic britànic PJ Heawood va ser demostrat amb suficiència de cinc colors el 1890.
El 1879 AB Kempe, un anglès, va proposar una solució del problema de quatre colors. Tot i que Heawood va demostrar que l'argument de Kempe era defectuós, dos dels seus conceptes van resultar fructífers en investigacions posteriors. Una d’aquestes, anomenada inevitabilitat, afirma correctament la impossibilitat de construir un mapa en el qual no existeixi cada una de les quatre configuracions (aquestes configuracions consisteixen en una regió amb dos veïns, un amb tres, un amb quatre i un altre amb cinc). El segon concepte, el de reducibilitat, pren el seu nom de la prova vàlida de Kempe que si hi ha un mapa que requereix almenys cinc colors i que conté una regió amb quatre (o tres o dos) veïns, hi ha d’haver un mapa que requereixi cinc colors per a un nombre menor de regions. L'intent de Kempe de demostrar la reducibilitat d'un mapa que contenia una regió amb cinc veïns va ser erroni, però es va corregir en una prova publicada el 1976 per Kenneth Appel i Wolfgang Haken dels Estats Units. La seva prova va atreure algunes crítiques perquè va requerir l'avaluació de 1.936 casos diferents, cadascun dels quals va implicar fins a 500.000 operacions lògiques. Appel, Haken i els seus col·laboradors van idear programes que van permetre a un gran ordinador digital manejar aquests detalls. L’ordinador va requerir més de 1.000 hores per realitzar la tasca, i la prova formal resultant és de diversos centenars de pàgines.
Cicles eulerianos i problema del pont de Königsberg
Una multígrafa G consisteix en un conjunt V (G) no buit de vèrtexs i un subconjunt E (G) del conjunt de parells no ordenats d’elements diferents de V (G) amb una freqüència f ≥ 1 unida a cada parella. Si la parella (x 1, x 2) amb la freqüència f pertany a E (G), els vèrtexs x 1 i x 2 s'uneixen per les vores f.
Un cicle eulerià d’un multígraf G és una cadena tancada en la qual cada aresta apareix exactament una vegada. Euler va demostrar que un multígraf té un cicle eulerià si i només si està connectat (a part de punts aïllats) i que el nombre de vèrtexs de grau imparell és zero o dos.
Aquest problema va sorgir de la manera següent. El riu Pregel, format per la confluència de les seves dues branques, recorre la ciutat de Königsberg i desemboca a banda i banda de l'illa de Kneiphof. Hi havia set ponts, tal com es mostra a la figura 6A. Els ciutadans es preguntaven si era possible fer una passejada i creuar cada pont una vegada. Això equival a trobar un cicle eulerià per al multígraf de la figura 6B. Euler va demostrar que era impossible perquè hi ha quatre vèrtexs d'ordre imparell.
