4 votos

Conjunto mínimo de aristas.

No se le da el grafo completo $K_{n}$.

Deje $A(n,k)=$mínima (en relación a su tamaño) subconjunto de los bordes de las $K_{n}$ tales todos los $k$-camarilla tiene al menos un borde en común con este conjunto.

Encontrar la fórmula para $|A(n,k)|$

Escribí algunos ejemplos $|A(4,3)|=2$ Pero después de todo no puedo ver el patrón.

Gracias de antemano por la ayuda.

0voto

antkam Puntos 106

Oh, en realidad este es respondidas directamente por Frigyes del teorema.

El teorema se da una construcción de la $n$-gráfico de nodos, llamados el Frigyes gráfico de $T(n,k-1)$, que tiene el máximo número de aristas $B(n,k)$ bajo la restricción de que está libre de $k$-camarillas. Esto es equivalente a decir que a partir de $K_n$ tienes que eliminar (color) como muchos bordes como sea necesario para bajar a $T(n,k-1)$. La construcción es bastante fácil que usted debería ser capaz de averiguar $B(n,k)$ y, por tanto, $A(n,k) = {n \choose 2} - B(n,k)$.

i-Ciencias.com

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.

Powered by: