Grafos e multigrafos: o teorema da matriz-árvore

Abstract

O trabalho apresenta definições, resultados básicos e um breve histórico da Teoria de Grafos. Seu objetivo principal é demonstrar o Teorema da Matriz-Árvore de Kirchhoff para grafos e multigrafos não orientados, utilizando alguns resultados da Álgebra Linear, e demonstrar o Teorema da Matriz-Árvore de Tutte para grafos e multigrafos orientados, utilizando propriedades de determinantes e do grupo de permutações juntamente com o Princípio de Inclusão-Exclusão da Análise Combinatória. Foi realizada uma pesquisa bibliográfica, onde se destacaram os trabalhos de Abreu et al e Muldoon.