Autor Tema: Subgrafos posibles

0 Usuarios y 1 Visitante están viendo este tema.

28 Agosto, 2020, 06:10 am
Leído 463 veces

Kosiago

  • $$\Large \color{red}\pi$$
  • Mensajes: 2
  • País: mx
  • Karma: +0/-0
Necesito ayuda con este ejercicio, espero que me puedan ayudar me he dado de topes para resolverlo

¿Cuántas subgráficas tiene \( K_{10} \)?.

Para realizar este conteo recuerda que \( K_{10} \) es la gráfica completa con \( 10 \) vértices. Toma en cuenta que debes contar todas las sub-gráficas distintas como conjuntos (aunque sean isomorfas); las sub-gráficas pueden ser disconexas. Tienes que anotar todos los pasos de tu conteo.

28 Agosto, 2020, 08:30 pm
Respuesta #1

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

¿Cuántas subgráficas tiene \( K_{10} \)?.

Para realizar este conteo recuerda que \( K_{10} \) es la gráfica completa con \( 10 \) vértices. Toma en cuenta que debes contar todas las sub-gráficas distintas como conjuntos (aunque sean isomorfas); las sub-gráficas pueden ser disconexas. Tienes que anotar todos los pasos de tu conteo.

De \( K_{10} \) se pueden escoger \( n \) vértices de \[ \binom{10}{n} \] formas diferentes ya que se trata de una combinación.

Los \( n \) vértices se pueden unir mediante \[ \binom{n} {2} \] aristas diferentes, otra combinación, los 10 vértices tomados de 2 en 2, ya que una artista une dos vértices de los \( n \) disponibles.

Cada una de las  \[ \binom{n} {2} \] aristas puede aparecer o no en el subgrafo (variación con repetición), luego se pueden obtener \[ 2^  {\binom{n} {2}}
   \] subgrafos de n vértices...

Intenta acabar tú. O vuelve a insistir.

Un saludo.

28 Agosto, 2020, 09:52 pm
Respuesta #2

Kosiago

  • $$\Large \color{red}\pi$$
  • Mensajes: 2
  • País: mx
  • Karma: +0/-0
Entiendo lo que me explicas, pero no sé me queda del todo claro, podrías ayudarme con el ejemplo para K3?

28 Agosto, 2020, 10:43 pm
Respuesta #3

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
En \[ K_3 \] puedes encontrar subgrafos de \( 0,1,2 \) ó \( 3 \) vértices.

Subgrafos de cero vértices hay \[ \binom{3}{0}=1 \]. No se pueden añadir aristas.

De un vértice hay \[ \binom{3}{1}=3 \]. A ninguno de ellos se les puede añadir aristas.

Dos vértices se pueden escoger de \[ \binom{3}{2}=3 \] formas diferentes. Para cada una de ellas se puede añadir o no \[ \binom{2}{2}=1 \] artista, es decir que por cada par de vértices habrá \[ 2^{1}=2 \] subgrafos distintos. Lo que quiere decir \[ 3\cdot{2=6} \]subgrafos de dos vértices.

Por último, tres vértices se pueden escoger de \[ \binom{3}{3}=1 \] formas, se pueden añadir o no \[ \binom{3}{2}=3 \] aristas, lo que da lugar a \[ 1\cdot{2^3}=8 \] subgrafos de 3 vértices.

En total \[ 8+6+3+1=18 \]

Espero que te sirva. Un saludo.