Deje $S$ ser un conjunto de $n$ puntos en el plano, la distancia entre dos de los cuales está a más de uno. Mostrar que existen en la mayoría de las $n$ pares de puntos de $S$ a distancia exactamente uno.
Mi intento de prueba:
Construir un gráfico de $G$ que $2$ vértices son adyacentes si y sólo si su distancia es exactamente uno. A continuación, el gráfico contiene $3$ vértices en forma de triángulo equilátero ($3$ pares). No sé cómo generalizar esta.
dado un punto, donde se encuentra un punto en la distancia 1 a partir de este punto ?
considerando el grafo cuyos vértices son los puntos, y los bordes son los pares de puntos a distancia $1$, si un vértice tiene grado 3, muestran que uno de sus vecinos ha de grado uno.
una vez que usted tiene un ciclo en este gráfico, se puede tener otro ?
Si dos círculos de unidad $\mathcal{C}_1$ $\mathcal{C}_2$ se cruzan, su intersección es de dos puntos, que se encuentra en la bisectriz del segmento que une los centros de los círculos. Esta intersección se divide $\mathcal{C}_1$ en los dos arcos.El arco contenida en el lado de la bisectriz que no contiene el centro de $\mathcal{C}_1$ es más corto que un semi-círculo, y está contenida en $\mathcal{C}_2$. La intersección de a $k$ unidad de discos es una convexidad cuyo límite es de arcos de la $k$ círculos. Cada uno de estos arcos es menor que la de un semi-círculo, y nos referimos a una forma como un polyarc. Ya que los discos que se cruzan son distintos, no puede ser tangente intersecciones entre sus límites.
Por convexidad, la polyarc $\mathcal{P}$ y el círculo de $\mathcal{C}$ se intersecan en dos puntos. Si $\mathbf{p}_1$ es nuestro intersección, por la convexidad así, desde todos los rincones de la $\mathcal{P}$ están dentro de $\mathcal{C}$ la segunda intersección $\mathbf{p}_2$ se encuentra en el mismo arco como $\mathbf{p}_1$. La porción del arco entre el $\mathbf{p}_1$ $\mathbf{p}_2$ es más corto que el de un semi círculo, y por lo tanto tiene que ser la parte de el círculo de definir el arco que se encuentra dentro de $\mathcal{C}$. Por lo tanto, las dos esquinas del arco están fuera de $\mathcal{C}$, lo cual es una contradicción.
Consideremos $\mathbf{p}_0$ de valencia 3, y $\mathbf{p}_1$, $\mathbf{p}_2$ y $\mathbf{p}_3$ a sus vecinos. Wlog, $\mathbf{p}_2$ entre $\mathbf{p}_1$ $\mathbf{p}_3$ sobre el círculo centrado en $\mathbf{p}_0$. El polyarc resultante de la intersección de los discos de $\mathbf{p}_0$, $\mathbf{p}_1$ y $\mathbf{p}_3$ 3 esquinas, y $\mathbf{p}_0$ es uno de ellos. Si $\mathbf{p}_2$ tiene un prójimo $\mathbf{p}_4$, el círculo de $\mathcal{C}$ centrada en $\mathbf{p}_4$ pasa a través de $\mathbf{p}_2$ y recortes de un arco de la polyarc en este punto. En II, uno de los rincones de la polyarc se encuentra fuera del círculo, y esto no puede ser $\mathbf{p}_0$. Por lo tanto la mitad del arco que contiene $\mathbf{p}_2$ está fuera de $\mathcal{C}$, y no $\mathbf{p}_1$ o $\mathbf{p}_3$, lo cual es una contradicción.
Todos los vértices de un ciclo han de valencia, al menos 2, y por lo tanto son las esquinas de la polyarc. Además, en II, la adición de un nuevo vértice sólo puede aumentar el número de las esquinas de la polyarc por 1. Por lo tanto, la polyarc no tiene otros ángulos de los vértices del ciclo. Si un nuevo vértice $\mathbf{p}_1$ es añadido estrictamente dentro de la polyarc y tiene un prójimo $\mathbf{p}_2$, el círculo centrado en $\mathbf{p}_2$ pasando a través de $\mathbf{p}_1$ cruza la polyarc y una esquina de la polyarc está fuera de este círculo, que es una contradicción. $\mathbf{p}_1$ es, por tanto, situada en el límite de la polyarc, y una de las esquinas está entre sus vecinos. Desde las esquinas, todos tienen valencia de al menos 2, $\mathbf{p}_1$ tiene valencia 1 y no puede ser parte de un ciclo. Por lo tanto, existe un solo ciclo. Si tenemos un ciclo, de corte un borde del ciclo transforma el gráfico en un árbol que tiene al $n-1$ vértices. De lo contrario, el gráfico es un bosque y tiene menos de $n$ vértices.
Aunque esta parece ser una pregunta simple, yo no sé de un enfoque sencillo. Esto es lo mejor que me podría venir para arriba con.
Comience por la construcción de su gráfica con un borde entre 2 vértices, siempre que su distancia es de 1.
Reivindicación 1: Si dos aristas tienen distintas estaciones, a continuación, estos dos bordes deben intersectarse.
Prueba: Supongamos que no. Vamos a los extremos de ser $A, B, C, D$ donde $AB$ $CD$ son bordes. Considerar el casco convexo de estos puntos. Si uno de ellos está contenida dentro de (WLOG $A$), entonces podemos demostrar que $max(AD, AC) > AB $ lo cual es una contradicción. Por lo tanto debemos tener de 4 puntos en el casco convexo, y etiquetados en orden de las agujas del reloj (WLOG) $A, B, C, D$. Deje $AC$ $BD$ se cruzan en $X$. Entonces, por la desigualdad de triángulo, $AC + BD = XA + XC + XB + XC = (XA + XB) + (XC + XD) > 2$, lo cual es una contradicción.
Reivindicación 2: No son ni siquiera los de ciclos de longitud de al menos 4).
Prueba: Supongamos que no. Vamos a la par, ciclo dado por $v_1, v_2, \ldots v_{2n} $. Considerar la línea de $v_1 v_2$. Luego, por la reivindicación anterior, los pares y los impares vértices deben estar en diferentes lados de $v_1 v_2$, como cada consecutivos pair debe cruzan esta línea. Sin embargo, $v_1 v_{2n} $ $v_2 v_3$ no se cruzan, por lo tanto la contradicción.
Reivindicación 3: Si hay un ciclo, entonces cualquier ventaja que no está en este ciclo debe de tener un extremo que está contenido dentro de este ciclo.
Prueba: Supongamos que no, vamos a la orilla $AB$ tienen extremos que no figuran en el ciclo. Por la primera observación, cada borde del ciclo debe intersectar $AB$, por lo tanto, esta divide los vértices deben alternar por encima y por debajo de $AB$. Esto significa que el ciclo debe tener longitud, lo que se contradice con la reivindicación 2.
Reivindicación 4: no Podemos tener 2 diferentes ciclos.
Prueba: Supongamos que hacemos. Deje que el primer ciclo tienen vértices $v_1, v_2, \ldots v_{2n+1}$, y el segundo ciclo tienen vértices $s_1, s_2, \ldots s_{2m+1} $. Si cualquiera de los bordes de la 2º ciclo tiene ambos extremos en el primer ciclo, esto va a crear un ciclo, lo que se contradice con la reivindicación 2. Pero por la reivindicación 3, en menos de 1 extremo de cada borde tiene que ser en el primer ciclo. Por lo tanto, los puntos finales de la 2º ciclo alternativamente pertenecen y no pertenecen al primer ciclo. Por lo tanto, el 2º ciclo es regular, lo que es una contradicción.
Reivindicación 5: Cualquier gráfico 1 ciclo tiene en la mayoría de las $n$ bordes, donde $n$ es el número de vértices.
Prueba: Si no tiene ningún ciclo, es un árbol con el en la mayoría de las $n-1$ bordes.
Si dispone de 1 ciclo, quite 1 de los bordes, y obtenemos un árbol en la mayoría de las $n-1$ bordes. Por lo tanto la gráfica original tiene en la mayoría de las $n$ bordes.
Por lo tanto hemos terminado.
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.
