Hay un rompecabezas donde usted tiene 3 casas y 3 los servicios públicos. Usted debe dibujar líneas, de modo que cada casa está conectada a las tres utilidades, pero las líneas no se superponen. Sin embargo, estoy bastante seguro de que el rompecabezas es imposible. Cómo es esto resultó?
Respuestas
¿Demasiados anuncios?
Oliver Nelson
Puntos
176
Como otros han señalado, usted está tratando de encontrar una representación planar de la completa bipartito gráfico de $K_{3,3}$ y aunque hay muchas pruebas de que esto no es posible, hay uno que me parece especialmente cuidada.
Vamos a confiar en los resultados siguientes:
$v-e+f=2$ para todos los grafos planares (ver aquí)
bipartito gráficos sólo contienen ciclos de longitud (ver aquí).
Prueba: Vamos a $G$ ser un plano gráfico de tal manera que cada ciclo en $G$ está a menos de longitud 4. Ahora, cada cara es simplemente un ciclo y ya que cada ciclo tiene al menos 4 bordes podemos establecer que $$\frac{4f}{2}\le e$$ mientras que dividir por dos para evitar la doble contabilización (cada borde pertenecen a dos caras). Reordenando obtenemos $$f\le\frac12 e$$ Ahora podemos utilizar la fórmula de Euler para llegar a una desigualdad que debe ser satisfecha para todos los grafos planares con ciclos de longitud de al menos la longitud de 4. $$\begin{align*} 2=v-e+f&\le v-e+\frac12e=v-\frac12e\\ \implies 2&\le v-\frac12e \\ \implies e&\le 2v-4 \quad (\spadesuit) \end{align*}$$ Ahora, en cualquier gráfico, los ciclos pueden ser no menor de longitud 3 (esto se deduce de la definición de un ciclo). Sin embargo, desde la $K_{3,3}$ es bipartita de cada ciclo es aún y así, cada ciclo es, al menos, de longitud 4$^*$. Por lo tanto, podemos utilizar ($\spadesuit$) para ver si $K_{3,3}$ es plana o no. $K_{3,3}$ tiene 6 vértices y 9 bordes y así: $$9\nleq2(6)-4=8$$ No cumple con la desigualdad y por lo $K_{3,3}$ no puede ser plana. Tenga en cuenta que esta muestra qué es tan especial acerca de que la última de alambre. Si sólo tiene 8 cables de la desigualdad estaría satisfecho $$8\le2(6)-4=8$$
$^*$-Nota de este problema en realidad se puede comprobar esto por ti mismo por contar cuántas aristas de cada ciclo en $K_{3,3}$.
No es difícil ver que esto es imposible. Conectar dos casas para los tres servicios públicos, y cuya esencia es la de un cuadrado con una diagonal trazada. Las dos esquinas unido son dos de las casas, las otras dos esquinas y el punto medio de la diagonal son las utilidades. (La forma real puede verse distorsionada de esto, pero es esencialmente esto).
Donde es la tercera casa? Si la casa está "fuera" de la plaza, que no se puede conectar a la empresa en el medio. Si la casa está dentro de la plaza, entonces se encuentra en uno de los dos lados de la diagonal, y por lo tanto no puede conectarse al vértice (utilidad) que es "a través" de la diagonal.
Postscript. Como Aryabhata puntos, soy implícitamente mediante el Jordán curva teorema que dice que una simple curva cerrada que divide el plano en dos regiones disjuntas, de modo que cualquier camino de unirse a un punto desde el "exterior" a un punto "dentro" de la cuenta para cruzar la frontera. Yo lo uso cuando quiero argumentar que la casa de "fuera" no se puede conectar a la utilidad de "dentro" (sin cruzar las líneas), o que no se puede pasar de un lado de la diagonal a la otra sin necesidad de cruzar la diagonal.
Fardad Pouran
Puntos
985
En el lenguaje de la Teoría de grafos, Gráfico de $K_{3,3}$ no es un plano gráfico donde $K_{m,n}$ es completa bipartito gráfico.
Definición de Grafos Planares se indica aquí .
También como se ha dicho, "Kuratowski demostrado en $1930$ que un grafo es planar si no contiene dentro de ella cualquier gráfico es un gráfico de expansión del grafo completo $K_5$ o $K_{3,3}$."
bentsai
Puntos
1886
Así, la pregunta que parece estar pidiendo una incrustación de $K_{3,3}$ en el avión. Esto es bien conocido por ser imposible. Pero, vivimos en una esfera, en lugar de un avión. Sin embargo, también es imposible en este caso, en la cual podemos visualizar el uso de la proyección estereográfica. Usted puede obtener bastante cerca, $K_{3,3} \setminus e$ es plano (es decir, eliminar un borde).
Pero... pensar fuera de la caja, hay situaciones en las que es posible:
- Vivimos en tres dimensiones, donde una incrustación de $K_{3,3}$ es fácilmente posible.
- No parece ser nada para evitar que una de las utilidades de ser también una casa. Así, en el gráfico siguiente, el rojo los vértices son servicios públicos, azul vértices son casas y el verde vértice es tanto una casa y una utilidad.
