G-Fact 20 (fórmula de Cayley para el número de árboles etiquetados)

Considere las siguientes preguntas.

  1. ¿Cuántos árboles de expansión puede haber en un gráfico completo con n vértices?
  2. ¿Cuántos árboles etiquetados (tenga en cuenta árboles, no árboles binarios) puede haber allí con n vértices?

La respuesta es la misma para ambas preguntas.

Para n = 2, hay 1 árbol.

Para n = 3, hay 3 árboles.

Para n = 4, hay 16 árboles

CayleysForumula


La fórmula establece que para un entero positivo n, el número de árboles en n vértices etiquetados es n n-2

Fuente:
https://en.wikipedia.org/wiki/Cayley%27s_formula

Este artículo es una contribución de Vaibhav Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *