El grafo de Catlin.

A continuacion les presento el grafo de Catlin:

Grafo de Catlin, tomado del libro Graph Theory de Bondy  y Murty

A primera vista podra pararecer un grafo un tanto entreverado pero notemos bien, es un ejemplo de composicion de grafos, es decir poner un grafo dentro de otro, !como !?
La composicion de un grafo B en un grafo A, representada por A[B] simplemente lo siguiente, cada vertice del grafo A ahora ya no es un vertice sino que ahora va ser un nuevo grafo!, en este caso una instancia del grafo B, y las aristas? pues lo logico seria, que si queremos unir dos grafos, unamos cada vertice de un grafo con cada vertice del otro.

Listo, entonces observen bien el grafo de alla arriba, es nada menos que un circuito de  5 vertices en el que cada vertice ha sido reemplazado por un grafo completo de tres vertices(osea, un triangulo), su nomenclatura
es $C_5[K_3]$.

Se le dice grafo de Catlin, por que Catlin lo utilizo para encontrar contraejemplos en la  Conjetura de Hadwiger

Ahora este grafo puede ser generalizado a un $C_n[K_r]$, donde $C_n$ es un circuito de tamanho $n$ y $K_r$ es un grafo completo con $r$ vértices.

La pregunta de rigor es, cual es el menor numero de colores con que se puede pintar los vertices de este grafo tal que  dos vertices del mismo color no son adjacentes.A este numero minimo se le llama numero cromatico del grafo.

Tal vez la pregunta es muy general en realidad no se como resolverla para cualquier n, r. Entonces vamos a partirla en varias subpreguntas.

Cual es el numero cromatico de un  $C_5[K_3]$
Cual es el numero cromatico de un  $C_5[K_r]$
Cual es el numero cromatico de un  $C_n[K_3]$
y la mas general, Cual es el numero cromatico de un  $C_n[K_r]$?

Bueno ahora si voy a necesitar ayuda asi que si alguien sabe la respuesta de la ultima pregunta me avisa jajaja.

El grafo del caballo

Hola amigos y amigas, el siguiente problema tiene que ver con ajedrez, asi que espero motive a los fanaticos de este apasionanete juego. Bien ustedes saben que el caballo tiene un movimiento un tanto peculiar,( se mueve dos casilleros en una direccion y luego uno en una direccion perpendicular a ella). Ahora, si comenzamos a mover el caballo desde una posicion cualquiera hacia todo el tablero, sera que el caballo logra cubrir todo el tablero?, cuantas movidas diferentes puede hacer el caballo hasta regresar  a su posicion inicial?, pues bien todas estas preguntas pueden resolverse mejor si transformamos ese problema a un grafo, el grafo del caballo. Generalizando un poco el asunto, el grafo del caballo nxn seria un grafo con nxn nodos(cada uno de los cuales es un casillero del tablero nxn) de tal manera que dos nodos son adjacentes si existe una movida de caballo de un nodo hacia otro.

El presente problema pide calcular el numero de aristas en este grafo.Saludos!

Solucion: aqui

Numero de conocidos en una fiesta

El siguiente problema me parece bien chevere y sencillo, demostrar que en una fiesta hay por lo menos dos personas con el mismo numero de conocidos, parece raro pero se cumple!.

Ojo, si A conoce a B, entonces B conoce a A. No se puede dar que por ejemplo Pancho conozca a Pirulo pero Pirulo no conoce a Pancho(o lo conoce de vista). Ademas la fiesta debe ser de por lo menos dos personas(para poder llamarse fiesta).

Saludossssss.

Permutacion aleatoria uniforme

Saludos,el siguiente problema plantea lo siguiente: Dado un arreglo A indexado de 1 a N. Devolver una permutacion aleatoria uniforme de ese vector.
Bueno, esos tres nombres suenan un poco grandes, pero es facil de entender.

Primero, una permutacion, es decir variamos solamente el orden de los elementos del conjunto. Por ejemplo, dado digamos el arreglo {1 2 3 4}, devolvemos el arreglo {1 4 3 2} o el arreglo {4 2 3 1}. Un arreglo que no podemos devolver es el arreglo {1 1 3 4}.

La ultima parte es un poco mas dificil de comprender, tal vez sea bueno estar familiarizado con el concepto de variable aleatoria y distribucion uniforme. En resumen lo que se debe cumplir es que, la permutacion que el programa haya generado ha de tener la misma probabilidad de haber salido que cualquier otra permutacion.

Analizando un poco mas de cerca, esto queire decir que, dado n el tamanho del arreglo, la probabilidad de cada permutacion ser elegida, ha de ser 1/n! (ya que existen n! permutaciones). Osea, no puede haber favoritismos de elegir alguna permutacion u otra, ha de ser un algoritmo equitativo.

Bueno, entonces espero les guste el problema, la solucion en los comentarios.Chauuuuuuuu

N a la N.

Holaaaaaaaaaaaa, el siguiente problema es pequeno pero interesante, cómo hacer un algoritmo para calcular $ n^{n}$? Bueno ustedes dirán, fácil, hago un for de 1 hasta n y tendriamos en total n multiplicaciones. Pero hay una forma de hacer esto mas rápido?. El problema pide hacer un algoritmo para calcular $ n^{n}$ haciendo no más que $ 2\lg n$ multiplicaciones. La solucion en los comentarios.

Obs: el problema fue tomado del curso MAC5711 Análise de Algoritmos,en el IME, Slides de Paulo Feofiloff.

Acotación polinomial

El siguiente problema pertenece al capitulo 3 del libro de Cormen Introduction to algorithms 2 edicion el cual pueden descargar aqui (ojo que ya salio la tercera). Bueno el capitulo 3 trata sobre Notacion asintotica, para darse una idea den una revisada aca. La notacion O-grande es la mas utilizada y nos dice si una funcion esta acotada por otra. Bien, cuando una función esta acotada por un polinomio existe acotación polinomial, por ejemplo Por ejemplo, log(n) esta acotada por n que es un polinomio, pero n! no esta acotado por ningun polinomio.
Otro concepto importante es el de piso y techo de un numero, en resumen el piso de una funcion es el maximo entero menor o igual que el numero dado y el techo seria el minimo entero mayor o igual que el numero dado.
El siguiente problema pide decidir si $\lceil lg n \rceil !$ está acotada polinomialmente, y si $\lceil( lg lg n)\rceil !$ lo está.
Ah porsiacaso, lgn significa logaritmo en base dos de n.

La solucion en los comentarios...,saludos.

Subsequencia de suma maxima

El siguiente problema es bastante conocido en la ciencia de la computación: Dado un arreglo de números enteros(ojo,pueden ser negativos).Encontrar la subsequencia que posee suma maxima.Por ejemplo, si tenemos el siguiente arreglo: 4,-1,-5,6,-4,2,-1,4 la subsequencia de suma máxima es: ,6,-4,2,-1,4. Existe el algoritmo obvio, que busca todas las posibilidades y resuelve el problema en tiempo cuadratico, sin embargo existe un algoritmo que resuelve el problema en tiempo linear, cual es este algoritmo?La solucion en los comentarios,saludoss...