Anuncio

Colapsar
No hay ningún anuncio todavía.

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

Colapsar
X
 
  • Filtro
  • Hora
  • Mostrar
Borrar todo
nuevos mensajes

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

    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.
    Última edición por skan; 18/11/2017, 21:47:28.

  • #2
    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

    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

    Saludos

    Comentario


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

      Escrito por Richard R Richard Ver mensaje
      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

      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

      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.
      Haz clic en la imagen para ampliar

Nombre:	QJzARU8.png
Vitas:	1
Tamaño:	12,2 KB
ID:	303967

      Comentario


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

        Escrito por skan Ver mensaje


        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)...


        ¿
        Escrito por skan Ver mensaje
        [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 64?????
        Última edición por Richard R Richard; 20/11/2017, 00:56:55.

        Comentario


        • #5
          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 .

          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, .

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

          Saludos
          Última edición por carroza; 20/11/2017, 09:08:42.

          Comentario


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

            Escrito por carroza Ver mensaje
            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, .
            ¿Podrías explicar como has deducido esto?

            Comentario


            • #7
              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

              y para este caso


              así para 8 el número de cruces es

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


              el siguiente numero de cruces lo puedes sacar multiplicando el número de cruces anterior por


              si vamos al entonces




              Saludos
              Última edición por Richard R Richard; 20/11/2017, 19:30:56. Motivo: ortografia

              Comentario

              Contenido relacionado

              Colapsar

              Trabajando...
              X