7 votos

$n$ ciudades con dos formas

Tenemos $n$ ciudades. Cualquiera de las dos ciudades a y B de ellos, se puede viajar de a a B y de B a a por el coche o en avión [Pero no es exactamente una forma, no se puede viajar de a a B, tanto en coche o en avión]. Hay al menos un par de ciudades (a,B), por lo que se puede viajar de uno a otro en avión y hay al menos un par de ciudades (C,D) de modo que usted puede viajar de uno a otro en coche.

La cuestión es que: Demostrar que podemos eliminar una de tales formas de transporte: en coche o en avión, por lo que para cualquiera de las dos ciudades,B. Usted puede viajar de a a B pasando en la mayoría de los otros dos ciudades C,D. [Si se quita coche maneras, se puede pasar de a a B pasando por las ciudades C,D en avión sólo].

Estoy realmente no tienen ideas. Por favor, dame algunas pistas. Lo siento por mi mal inglés.

5voto

Usted no puede tener $n \lt 3$ a satisfacer a la existencia de un plano de conexión directa y un coche de conexión directa.

Para $n=3$ va a tener tres conexiones en directo, dos de un tipo particular y uno de los otros. El primer tipo de conexión que conecta todas las ciudades, directamente o indirectamente.

Para $n \gt 3$, dados a y B, tome cualquiera de las otras dos ciudades. Entre estas cuatro ciudades hay seis conexiones directas. Así que al menos tres de las conexiones directas son de un tipo en particular. Este tipo particular directamente o indirectamente conecta las cuatro ciudades, excepto cuando se forma un triángulo entre los tres de ellos y el otro tipo proporciona conexiones directas entre la cuarta ciudad y los otros tres. Por lo tanto, en cada caso, las cuatro ciudades que están vinculados directamente o indirectamente por un solo tipo de conexión. Esta imagen puede ayudar cuando hay al menos tres negros conexiones en directo:

enter image description here

Así que usted puede conseguir entre dos ciudades en un solo tipo de conexión, pasando a pesar de que en la mayoría de las otras dos ciudades.

0voto

CodingBytes Puntos 102

Como entiendo la pregunta que nos tenemos un grafo completo $K_n$, cuyos bordes son de color rojo y azul. Se afirma que podemos eliminar todos los bordes de una adecuada color elegido y se quedan con una gráfica conectada en $n$ vértices. (La frase es aún más fuerte, pero no voy a entrar en eso).

La afirmación es verdadera para $n=3$, y para todos los $n$ en el caso especial en que un color que falta en el principio. Supongamos que el enunciado es cierto para algunos $n\geq3$, y que nos dan un color $K_{n+1}$. Si hay dos bordes con diferentes colores que usted puede encontrar un vértice $v_0$ que es incidente con los dos bordes de diferentes colores. Denotar por $K_n'$ el color completar el gráfico resultante de la extracción $v_0$, y el incidente de los bordes, y aplicar la hipótesis de inducción a $K_n'$. Si, por ejemplo, los bordes rojos puede ser removido de $K_n'$ dejando un grafo conexo, re-lindan $v_0$, así como el azul de bordes con $v_0$ como un extremo, y obtener un conectada "blue" en el gráfico de $n+1$ vértices.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X