"Ciências Básicas para o Desenvolvimento Sustentável"
24 a 26 de outubro de 2023
Trabalho 19505
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Matemática Aplicada |
| Setor | Instituto de Ciências Exatas e Tecnológicas - Campus Rio Paranaíba |
| Bolsa | FAPEMIG |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Hellen Sara Soares |
| Orientador | VAGNER RODRIGUES DE BESSA |
| Título | Análise e aplicações: explorando a relação entre a teoria dos grafos e as matrizes |
| Resumo | Os fundamentos teóricos deste trabalho foram construídos a partir de uma revisão bibliográfica sobre a teoria dos grafos e conceitos de álgebra linear. A teoria dos grafos é um campo da matemática dedicado ao estudo das propriedades e relações entre estruturas chamadas grafos. Um grafo G é um conjunto não vazio, definido por uma tripla de objetos (V(G), E(G), f), em que V(G) (conjunto não vazio) e E(G) são denominados os conjuntos de vértices e arestas, respectivamente, de forma que o grafo G consiste da união disjunta de V(G) e E(G). No caso em que E(G) é não vazio, existe uma aplicação f chamada função de incidência, que associa cada aresta de G a um par não ordenado de vértices. As arestas de G podem ser orientadas ou não-orientadas. Por meio dessa teoria, é possível modelar um problema, analisar a estrutura e as propriedades de um grafo, bem como desenvolver algoritmos e técnicas para responder questões relacionados à conectividade, caminhos mais curtos, fluxo em redes, otimização e muitos outras questões importantes. Neste trabalho nós estudamos a relação entre as matrizes e os grafos com objetivo de conhecer a estrutura do grafo através de sua representação matricial, sendo possível resolver problemas em estruturas gráficas complexas. Para tanto, existem duas principais formas de representar grafos por meio de matrizes: a matriz de adjacência e a matriz de incidência. A matriz de adjacência é uma matriz quadrada em que cada entrada é representada pelo número de arestas incidentes ao vértice correspondente, sendo aplicada para verificar a conectividade entre vértices e para analisar propriedades relacionadas à vizinhança de cada vértice. Utilizando a matriz de adjacência de G é nosso objetivo responder questões como: Dado um grafo simples G, qual a quantidade de árvores geradoras de G? Apresentaremos uma fórmula que calcula esse número utilizando o complemento algébrico da matriz de adjacência de G. Por sua vez, a matriz de incidência M=[a_ij] é uma matriz retangular em os elementos das colunas representam as arestas e os elementos das linhas representam os vértices do grafo. O número da posição ij da matriz M será 0 se o vértice v_i não incide a aresta e_j , 1 se o vértice v_i incide a aresta e_j (uma única vez) e 2 caso a aresta e_j seja um laço no vértice v_i. Esse formato de representação matricial nos auxilia para resolver problemas de otimização em um grafo e também será abordado neste trabalho. |
| Palavras-chave | Teoria dos grafos, matriz de adjacência, matriz de incidência. |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|