Tamanho da fonte: 

Ao querer modelar o modo como objetos estão ou não conectados entre si, nos deparamos com alguns tipos de padrões comuns em diferentes tipos de problema. A Teoria dos Grafos é o ramo da matemática que abstrai essa ideia em comum por trás desses problemas e a partir disso estuda as relações existentes entre objetos. Exemplos comuns de problemas associados à Teoria dos Grafos são: as relações de amizade em redes sociais como o Facebook, comunicação entre torres de rádio, gerenciamento de fronteiras de estados em países, estratégias de vacinação para a prevenção de doenças contagiosas, estabelecimento de redes inteligentes de conexão entre computadores, elaboração de percurso de menor custo para a realização de entregas, etc. Por trás de todos esses problemas, existe o que chamamos de grafos. Um grafo é uma estrutura algébrica composta por um conjunto finito cujos elementos são chamados de vértices, denotado por V, e outro conjunto cujos elementos são chamados de arestas, que são pares não ordenados de vértices, denotado por E. A existência ou não de um par de vértices de V como uma aresta em E é o que determina a existência ou não de conexão entre os vértices desse par. Um chamado desenho de um grafo é a forma mais comum de se representar e estudar grafos, onde os vértices são representados por pontos e as arestas são representadas por linhas que ligam pares de vértices. Existem diversas maneiras de desenhar um mesmo grafo, e existem propriedades de grafos que dependem da possibilidade ou não de desenhar um grafo satisfazendo uma certa característica. Além de grafos na sua maneira tradicional, como foi definido, existem outras vertentes de grafos que surgiram devido à adaptação desse conceito a outros tipos de problemas. Por exemplo, no Facebook, poderíamos representar os usuários como vértices, e então conectar dois vértices por uma aresta, se esses são amigos na rede. Porém, no Instagram é permitido que um usuário A siga outro usuário B, sem que o usuário B siga o usuário A. Esse tipo de rede pode ser representada por um grafo se considerarmos que as arestas são pares ordenados (ao invés de não ordenados) de vértices, atribuindo assim uma orientação para cada aresta, ou seja, dizendo que um vértice x pode estar relacionado a um vértice y sem que y esteja relacionado com x, e nesse caso estaremos falando de um digrafo. Ao considerarmos que as arestas podem ser formadas por dois vértices iguais, estaremos permitindo a presença dos chamados loopings, isto é, um vértice que está conectado a ele mesmo. Se for possível que as arestas conectem mais do que dois vértices, então estaremos falando de um hipergrafo, sendo que se todas as arestas tiverem um mesmo tamanho, estamos, além disso, falando de um hipergrafo uniforme. Diversos grafos clássicos aparecem com frequência na modelagem de vários tipos de problemas e, por isso, recebem nomes especiais. Chamamos de caminho, um grafo cujos vértices possuem um ordenamento de modo que o primeiro está conectado ao segundo, que está conectado ao terceiro, que está conectado ao quarto, e assim por diante até o último. Ao adicionarmos uma aresta conectando o último vértice ao primeiro em um caminho estaremos falando então de um ciclo. O grafo completo é aquele em que quaisquer dois de seus vértices constituem uma aresta, enquanto que o grafo vazio não possui arestas. Além de grafos frequentes existem também propriedades muito conhecidas e recorrentes, o que permite a divisão dos grafos por classes. Um grafo é bipartido se for possível particionar seu conjunto de vértices em dois subconjuntos de modo que não existe aresta conectando vértices de um mesmo subconjunto. Um grafo é conexo se quaisquer dois de seus vértices são extremidades de um caminho. Um grafo é planar se existir um desenho do grafo em que não há cruzamento de arestas. Para todas essas classes de grafos mencionadas, diversos resultados são bem conhecidos e respondem muitas das questões relacionadas aos problemas descritos anteriormente. Já são sabidas, por exemplo, as condições necessárias e suficientes para que um grafo seja planar. Apesar da imensa quantidade de resultados já estudados na Teoria dos Grafos, ainda há muitos problemas em aberto a serem investigados, o que faz com que essa seja uma área que ainda está em grande crescimento no meio científico.

Grafos; Modelagem; Planaridade; Aplicação; Redes.