Teoria dos grafos
A teoria dos grafos ou de grafos é um ramo da matemática que estuda as relações entre os objetos pertencentes a um determinado conjunto. Para tal são utilizadas estruturas chamadas de grafos, , onde é um conjunto não vazio de objetos denominados vértices e é um subconjunto de pares não ordenados de V.
O artigo de Leonhard Euler, publicado em 1736, sobre o problema das sete pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia. Mais de um século após a publicação do artigo de Euler sobre as pontes de Königsberg e enquanto Listing introduzia o conceito de topologia, Cayley foi levado por um interesse em formas analíticas particulares decorrentes do cálculo diferencial para estudar uma classe particular de grafos, as árvores. Esse estudo teve diversas implicações na química teórica. As técnicas usadas por ele eram relacionadas a enumeração de grafos com propriedades particulares. O primeiro livro didático sobre teoria dos grafos foi escrito por Dénes König e publicado em 1936.
Imagem: liquidslave · BY-NC · Openverse
Na literatura, as definições básicas da teoria dos grafos variam bastante. Aqui estão as convenções usadas nesta enciclopédia. Um grafo direcionado (também chamado dígrafo ou quiver) consiste de Um grafo não direcionado (ou simplesmente grafo) é dado por Em um grafo ou dígrafo com pesos, uma função adicional E → R associa um valor a cada aresta, o que pode ser considerado seu "custo"; tais grafos surgem em problemas de rota ótima tais como o problema do caixeiro viajante.
Imagem: Savionasc · BY-SA · Openverse
Os grafos são geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado na aresta por uma seta. O grafo de exemplo exibido na figura é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} } (com o mapeamento w sendo a identidade). Note que essa representação gráfica não deve ser confundida com o grafo em si (a estrutura abstrata, não-gráfica). Diferentes representações gráficas podem corresponder ao mesmo grafo. O que importa é quais vértices estão conectados entre si por quantas arestas. O trabalho pioneiro de William Thomas Tutte foi de grande influência no desenho de grafos. Entre outras realizações, ele introduziu o uso de técnicas da álgebra linear para desenhar grafos.
Imagem: Cristiano Dalbem · BY · Openverse
Há diversas maneiras de armazenarmos grafos em computadores. A estrutura de dados usada dependerá tanto da estrutura do grafo quanto do algoritmo usado para manipulá-lo. Teoricamente, podemos dividir entre estruturas do tipo lista e do tipo matriz, mas em aplicações reais, a melhor estrutura é uma combinação de ambas. Estruturas do tipo lista são frequentemente usadas em grafos esparsos (grafos que possuem um pequeno número de arestas em relação ao número de vértices, oposto ao grafo denso, onde o número de arestas se aproxima do máximo de arestas possível) já que exigem menor uso da memória. Por outro lado, estruturas do tipo matriz fornecem um rápido acesso em algumas aplicações, mas podem consumir uma grande quantidade de memória. Estruturas do tipo lista incluem a lista de adjacência que associa a cada vértice do grafo uma lista de todos os outros vértices com os quais ele tem uma aresta e a lista de incidência, que armazena para cada vértice uma lista de objetos que representam as arestas incidentes a esse vértice.
Relações de incidência e de adjacência
Se uma aresta conecta dois vértices, então esses dois vértices são ditos incidentes à aresta. Usando o grafo ao lado como exemplo temos: 1 é incidente a 2 e 5, mas não é incidente a 3, 4 ou 6; 4 é incidente a 5, 3 e 6, mas não a 2 nem a 1. Dois vértices são considerados adjacentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjacentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjacentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5. Na computação, um grafo finito direcionado ou não-direcionado (com, digamos, n vértices) é geralmente representado por sua matriz de adjacência: uma matriz n-por-n cujo valor na linha i e coluna j fornece o número de arestas do i-ésimo ao j-ésimo vértices.
Valência (Grau)
A valência (ou grau) de um vértice é o número de arestas incidentes a ele. Se houver laços, serão contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas. Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice em um dígrafo é igual à soma dos graus de saída e de entrada. O grau de um vértice é definido somente quando o número de arestas incidentes sobre o vértice é finito.
Passeio
Um passeio p {\displaystyle p} entre dois vértices A {\displaystyle A} e B {\displaystyle B} , definido como p ( A , B ) {\displaystyle p(A,B)} , é uma lista alternada de vértices e arestas p ( A , B ) = v 0 , e 1 , v 1 , e 2 , v 2 , . . . , e k , v k {\displaystyle p(A,B)=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}} tal que O tamanho de um passeio, definido por | p | {\displaystyle \left\vert p\right\vert } corresponde ao número de arestas que possui, incluindo as repetições. Na figura ao lado, um passeio do vértice a {\displaystyle a} até o vértice d {\displaystyle d} possível é a lista p ( a , d ) = a , e 9 , c , e 2 , b , e 1 , a , e 9 , c , e 8 , d {\displaystyle p(a,d)=a,e_{9},c,e_{2},b,e_{1},a,e_{9},c,e_{8},d} de tamanho 5 {\displaystyle 5} . Note que a aresta e 9 {\displaystyle e_{9}} se repete. É necessário listarmos as arestas em um passeio para distinguirmos entre as diversas arestas existentes quando estamos trabalhando em um grafo que não é simples. Em um grafo simples, basta listarmos os vértices.
Caminho
Caminho é uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são independentes se não tiverem nenhum vértice em comum, exceto o primeiro e o último. No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2. Ciclo (ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico se não contém ciclos simples.
Num hipergrafo uma aresta pode conectar mais que dois vértices. Um grafo não-direcionado pode ser visto como um complexo simplicial consistindo de símplices de uma dimensão (as arestas) e símplices de dimensão zero (os vértices). Ou seja, complexos são generalizações de grafos que permitem símplices de maiores dimensões.
