1r ciclo ¿Máximo número de intersecciones entre rectas (o ejes en un grafo)?

[skan]

Buenas.


Si dibujo un grafo con N nodos y E ejes (que unen pares de nodos aleatoriamente escogidos, entre dos nodos sólo puede haber o 0 o 1 ejes)...


¿Cuál es el máximo número posible de intersecciones entre ejes? ¿O la media esperada del número de intersecciones?


Lo podríamos preguntar como puntos, rectas e intersecciones.

[Richard R Richard]

Re: ¿Máximo número de intersecciones entre rectas (o ejes en un grafo)?

Para mi en una respuesta rápida de los datos que aportas veo que solo puedes tener un número entero de ejes menor que $E\leqslant\dfrac N2$

si supones que el primer eje que dibujas no intersecta a nada (pues no hay nada dibujado)
el segundo intersecta solo al primero,
el tercero a los dos anteriores, y asi sucesivamente

el número máximo lo da la serie $X=\dst\sum_{i=1}^{E-1} i$

Saludos

[skan]

Re: ¿Máximo número de intersecciones entre rectas (o ejes en un grafo)?

Para mi en una respuesta rápida de los datos que aportas veo que solo puedes tener un número entero de ejes menor que $E\leqslant\dfrac N2$

si supones que el primer eje que dibujas no intersecta a nada (pues no hay nada dibujado)
el segundo intersecta solo al primero,
el tercero a los dos anteriores, y asi sucesivamente

el número máximo lo da la serie $X=\dst\sum_{i=1}^{E-1} i$

Saludos

He hecho un esquema con 1, 2 y 3 nodos.
Número máximo de ejes 1,3 y 6 respectivamente.
Número de cruces 0,0 y 1.

[Richard R Richard]

Re: ¿Máximo número de intersecciones entre rectas (o ejes en un grafo)?

Si dibujo un grafo con N nodos y E ejes (que unen pares de nodos aleatoriamente escogidos, entre dos nodos sólo puede haber o 0 o 1 ejes)...


¿

[ATTACH=CONFIG]12914[/ATTACH]

he malinterpretado tu enunciado, pensé que en cada uno de los nodos solo podia salir o bien ninguno o 1 solo eje,hasta otro nodo , la primer figura lo cumple la segunda no, por lo que te dicho no sirve para lo que planteas , le dare un nuevo vistazo para ver si te puedo ayudar...

n	e	cruces
2	1	0
3	3	0
4	6	1
5	10	5
6	15	15
7	21	35
8	$\dst\sum_{i=2}^n (i-1)=28$	64?????

[carroza]

Re: ¿Máximo número de intersecciones entre rectas (o ejes en un grafo)?

Hola.

Hay una forma facil de resolver este problema.

Si tienes N puntos, el numero de "ejes", es igual al numero de pares de puntos, que es $e= N(N-1)/2$.

Ni tienes N puntos, el numero (máximo) de cruces es igual al numero de grupos de cuatro puntos. Esto podemos visualizarlo imaginando que en un "cruce", como en un cruce de carreteras, habrá señales indicando los cuatro "puntos" (cuatro pueblos) a los que se puede ir desde el cruce.

El numero de grupos de 4 puntos, sobre un total de N puntos, es igual a combinaciones de N tomados de 4 en cuatro, o sea, $c=N(N-1)(N-2)(N-3)/24$.

Segun esto, el numero de cruces entre 8 puntos es 70. El resto de los valores de la tabla de R3 son correctos.

Saludos

[skan]

Re: ¿Máximo número de intersecciones entre rectas (o ejes en un grafo)?

Si tienes N puntos, el numero (máximo) de cruces es igual al numero de grupos de cuatro puntos. Esto podemos visualizarlo imaginando que en un "cruce", como en un cruce de carreteras, habrá señales indicando los cuatro "puntos" (cuatro pueblos) a los que se puede ir desde el cruce.

El numero de grupos de 4 puntos, sobre un total de N puntos, es igual a combinaciones de N tomados de 4 en cuatro, o sea, $c=N(N-1)(N-2)(N-3)/24$.

¿Podrías explicar como has deducido esto?

[Richard R Richard]

Re: ¿Máximo número de intersecciones entre rectas (o ejes en un grafo)?

Carroza lleva la razón, yo a 64 llegué tirando líneas en lápiz y papel

la forma de obtener un cruce es seleccionando 4 puntos al azar, de los N que hay , y trazar dos rectas cruzadas obteniendo un cruce, así el problema se convierte en uno de hallar cuantos subgrupos de 4 puntos distintos se pueden hallar entre N puntos

y ese numero es el combinatorio de N y 4

en general seria $\dst{N\choose k} = \frac{N!}{k!(N-k)!}$

y para este caso $\dst{N\choose 4} = \frac{N!}{4!(N-4)!}=N(N-1)(N-2)(N-3)/24$


así para 8 el número de cruces es $\dst{8\choose 4} = \frac{8!}{4!(8-4)!}=70$

puedes seguir para 9 sera 126......


el siguiente numero de cruces lo puedes sacar multiplicando el número de cruces anterior por $\dfrac{N}{N-4}$


si vamos al $N=10$ entonces

$x_{(10)}=x_{(9)}\dfrac{10}{10-4}=126 \dfrac{10}{6}=210$


Saludos