Counting of spanning trees of a complete graph
DOI:
https://doi.org/10.5902/2179460X27277Palavras-chave:
Trees, Spanning Trees, Cayley’s Formula, Complete Graphs, Inverse Process of Cayley-PruferResumo
In 1889, Arthur Cayley published an article that contained a formula for counting the spanning trees of a complete graph. This theorem says that: Let n E N and Kn the complete graph with n vertices. Then the number of spanning trees of Kn is established by n n-2: The present work is constituted by a brief literary review about the basic concepts and results of the graph theory and detailed demonstration of the Cayley’s Formula, given by the meticulous construction of a bijection between the set of the spanning trees and a special set of numeric sequences. At the end we bring an algorithm that describes a precise construction of the spanning trees obtained of Kn from Cayley-Prufer sequences.
Downloads
Referências
Abu-Sbeih, M. Z. (1990). On the number of spanning trees of Kn and Km;n. Discrete Mathematics, North-Holland, 84, 205–207.
Bondy, J. A., Murty, U. R. S. (1982). Graph theory with applications, 5o edn. New York: North Holland.
Domingues, H. H., Iezzi, G. (2003). Algebra Moderna ´ , 4o edn. Sao Paulo: Atual.
Fracasso, P. (2008). Analise de t ´ ecnicas para amostragem e sele ´ c¸ao de v ˜ ertices no planejamento probabil ´ ´ıstico de mapa de rotas. Dissertac¸ao de mestrado, Escola polit ˜ ecnica da USP. ´
Harary, F. (1969). Graph Theory, 1o edn. Menlo Park: Addison Wesley Pub. Co. Inc..
Junior, E. R. H., Nicoletti, M. C. (2006). ´ Fundamentos da teoria dos grafos para computac¸ao ˜ , 1o edn. Sao Carlos: Edufscar. ˜
Konzen, D. C. (1997). Automata and computability, 1o edn. Springer New York.
Orsini, L. Q., Consonni, D. (2002). Curso de circuitos eletricos ´ , 2o edn. Edgard Blucher Ltda. ¨
Wilson, R. J. (1996). Introduction to graph theory, 4o edn. London: Prentice-Hall.
Wu, B. Y., Chao, K. (2004). Spanning trees and optimization problems, 1o edn. Chapman & Hall/CRC Press, USA.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Para acessar a DECLARAÇÃO DE ORIGINALIDADE E EXCLUSIVIDADE E CESSÃO DE DIREITOS AUTORAIS clique aqui.
Diretrizes Éticas para Publicação de Revistas
A revista Ciência e Natura está empenhada em garantir a ética na publicação e na qualidade dos artigos.
A conformidade com padrões de comportamento ético é, portanto, esperada de todas as partes envolvidas: Autores, Editores e Revisores.
Em particular,
Autores: Os Autores devem apresentar uma discussão objetiva sobre a importância do trabalho de pesquisa, bem como detalhes e referências suficientes para permitir que outros reproduzam as experiências. Declarações fraudulentas ou intencionalmente incorretas constituem comportamento antiético e são inaceitáveis. Artigos de Revisão também devem ser objetivos, abrangentes e relatos precisos do estado da arte. Os Autores devem assegurar que seu trabalho é uma obra totalmente original, e se o trabalho e / ou palavras de outros têm sido utilizadas, isso tem sido devidamente reconhecido. O plágio em todas as suas formas constitui um comportamento publicitário não ético e é inaceitável. Submeter o mesmo manuscrito a mais de um jornal simultaneamente constitui um comportamento publicitário não ético e é inaceitável. Os Autores não devem submeter artigos que descrevam essencialmente a mesma pesquisa a mais de uma revista. O Autor correspondente deve garantir que haja um consenso total de todos os Co-autores na aprovação da versão final do artigo e sua submissão para publicação.
Editores: Os Editores devem avaliar manuscritos exclusivamente com base no seu mérito acadêmico. Um Editor não deve usar informações não publicadas na própria pesquisa do Editor sem o consentimento expresso por escrito do Autor. Os Editores devem tomar medidas de resposta razoável quando tiverem sido apresentadas queixas éticas relativas a um manuscrito submetido ou publicado.
Revisores: Todos os manuscritos recebidos para revisão devem ser tratados como documentos confidenciais. As informações ou ideias privilegiadas obtidas através da análise por pares devem ser mantidas confidenciais e não utilizadas para vantagens pessoais. As revisões devem ser conduzidas objetivamente e as observações devem ser formuladas claramente com argumentos de apoio, de modo que os Autores possam usá-los para melhorar o artigo. Qualquer Revisor selecionado que se sinta desqualificado para rever a pesquisa relatada em um manuscrito ou sabe que sua rápida revisão será impossível deve notificar o Editor e desculpar-se do processo de revisão. Os Revisores não devem considerar manuscritos nos quais tenham conflitos de interesse resultantes de relacionamentos ou conexões competitivas, colaborativas ou outras conexões com qualquer dos autores, empresas ou instituições conectadas aos documentos.
