6.4.2. PROPIEDADES DEL ÁRBOL

09.12.2015 16:16

 

Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto numerable de vértices es además un grafo plano. Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G. Dado n vértices etiquetados, hay n n-2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d1, d2,..., dn es: un coeficiente multinomial.