Enumeración de grafos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
La lista completa de todos los árboles libres en los vértices 2,3,4: 2^{2-2}=1 árbol con 2 vércies, 3^{3-2}=3 árboles con 3 vértices y 4^{4-2}=16 árboles con 4 vértices.

En la teoría de combinatoria, un área de las matemáticas, la enumeración de grafos describe una clase de problemas de enumeración combinatoria en la que se debe contar grafos dirigidos o no dirigidos de un tipo determinado, usualmente como función del número de vértices del grafo.[1] Los pioneros en esta área de las matemáticas fueron Pólya, Cayley y Redfield.

En ciertos problemas de enumeración de grafos se consideran a los vértices del grafo como etiquetados de tal manera que se distingan entre sí mientras que en otros problemas cualquier permutación de los vértices se considera parte del mismo grafo. En general, los problemas etiquetados tienden a ser de más fácil resolución que los problemas no etiquetados.[2]

Algunos resultados importantes en esta área:

  • El número de grafos no dirigidos con n vértices etiquetados es 2n(n − 1)/2.[3]
  • El número de grafos dirigidos con n vértices etiquetados es 2n(n − 1).[4]
  • El número Cn de grafos conectados no dirigidos de n vértices etiquetados satisface la relación de recurrencia[5]
C_n=2^{n\choose 2} - \frac{1}{n}\sum_{k=1}^{n-1} k{n\choose k} 2^{n-k\choose 2} C_k.
de lo que se puede calcular con facilidad, para n = 1, 2, 3, ..., que los valores para Cn son
1, 1, 4, 38, 728, 26704, 1866256, ...(sucesión A001187 en OEIS)
  • El número de árboles libres con n vértices etiquetados es nn − 2 (Fórmula de Cayley).
  • El número de caterpilars de n vértices no etiquetadas es
2^{n-4}+2^{\lfloor (n-4)/2\rfloor}.


Referencias[editar]

  1. Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. Academic Press . ISBN 0-12-324245-2
  2. Harary and Palmer, p. 1.
  3. Harary and Palmer, p. 3.
  4. Harary and Palmer, p. 5.
  5. Harary and Palmer, p. 7.