Tarea 4. Combinatoria, Grafos Opciones

[Cesarator]

Tarea sobre la breve y estandar introducción a la teoría de grafos.

El P4 tiene un error de tipeo y debe decir "... de cada ciudad salen exactamente 20 rutas"
(dice que salen al menos 20)

 Untitled.jpg ( 74.31k ) Número de descargas:  6


Mensaje modificado por Cesarator el Jan 18 2007, 07:06 AM

[Killua]

Solución al problema 5.

Notamos que un cubo tiene 12 aristas , y como tenemos 120 cm de cable, cada arista mide 10 cm. Entonces, construir el cubo con los 120 cm de cable equivale a "dibujar sin levantar el lápiz" un cubo.

Notamos que cada vértice del cubo tiene tres ejes, por lo tanto cada uno tiene grado tres. Entonces el cubo no es euleriano, por lo tanto no se puede construir.

Saludos

[Killua]

El problema 1 es directo del teorema de grafos que dice "en un grafo, el número de vértices de grado impar es par", tomando a los marcianos como los vértices de un grafo. Otra solución, que no usa grafos, viene a continuación

Solución al problema 1

Si un marciano ha dado un número par de veces un apretón de manos, entonces ese marciano es "par". Si ha dado un número impar de veces, entonces el marciano es "impar". Al comienzo de la raza marciana, nadie había dado un apretón de manos; o sea todos los marcianos eran pares. Cuando a dos marcianos se les ocurrió darse la mano, entonces ellos dos quedaron impares (un número par de impares). Desde aquí, tenemos las siguientes posibilidades: si un par le da la mano a otro par, entonces el número de marcianos impares aumenta en dos, por lo tanto la cantidad de impares sigue siendo par; si un impar le da la mano a un impar, entonces la cantidad de marcianos impares disminuye en dos, con lo que la cantidad de impares sigue par; y, nuestro último caso, si un impar estrecha la mano de un par, entonces su "paridad" se intercambia, quedando el mismo número de pares e impares que había. Hemos probado lo pedido

Saludos

[Vicho_Correa]

Problema 3:

Este habría sido el 2º mas fácil si nos hubieran dicho que @%&$# era conexo (ver AQUÍ).
Supongamos que no es conexo, luego consideremos dos vértices a y b tales que no puede irse de a hasta b. Tanto a como b están unidos con vertices cada uno, pero como estos últimos deben ser distintos entre sí, el grafo estaría formado por al menos vértices distintos, y por contradicción el grafo es conexo.