Shuanexmalaonda

1) El teorema de los 4 colores dice que para cualquier grafo planar, este puede ser coloreado con a lo sumo cuatro colores diferentes, de forma que no queden caras adyacentes con el mismo color."

Esta propuesto para grafos planares.

La demostración de ese teorema es cuanto menos polémica, ya que no se pudo demostrar matemáticamente. Se realizó mediante cálculos de un ordenador, por esta causa muchos matemáticos no la aceptan como válida. Sin embargo, la solución parte de un razonamiento matemático previo que reduce el teorema a un conjunto de casos limitado y fueron únicamente estos casos los que se probaron por ordenador sorteando así el límite de la prueba manual.

Hay un teorema similar con 3 colores que estipula que cualquier grafo planar sin triángulos es 3-coloreable.

2)



fun build

fun pertenece a [] = false
| pertenece a (x,y)::xs = if a=x then true else pertenece a xs;

fun dirigido [] = []
|dirigido ((x,y)::xs) = [(x,y)]@[(y,x)]@(dirigido xs);

fun vecino a [] = []
| vecino a (x,y)::xs = if a=x then y::(vecino a xs) else vecino a xs;


fun dfs (x,y)::xs visitados =