b"\n_START_ARTICLE_\nLa teoria de grafs de Leonhard Euler\n_START_PARAGRAPH_\nLa teoria de grafs, com la coneixem avui en dia no va apar\xc3\xa8ixer fins al segle XX quan D\xc3\xa9nes K\xc5\x91nig va escriure el primer llibre que en parlava l\xe2\x80\x99any 1936. Euler no parlava de grafs, ell parlava de problemes de geometria de posici\xc3\xb3. Ell va impulsar l\xe2\x80\x99estudi dels grafs per\xc3\xb2 no els va inventar._NEWLINE_El precursor de la teoria de grafs fou Leonhard Euler, que la va iniciar tot intentant resoldre el problema dels set ponts de K\xc3\xb6nigsberg i el problema del cavall.\n_START_SECTION_\nProblema dels ponts de K\xc3\xb6nigsberg\n_START_PARAGRAPH_\nEl problema dels ponts de K\xc3\xb6nigsberg va sorgir d\xe2\x80\x99una pregunta popular inofensiva. K\xc3\xb6nigsberg, l'actual Kaliningrad, \xc3\xa9s una ciutat russa per la qual passa el riu Pregolya. Enmig del riu, dues grans illes estaven connectades entre elles i a les voreres mitjan\xc3\xa7ant una estructura de set ponts en total._NEWLINE_Els habitants de la ciutat es plantejaven si era possible rec\xc3\xb3rrer els set ponts de manera que nom\xc3\xa9s es pass\xc3\xa9s per cadascun d'ells un sol cop._NEWLINE_Euler va resoldre aquest problema donant la primera demostraci\xc3\xb3 l\xe2\x80\x99any 1736. Ell no va mencionar en cap moment les paraules graf, v\xc3\xa8rtex, aresta o grau._NEWLINE_El primer que va fer Euler al veure aquest problema va ser pensar que realment el que deia Leibniz en el seu Geometriam situs era cert. \xc3\x89s a dir, que existia una branca de la geometria en la qual hi havia unes propietats de posici\xc3\xb3 per\xc3\xb2 no propietats de dist\xc3\xa0ncies. Euler no va trobar aix\xc3\xb2 llegint Leibniz sin\xc3\xb3 parlant amb Johann Bernoulli. Ell abans de comen\xc3\xa7ar va dir que semblava un problema geom\xc3\xa8tric per\xc3\xb2 que no depenia de la mesura de dist\xc3\xa0ncies._NEWLINE__NEWLINE_A continuaci\xc3\xb3 Euler va descriure el problema de la seg\xc3\xbcent manera.Com podem veure a la Fig. 1. Va denotar els ponts com a; a, b, c, d, e, f i g i les \xc3\xa0rees de terra com A, B, C i D. Es va formular la pregunta; com alg\xc3\xba pot organitzar una ruta passant una vegada per cada pont? Sense tenir en compte si acabava al mateix punt que comen\xc3\xa7ava. Ell va dir que primer buscaria tots els resultats i despr\xc3\xa9s buscaria la soluci\xc3\xb3 particular de comen\xc3\xa7ar i acabar al mateix punt. _NEWLINE_Va posar exemples de la notaci\xc3\xb3 que utilitzaria per representar els recorreguts. Per exemple AB \xc3\xa9s el pas de l\xe2\x80\x99\xc3\xa0rea de terra A a la B utilitzant qualsevol dels ponts. No obstant aix\xc3\xb2, si volia especificar el pont pel qual passava l\xe2\x80\x99escrivia aix\xc3\xad AbB, Recorregut de A a B passant pel pont b. _NEWLINE_Aleshores va plantejar que un recorregut seria per exemple ABCD, comen\xc3\xa7ant en A, passant per B i C, per acabar en D. Ell va veure que no era una soluci\xc3\xb3 del problema per\xc3\xb2 va deduir que la soluci\xc3\xb3 del problema necessitaria vuit lletres, ja que hi ha set ponts. Per tant, la soluci\xc3\xb3 del problema romania en trobar un recorregut de vuit lletres._NEWLINE_Tamb\xc3\xa9 va veure que hi havia d\xe2\x80\x99haver certes restriccions en el recorregut, ja que de l\xe2\x80\x99\xc3\xa0rea de terra A a l\xe2\x80\x99\xc3\xa0rea de terra C hi havia dos ponts, per tant A i C havien de sortir correlatives dues vegades. Euler va preguntar-se si aix\xc3\xb2 era possible i va afirmar que si no era possible trobar un recorregut amb aquestes caracter\xc3\xadstiques, aleshores era impossible trobar una soluci\xc3\xb3 al problema perqu\xc3\xa8 aquest no en tenia._NEWLINE__NEWLINE_Posteriorment, va buscar un problema m\xc3\xa9s senzill per trobar regles que confirmessin o no que existia aquesta seq\xc3\xbc\xc3\xa8ncia de lletres. A la Fig. 2 podem veure com va plantejar un problema amb els ponts a, b, c, d, etc. amb dues \xc3\xa0rees de terra A i B. _NEWLINE_Euler va veure que si hi havia un sol pont, llavors la lletra A apareixia nom\xc3\xa9s una vegada sense que comenc\xc3\xa9s i acab\xc3\xa9s en A, si hi havia tres ponts, llavors la lletra A apareixia dues vegades, si hi havia cinc ponts, la lletra A apareixia tres vegades. Per tant, en general, si hi ha un nombre imparell de ponts, llavors, el nombre de vegades que apareix la lletra A a la seq\xc3\xbc\xc3\xa8ncia \xc3\xa9s la meitat m\xc3\xa9s u del nombre de ponts._NEWLINE_Aplicant aix\xc3\xb2 al cas dels ponts de K\xc3\xb6nigsberg, la lletra A hauria d\xe2\x80\x99apar\xc3\xa8ixer tres vegades perqu\xc3\xa8 hi ha cinc ponts fins a l\xe2\x80\x99\xc3\xa0rea A. Llavors les lletres B, C i D haurien d\xe2\x80\x99apar\xc3\xa8ixer dues vegades cada una perqu\xc3\xa8 hi ha tres ponts fins a cada una de les \xc3\xa0rees. Aix\xc3\xb2 vol dir que el nombre de lletres de la seq\xc3\xbc\xc3\xa8ncia per obtenir un resultat, si existeix, \xc3\xa9s la suma de les vegades que haurien d\xe2\x80\x99apar\xc3\xa8ixer les lletres. \xc3\x89s a dir, 3+2+2+2=9. Per\xc3\xb2 nom\xc3\xa9s hi ha set ponts, llavors, una seq\xc3\xbc\xc3\xa8ncia de lletres per la que nom\xc3\xa9s es passa una vegada per cada pont hauria de ser de 8 lletres. Per tant no existeix aquesta soluci\xc3\xb3. _NEWLINE_Posteriorment, Euler intenta generalitzar aquest resultat per a qualsevol problema amb diferents nombres d\xe2\x80\x99\xc3\xa0rees i qualsevol nombre de ponts sigui parell o imparell. Ho veiem tot seguit.\n_START_SECTION_\nTerminologia actual i resum de les conclusions d'Euler\n_START_PARAGRAPH_\nUn graf \xc3\xa9s un parell ordenat G:=(V, E) que compr\xc3\xa8n un conjunt V de v\xc3\xa8rtexs o nodes juntament amb un conjunt E d\xe2\x80\x99arestes o l\xc3\xadnies, les quals s\xc3\xb3n conjunts de dos elements de V. Els grafs poden ser no dirigits, \xc3\xa9s a dir sense fer distinci\xc3\xb3 entre els dos v\xc3\xa8rtexs associats a cada aresta, o dirigits, les arestes dels quals van d'un v\xc3\xa8rtex a un altre; en aquest cas, les arestes s'anomenen arcs. El grau d'un v\xc3\xa8rtex \xc3\xa9s el nombre d'arestes que hi incideixen._NEWLINE_Un cam\xc3\xad euleri\xc3\xa0 \xc3\xa9s aquell cam\xc3\xad que recorre tots els v\xc3\xa8rtexs (nodes) d'un graf passant una i nom\xc3\xa9s una vegada per cada arc (aresta) del graf. Un cicle euleri\xc3\xa0 \xc3\xa9s un cam\xc3\xad euleri\xc3\xa0 que comen\xc3\xa7a i acaba al mateix v\xc3\xa8rtex._NEWLINE_Un cam\xc3\xad hamiltoni\xc3\xa0 \xc3\xa9s un cam\xc3\xad en un graf no dirigit que passa per cada v\xc3\xa8rtex del graf exactament un cop. Un cicle hamiltoni\xc3\xa0 (o circuit hamiltoni\xc3\xa0) \xc3\xa9s un cam\xc3\xad hamiltoni\xc3\xa0 que retorna al v\xc3\xa8rtex de sortida._NEWLINE_Quan expressem les conclusions d'Euler d\xe2\x80\x99abans per una xarxa qualsevol d'aquest tipus en terminologia moderna de teoria de grafs, tenim:_NEWLINE_1. Si m\xc3\xa9s de dos v\xc3\xa8rtexs tenen grau senar, aleshores no \xc3\xa9s possible un cam\xc3\xad Euleri\xc3\xa0._NEWLINE_2. Si exactament dos v\xc3\xa8rtexs tenen grau senar, llavors un cam\xc3\xad Euleri\xc3\xa0 \xc3\xa9s possible sempre, si comen\xc3\xa7a en qualsevol dels dos territoris representats per v\xc3\xa8rtex de grau senar i finalitza en l'altre. _NEWLINE_3. Si tots els v\xc3\xa8rtexs tenen grau parell, llavors es pot aconseguir el cicle Euleri\xc3\xa0 comen\xc3\xa7ant des de qualsevol v\xc3\xa8rtex._NEWLINE_ _NEWLINE_Tamb\xc3\xa9 tenim que quan resolia el problema del cavall treballava amb cicles hamiltonians._NEWLINE_Euler tamb\xc3\xa9 va trobar el Teorema de la caracter\xc3\xadstica que diu:_NEWLINE_(V\xc3\xa8rtex)+(Cares)=(Arestes)+2 _NEWLINE_Obtenint d\xe2\x80\x99aqu\xc3\xad posteriorment la f\xc3\xb3rmula d\xe2\x80\x99Euler per grafs que diu que la suma dels graus dels v\xc3\xa8rtexs \xc3\xa9s igual al doble del nombre arestes."