En la wikipedia se da el algoritmo FKT para grafos planos. No hay nada para grafos completos. Necesito encontrar el número de coincidencias perfectas en el grafo completo de seis vértices.
Es sólo el número de formas de dividir los seis vértices en tres conjuntos de dos vértices cada uno, ¿no? Así que son 15; el vértice 1 puede ir con cualquiera de los otros 5, luego elige uno de los 4 restantes, puede ir con cualquiera de los otros tres, luego no hay más opciones que hacer. $5\times3=15$ .
Nota al margen. Para un gráfico general completo sobre $2n$ vértices, este número resulta ser $\frac{(2n)!}{n! 2^{n}}$ .
Si sólo quiere obtener el número de coincidencias perfectas, utilice la fórmula $\dfrac{(2n)!}{2^n\cdot n!}$ donde $2n =$ número de vértices en el gráfico completo.
Explicación detallada:- Debes entender que tenemos que hacer n conjuntos diferentes de dos vértices cada uno.
Tomemos primero un vértice . Ahora tenemos (2n-1) formas de seleccionar otro vértice para hacer el par. Ahora para hacer otro par tomamos un vértice y ahora tenemos (2n-3) formas de seleccionar otro vértice. Esto se debe a que ya hemos utilizado 2 vértices en el primer par y un vértice está actualmente en uso para hacer el segundo par. Del mismo modo, para el tercer par tendremos (2n-5) formas. Cuando hagamos el enésimo par sólo tendremos una forma.
Multiplicando todo obtenemos (2n-1) (2n-3) ........... 1 Ahora multiplícalo y divídelo por los términos pares de la siguiente manera ((2n) (2n-1) (2n-2) (2n-3) ..................1)/((2n) (2n-2)(2n-4).....*2)
ahora el numerador se convertirá en (2n)! y toma 2 comunes de cada término en el denominador . Obtendrás 2^n * (n*(n-1) (n-2) .......1) ¡Por lo tanto, el denominador se convertirá en 2^n * n! por lo que obtenemos la fórmula como (2n)/(2^n*n!). Espero que esto ayude.
Para un emparejamiento perfecto, el número de vértices del grafo completo debe ser par.
Para un grafo completo con n vértices (donde n es par), el número de coincidencias perfectas es $\frac{n!}{(2!)^{n/2}(n/2)!}$ Para $n=2m$ Es decir, es $\frac{(2m)!}{(2!)^m m!}$
Utilizando esta fórmula para n=6, el número de particiones = 15
Explicación:
Este problema es básicamente el de encontrar el número de particiones "desordenadas" de un conjunto .
Para dividir un conjunto de n elementos en r particiones desordenadas de tamaño $n_1, n_2, n_3, ... , n_r$ la fórmula es $\frac{n!}{n_1!n_2!...n_r!r!}$
Para la pregunta dada debemos particionar un conjunto de tamaño $2m$ en $m$ particiones desordenadas de tamaño 2 cada una, es decir $ \quad n=2m; \quad n_1=n_2=...=n_r=2; \quad r=m$
Así que el resultado es: $\frac{(2m)!}{2!2!...(m-times)m!} = \frac{(2m)!}{(2!)^m m!}$
Para más información sobre este tema: https://www3.nd.edu/~dgalvin1/10120/10120_S16/Topic07_6p7_Galvin.pdf
Este problema es equivalente a encontrar un conjunto de $n$ pares disjuntos. Digamos que hay $2n$ vértices entonces $\frac{2n}{2^n}$ es el número de formas en que se pueden tener estos $n$ es decir, formas de hacer pares disjuntos a partir de ellos. Por ejemplo, si tienes vértices $1,2,3,4$ entonces una de las posibles formas de hacer set fuera de esto sería $\{(1,2),(3,4)\}$ . Finalmente, como el conjunto es una colección desordenada, la solución final es $\frac{2n}{2^n*n!}$ .
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.
3 votos
Aquí hay una forma alternativa de hacer esto a través de la recursión. Dejemos que $a_n$ denotan el número de coincidencias perfectas en $K_{2n}$ . Entonces, claramente, $a_1 = 1$ . Ahora en $K_{2n}$ (donde $n \geq 2$ ), elija cualquier vértice $u$ puede coincidir con $(2n-1)$ vértices. Después de emparejar $u$ , te quedas con $2n-2$ vértices. Así, $a_n = (2n-1)a_{n-1}$ . Así que, $a_n = (2n-1)(2n-3)\dots(1)$ .
0 votos
Esto también se llama doble factorial : $a_n=(2n-1)!!$