Teoria de Grafs

Us anem a proposar un problema:

Podries creuar tots els pont començant per qualsevol però sense creuar un mateix pont dos cops?pontsAquest curiós problema va donar lloc a la Teoria de Grafs ja que per a la seva resolució, Leonhard Euler, va crear un graf substituint les illes i riberes per punts i els ponts per arestes. I així, va aconseguir demostrar que no era possible recorrer els set pont sense haver de repetir-ne algun.

ponts2  fletxa   ponts simplificat   fletxa graf pons

El problema va sorgir l’any 1736, perquè a una ciutat anomenada Königsberg, situada a Rússia però que abans era d’Alemanya, es volia fer una desfilada, i els habitants de la ciutat es van plantejar si podien creuar els 7 ponts sense repetir-ne cap. Van demanar ajuda a Euler i ell va resoldre el problema.

Euler es va adonar que el problema es resolia en funció del grau dels nodes o vèrtexs (és a dir, del número d’arestes que hi arriben): Va provar que el circuit que es desitjava era possible si hi ha exactament dos nodes o ningun de grau senar. Si no n’hi ha cap (tots els vèrtexs parells) és possible començar en qualsevol node i acabar en el mateix, en canvi, si n’hi ha dos de senars cal començar en un d’ells i acabar en l’altre.

En el cas dels ponts de Königsberg hi ha 3 nodes de grau 3 i un de grau 5, per tant, tots quatre són senars i per això no es pot recorrer.

Ara intenta recorre aquests grafs passant per totes les arestes sense repetir-ne cap. Sabries fer el mateix sortint d’un punt i tornant al mateix?

graf1            graf2      graf3

Ja ho heu provat?

Haureu comprovat que el primer graf es pot recórrer partint de qualsevol vèrtex i tornant al mateix. Això és degut a que tots els seus vèrtexs són parells (tots tenen grau 4). Un graf així s’anomena Eulerià.

El segon graf es pot recórrer només si començem en el vèrtexs G o H i l’acabem sempre en l’altre. Això és degut a que aquests són els seus únics dos vèrtexs senars (G té grau 3 i H té grau 1). Un graf així s’anomena Semieulerià.

El tercer graf no es pot recórrer sense repetir alguna aresta. Això és degut a que té més de 2 vèrtexs senars (A, B, C i D tenen grau 3). Un graf així s’anomena No-Eulerià.

Si no n’heu tingut prou, proveu de passar pels 17 ponts que uneixen entre sí les parts del territori de Leningrad, sense recórrer ningun d’ells dues vegades:

Leningrat

L’any 1931, un enginyer elèctric i matemàtic que es deia Harry Beck va crear el recorregut de les línies de metro de Londres a través d’un disseny topogràfic i no geogràfic com els anteriors i aplicant la teoria de Grafs. Fins avui dia la idea topogràfica de Beck es la més utilitzada en el mon per aquests tipus de plànols.

mapa Londres

Us deixem una pàgina web molt interesant sobre grafs on podeu practicar tot això:

https://dl.dropboxusercontent.com/u/44162055/manipulables/topologia/topologia_trazos.html

El següent enllaç és un editor de grafs:

http://illuminations.nctm.org/Activity.aspx?id=3550

Anuncis

Teorema dels quatre colors

Quants colors creieu que fan falta per tal d’acolorir un mapa sense que dues regions limítrofes (que estan l’una al costat de l’altre) tinguin el mateix color sense considerar les que es tallen en un sol punt? Dos? Vuit? Cinc?

El teorema dels quatre colors diu que qualsevol mapa dibuixat sobre un pla o sobre una esfera es pot acolorir amb quatre colors distints de manera que dues regions adjacents no siguin del mateix color, com per exemple en aquest mapa

Francis Guthrie

El teorema va ser plantejat per primer cop l’any 1852 per Francis Guthrie a la seva germana després d’acolorir un mapa de Gran Bretanya. El problema es va plantejar de la següent manera: “Són suficients quatre colors per acolorir qualsevol mapa imaginable de manera que cap país amb límits comuns tingui el mateix color?”. I així una simple pregunta per divertir a una germana, es va convertí en un problema matemàtic que va estar obert més de 100 anys.

 

El teorema va ser demostrat l’any 1976 per Kenneth Appel i Wolfgang Hanken. Va ser una demostració que va crear una gran polèmica degut a que va ser assistida per un ordinador i per tant era impossible de comprovar a mà per un humà. Aquesta demostració es basava en demostrar que hi ha un conjunt particular de 1.936 mapes, cadascun dels quals no pot formar part d’un contraexemple de mida més petita pel teorema dels quatre colors i aquests mapes van ser comprovats per un ordinador. Anys més tard, el 1997, va ser demostrat d’una manera més senzilla per Neil Robertson, Daniel P. Sanders, Paul Seymour i Robin Thomas. El 2005, Benjamin Werner i Georges Gonthier van formalitzar una demostració del teorema dins de l’assistent de proves Coq. La resolució d’aquest teorema està molt lligada amb la Teoria de Grafs, ja que va definir termes i conceptes fonamentals per a l’estudi dels grafs (els grafs són col·leccions d’objectes, anomenats vèrtex connectats per línies anomenades arestes.

Kenneth Appel (sentat) i Wolfgang Hanken (dret)

Martin Gadner deia haver trobat un contra-exemple de la teoria dels quatre colors, però era fals. Aquí us deixem el mapa que va fer perquè el pugueu veure i provar de resoldre’l només usant quatre colors: http://www.xtec.cat/~jjareno/problemes/geometrics/4_colors_e.htm

Però… com podem estar segurs de que estem acolorint un mapa amb el mínim de colors necessaris? Doncs utilitzant l’algoritme d’acolorit.

Primer hem de saber que tot mapa, en el pla o en l’esfera pot ser representat mitjançant graf i si cap aresta es talla amb una altra el graf s’anomena planar. Així doncs, començarem l’algoritme fent el graf planar corresponent al mapa que volem acolorir. Cada regió serà un vèrtex i posarem una aresta entre els vèrtexs que representin regions contigües.

Tot seguit, ordenarem els vèrtexs en ordre decreixent segons el grau (nombre d’arestes que té un vèrtex).

Foto teorema dels 4 colors 3

Assignarem colors a cada vèrtex de la següent manera:

  1. Assignarem el primer color al primer vèrtex.
  2. Al segon vèrtex li assignarem el primer color si no és adjacent i si ho és li assignarem el segon color.
  3. Si el tercer vèrtex és adjacent a tots dos anteriors li assignarem el tercer color, si no és adjacent al primer vèrtex li assignarem el primer color i si és adjacent al primer, però no al segon vèrtex li assignarem el segon color.
  4. Seguirem amb aquest procés fins que haguem assignat un color a tots els vèrtex.

Finalment acolorirem el graf i tot seguit el mapa.

Foto teorema dels 4 colors FINAL

En aquest enllaç podreu veure aquest procés d’acolorit, pas a pas, per al mapa de les Comunitats Autònomes d’Espanya, i veureu que és suficient pintar-lo amb només 3 colors.

Els grafs planars van ser ideats per Euler, un famós matemàtic molt important. A continuació us deixem un vídeo sobre la vida d’aquest home.

A la següent entrada, uns companys nostres us explicaran com saber si un graf es pot recòrrer d’una sola passada!

La conjectura de Goldbach

La conjectura forta de Goldbach (1742) diu que tot nombre parell major que 2 es pot expressar com a suma de dos nombres primers (tingueu en compte que l’1 no es considera primer). És un enunciat senzill que, com passa en moltes altres ocasions, ens duu a estudis molt complicats.

Alguns exemples de la conjectura són aquests:

6=3+3                24=17+7               78=31+47             354=127+227          …

Aquesta afirmació va ser enunciada en una carta que va escriure Christian Goldbach al gran matemàtic de l’època Leonard Euler.

La interessant pel·lícula “La habitación de Fermat” comença amb l’enunciat d’aquesta conjectura.

 

En aquesta web podem obtenir la representació d’un número parell com suma de dos números primers, simplement introduïnt el mateix.

en aquest enllaç podem veure un video que parla de la història de la Conjectura de Goldbach.

Com diu en en vídeo, la conectura dèbil de Goldbach (“tot nombre senar major a cinc es pot escriure com la suma de 3 nombres primers“) es va demostrar l’any 2013 per Herald Andrés, un matemàtic peruà.