Metraipolis › archive › dc_66cf642c8575
Enumeración de grafos — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Enumeraci%C3%B3n_de_grafos
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T23:29:50.552Z
- SHA-256 of the archived text
c2436c823a70502740a1061665e19d498aa3168a2eea6db71d4e8ac5f53f3e89- Stable URL of this page
https://metraipolis.com/documento/dc_66cf642c8575
How to cite
Enumeración de grafos — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Enumeraci%C3%B3n_de_grafos (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_66cf642c8575 (Metraipolis archive dc_66cf642c8575, sha256 c2436c823a70502740a1061665e19d498aa3168a2eea6db71d4e8ac5f53f3e89)
BibTeX
@misc{dc66cf642c8575,
title = {Enumeración de grafos — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Enumeraci%C3%B3n_de_grafos},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_66cf642c8575; sha256 c2436c823a70502740a1061665e19d498aa3168a2eea6db71d4e8ac5f53f3e89},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Enumeraci%C3%B3n_de_grafos. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. 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. Algunos resultados importantes en esta área: El número de grafos no dirigidos con n vértices etiquetados es 2n(n − 1)/2. El número de grafos dirigidos con n vértices etiquetados es 2n(n − 1). El número Cn de grafos conectados no dirigidos de n vértices etiquetados satisface la relación de recurrencia C n = 2 ( n 2 ) − 1 n ∑ k = 1 n − 1 k ( n k ) 2 ( n − k 2 ) C k . {\displaystyle 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 ⌊ ( n − 4 ) / 2 ⌋ . {\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»).
Fonte: Wikipedia in spagnolo, voce «Enumeración de grafos» — https://es.wikipedia.org/wiki/Enumeraci%C3%B3n_de_grafos
Wikidata Q5597086 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5597086
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Enumeraci%C3%B3n_de_grafos?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 146032718, consultata il 2026-10-07T23:08:54.912Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f5c4ec17b8682186132ff34e735a1e955ae978781f0b61460eb78a5c507043fe