5. Indica qué grafos de la figura 1 son isomorfos



Descargar 9.39 Kb.
Fecha de conversión02.07.2017
Tamaño9.39 Kb.

GRAFOS I



1.- En un futuro no muy lejano habrá viajes interplanetarios. Supón que en el sistema solar se establecieran las siguientes rutas (y sólo éstas): Tierra-Mercurio, Plutón-Venus, Tierra-Plutón, Plutón-Mercurio, Mercurio-Venus, Urano-Neptuno, Neptuno-Saturno, Saturno-Júpiter, Júpiter-Marte, y Marte-Urano. ¿Se podría realizar el viaje desde La Tierra hasta Marte?
2.- Cuatro caballos, dos blancos y dos negros, están colocados en un tablero de 3x3 casillas, ocupando las esquinas de modo que los dos caballos blancos están en dos esquinas consecutivas. ¿Podrán moverse, usando el movimiento habitual de los caballos en ajedrez, de modo que al final resulten los dos caballos blancos en esquinas opuestas y los dos negros también en esquinas opuestas?
3.- Un tablero tiene forma de cruz, obtenida suprimiendo las esquinas de otro tablero de 4x4 casillas. ¿Podrás mover un caballo de modo que, empezando por una casilla del tablero pase por TODAS las casillas UNA SÓLA VEZ y termine en la misma casilla en la que comenzó?
4.- En cierto país hay nueve ciudades que llamaremos 1, 2, 3, 4, 5, 6, 7, 8 y 9. Las rutas aéreas entre ellas son un tanto curiosas, pues sólo hay vuelo de una ciudad a otra si el número de dos dígitos formado por los nombres de las ciudades de salida y de llegada es divisible entre 3. ¿Se puede viajar de la ciudad 1 a la 9?
5.- Indica qué grafos de la figura 1 son isomorfos.
6.- Prueba que los grafos de la figura 2 son isomorfos. ¿Serías capaz de nombrar los vértices de modo que existieran exactamente las mismas conexiones en los dos grafos?
7.- En Pequeñelandia hay 15 teléfonos. ¿Podríamos conectarlos con cables de modo que cada teléfono tenga línea exactamente con otros cinco?
8.- En un país hay cien ciudades y de cada ciudad salen (o llegan) cuatro carreteras. ¿Cuántas carreteras hay en ese país?
9.- En una clase hay treinta alumnos. ¿Puede ocurrir que nueve de ellos tengan exactamente tres amigos cada uno, once tengan cuatro amigos cada uno y diez tengan cinco amigos cada uno?
10.- Volvemos a los teléfonos de Pequeñelandia. ¿Podrían conectarse de modo que haya cuatro teléfonos que tengan cada uno línea con otros tres, ocho teléfonos que la tengan cada uno con otros seis y tres teléfonos que estén conectados cada uno con otros cinco?
11.- Un rey tiene diecinueve súbditos. ¿Puede suceder que cada súbdito tenga uno o cinco o nueve vecinos?
12.- ¿Puede un país en el que de cada ciudad salen tres carreteras tener exactamente cien carreteras?
13.- Cuando Antonio volvió de Disneylandia dijo que había visto un lago encantado que tenía siete islas, de cada una de las cuales salía uno, tres o cinco puentes. ¿Es cierto que por lo menos uno de esos puentes llevaba a la orilla del lago?
14.- Prueba que el número de personas que han vivido en la tierra en cualquier momento y que han saludado a otras con un apretón de manos un número impar de veces en toda su vida es par.
15.- ¿Se pueden dibujar nueve segmentos en el plano de modo que cada uno corte exactamente a otros tres?
16.- En el país del Siete hay quince pueblos cada uno de los cuales está comunicado a por lo menos siete de los otros. Demuestra que se puede viajar de un pueblo a otro cualquiera, aunque para ello haya que pasar posiblemente por algún otro pueblo en medio.
17.- En el país de Nuncajamás existe un único medio de transporte: la alfombra mágica. Hay veintiuna líneas de alfombras que hacen escala en la capital y una sóla línea que vuela hasta Findelatierra, mientras que cada una de las ciudades restantes tiene veinte líneas alfómbricas. Demuestra que se puede viajar desde la capital hasta Findelatierra (quizá haciendo transbordo).
18.- ¿Se pueden dibujar los grafos de la figura 3 sin levantar el lápiz del papel y trazando cada línea exactamente una vez?
19.- En la figura 4 aparece el mapa de la ciudad de Königsburg. La ciudad se extiende en ambas orillas de un río en el que hay dos islas. Hay siete puentes que conectan distintas partes de la ciudad. ¿Se puede pasear por la ciudad de manera que se crucen todos los puentes exactamente una vez cada uno?
20.- Un trozo de alambre tiene 120 cm de longitud. ¿Se puede construir con él un cubo de 10 cm de lado simplemente doblándolo? ¿Cuál es el número mínimo de cortes que tendremos que hacer en el alambre para conseguir construir el cubo?





La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal