grupos de puntos, Resuelto por xsebastian [medio] Opciones

[?????????]

hay 2 grupos de 3 puntos A, B, C y D, E, F. se debe unir cada punto solo con cada punto del otro grupo. probar que al menos un par de lineas se cruza.

nota: dados los 6 puntos pueden elegirse arbitrariamente los puntos que pertenecen a cada grupo

[Corecrasher]

mmm , compadre lea la seccion antes de postear po

[Rurouni Kenshin]

Tema Movido
Ahora esta en problemas propuestos...pues los problemas resueltos solo pueden estar ahi cuando uno de los moderadores lo transporta a ese sector...
Saludos y bienvenido....
PD:Registrate para que sepamos quien eres y tengas las ventajas de un usuario registrado...

[S. E. Puelma Moy...]

Esto tiene relación con la teoría de grafos. Tenemos seis "vértices", y las líneas se llaman habitualmente "arcos" o "aristas". Vamos a suponer que es posible construir un grafo plano. Debemos llegar a una contradicción, para lo cual es necesario revisar algunas cosas, previamente:

Aclaramos que un "grafo" es un conjunto finito de vértices y algunas aristas, que unen pares de vértices. Se dice que el grafo es "plano" si puede ser representado en un plano, donde las aristas no se intersecan. Cuando tenemos un grafo plano, las aristas delimitan regiones bidimensionales en el plano, que llamamos "caras". Se incluye una cara no acotada...

Fórmula de Euler: Si un grafo plano (conexo, como idea intuitiva) tiene "c" caras, "v" vértices y "a" aristas, entonces c-a+v=2

Lo que nosotros estamos suponiendo, es que tenemos un cierto grafo plano, y parte de la información es que a=9, v=6. De allí se deduce que c=5.

Otro concepto de teoría de grafos (tomo el nombre en inglés, porque no conozco equivalente en español) es el "girth" de un grafo. Este número, que denotaremos por "g", es la longitud del ciclo (o circuito) más corto de un grafo.

Nuevamente, como en casi toda la teoría de grafos, los muchos conceptos tienen nombres sugerentes. Por ejemplo, si tengo vértices a, b, c, y tengo aristas ab, bc, ca (o sea la notación xy es para una arista que une los vértices "x" e "y") entonces se produce un ciclo de longitud (o largo) 3, que a veces se denomina "triángulo"

Un argumento de conteo nos permite concluir que, si las caras son F(1),...,F©, rodeadas de e(1),...,e© aristas (respectivamente), entonces e(1)+...+e©=2a. La razón es porque cuando contamos las aristas, cara por cara, estamos contabilizando dos veces cada una.

En nuestro ejemplo: e(1)+e(2)+e(3)+e(4)+e(5)=18. De aquí es evidente que el girth es menor o igual que 3 (g<3). Pero en la definición de un ciclo, éste debe tener al menos tres vértices (y tres aristas obvio), porque están prohibidas dos o más aristas entre cada par de vértices. Luego g=3

Esto quiere decir que se produce un triángulo en un grafo bipartido. Nuestro grafo se denomina así, porque podemos dividir los vértices en dos grupos, y todas las aristas van desde un vértice de un grupo, hacia un vértice del otro grupo. Los grafos bipartidos no tienen triángulos, porque sus vértices deben ir alternando de grupo, y con tres transiciones regresamos al mismo grupo... eso es imposible...

Bueno, la solución es esa, conviene interiorizarse un poco con teoría de grafos para entenderlo mejor. Como sé que no me he expresado bien, prometo editar esta solución para hacerla entendible... pero avísenme para recordar esta promesa

[El Geek]

El grafo que se obtiene al unir los puntos, es un , quien por teorema de kuratoswki es no planar (es decir, que al dibujarse, sus líneas se cruzan).

PD: usando el teorema de kuratowski con el grafo de kuratowski, nice.

Mensaje modificado por El Geek el Aug 6 2012, 10:42 PM