Produção Nacional
Introdução à Teoria dos Grafos
2019; Éditions Mélanie Seteun; Linguagem: Português
ISSN
2117-4148
Autores Tópico(s)Linguistics and Education Research
ResumoA Teoria dos Grafos e a area da matematica que estuda as relacoes entre objetos, ou seja, e atraves desse ramo que abstraimos a ideia comum existente por tras de problemas como, por exemplo, gerenciar as fronteiras de regioes em mapas, estabelecer uma comunicacao eficiente entre torres de radio, determinar os elementos de uma populacao de pessoas para serem vacinados contra uma doenca contagiosa, descobrir o trajeto mais curto para realizar diversas entregas, estudar o alcance de uma noticia atraves das relacoes de amizade em redes sociais como o Facebook, criar uma rede inteligente de conexao entre computadores, dentre varios outros exemplos. A ideia existente por tras de todas essas relacoes e formalizada atraves do que chamamos de grafos. Um grafo e uma estrutura algebrica formada por dois conjuntos, sendo um desses chamado de conjunto de vertices do grafo, denotado por V, e o outro chamado de conjunto de arestas do grafo, denotado por E. Para determinarmos um grafo G = (V, E) e necessario que o conjunto de arestas E esteja contido no conjunto formado pelos pares nao ordenados de V, ou seja, uma aresta e um par nao ordenado de vertices. Tal maneira de construir arestas e justamente o que estabelece se dois vertices de V estao ou nao relacionados entre si. E muito comum que os grafos sejam representados de maneira grafica, ou seja, por meio de uma ilustracao (desenho) em um plano no qual os vertices de V sao representados por pontos e as arestas de E sao representadas por linhas que ligam ou nao pares de pontos. Tal ilustracao e chamada de desenho do grafo. Devido a existencia de redes de conexao mais elaboradas, outras vertentes de grafos surgiram. Ao considerarmos as arestas como sendo pares ordenados ao inves de nao ordenados, estamos informando que cada aresta possui uma orientacao, dizendo assim que um vertice x pode estar relacionado a um vertice y sem que y esteja relacionado com x, e nesse caso estaremos falando de um digrafo. Se permitirmos que as arestas sejam formadas por dois vertices iguais, entao estaremos permitindo o que e chamado de looping, ou seja, um vertice que esta relacionado com ele mesmo. Se as arestas conectarem mais vertices, como cinco ou oito, entao estaremos falando de um hipergrafo. Existem diversos grafos que, por estarem presentes na construcao e resolucao de diversos problemas, recebem um nome e uma notacao especial. A seguir alguns exemplos de grafos bem conhecidos serao descritos. E chamado de caminho um grafo cujos vertices podem ser enumerados de modo que o primeiro esta conectado ao segundo, que esta conectado ao terceiro, que esta conectado ao quarto, e assim por diante ate o ultimo. Se em um caminho adicionarmos uma aresta conectando o ultimo vertice ao primeiro, entao o grafo obtido e chamado de ciclo. Chamamos de grafo completo aquele em que quaisquer dois de seus vertices constituem uma aresta. Alem de grafos muito conhecidos, ha tambem algumas classificacoes importantes que sao consideradas em grafos. Dizemos que um grafo e bipartido se for possivel particionar seu conjunto de vertices em duas classes de modo que dois vertices de mesma classe nunca formem uma aresta. Dizemos que um grafo e planar se for possivel estabelecer um desenho do grafo sem que arestas se cruzem. Classificamos um grafo como conexo quando quaisquer dois de seus vertices sao extremidades de um caminho, que conecta esses dois vertices. Diversos resultados sao bem conhecidos em grafos e respondem muitas das questoes envolvendo os problemas descritos acima. Sao conhecidas, por exemplo, as condicoes necessarias e suficientes para um grafo ser planar, ou para ser possivel percorrer os vertices do grafo sem repetir aresta. Ja se sabe tambem qual e o numero minimo de vertices que deve ser removido de um grafo para desconecta-lo. Apesar dos muitos resultados existentes, a Teoria dos Grafos e uma area que ainda esta em grande crescimento no meio cientifico, tendo assim muitos problemas em aberto a serem investigados.
Referência(s)