Um grafo é um par $G=(V,E)$ onde $V$ representa o conjunto de vértices e $E$ o conjunto de aresta entre pares de vértices. Normalmente $V$ e $E$ são finitos. A ordem do grafo é dada pelo número de vértices e o tamanho pelo número de vértices.

Notação: $\{ u,v\}$ representa um par não ordenado de vértices. $e$ é o vértice que os liga. u e v são ditos incidentes em e.

Definições:

• Loop: Quando uma aresta liga o mesmo vértice $\{u,u\}$;
• Vértices paralelos: Quando duas ou mais arestas ligam pares distintos de vértices;
• Multigrafo: Grafo que não tem loop;
• Pseudografo: Grafo com pelo menos um loop;
• Grafo simples: Não tem vértices paralelos ou loops;
• Grafo completo: Escrito como $K_n$, é um grafo com n vértice com apenas uma aresta ligando cada par de vértices;
• Grafo trivial: $K_1$, um vértice e sem arestas;
• Grafo bipartido: Grafo simples em que o conjunto de vértices pode ser dividido em dois conjunto X e Y, tal que cada aresta está em um vértice em X e um vértice em Y. É representado por $G=(X,Y,E)$;
• Grafo completo bipartido: $K_{m,n}$ é o grafo $(X,Y,E)$ com m vértices em X e n vértices em Y, de forma que uma aresta entre cada vértice de X e em cada vértice de Y;
• Grafo direto, orientado ou digrafo: Conjunto finito de vértices V e um conjunto A de pares ordenados de vértices chamados arcos, arestas direcionadas ou setas. A ordem no par ordenado indica o sentido da seta. Se o par é $\{u,v \}$ em a, quer dizer que a é adjacente de u para v;
• Grafo misto: Grafo orientado com pelo menos uma aresta e um arco;
• Grafo subjacente: Quando substituímos as arestas por arcos;
• Digrafo com orientação: Quando substituímos arcos por arestas;
• Torneio: Dado um par de vértices $\{x,y\}$, há uma aresta xy ou yx, mas não ambas;
• Emparelhamento: Conjunto de arestas duas a duas não adjacentes. Um vértice é ponta de máximo uma aresta.

Dois grafos são idênticos se, dados $G=(V,E)$ e $G'=(V', E')$, $V=V'$ e $E=E'$. Dizemos que há isomorfismo entre dois grafos se há uma relação um para um entre eles, ou seja, dada uma aresta entre $f(v)$ e $f(w)$ em $G'$, há uma aresta entre $v$ e $w$ em $G$, para quaisquer $v$ e $w$. $G$ e $G'$ podem ser considerados equivalentes.

Problema do isomorfismo: Definir se existe isomorfismo entre dois grafos.

Um subgrafo $H=(W,F)$ do grafo $G=(V,E)$ ocorre quando W é subconjunto de $V$ e $F$ de $E$. Também pode ser descrito como $H$ sendo isomórfico de $G$. Algumas operações podem ser feitas entre grafos e subgrafos:

• $G-F$: remove as arestas $F$ do grafo $G$;
• $G-W$ : remove os vértices $W$ de $G$.

Um vértice que tem p loops e q vértices tem grau dado por $2p+q$. Um vértice é dito isolado se seu grau é 0 e um vértice é tipo final se seu grau é 1.

Grau máximo: $\Delta(G)$

Grau mínimo: $\delta(G)$

Um grafo é dito k-regular se cada vértice tem grau k e é regular se existe um número k não negativo tal que ele é k-regular.

Teorema (hand-shaking lemma de Euler): A soma dos graus de um grafo é duas vezes o número de seus vértices.

Um vértice é dito ímpar se tem grau ímpar e é par caso contrário.

Teorema: Todo grafo tem um número par de vértices ímpares.

Grau de entrada: Número de arcos adjacentes indo ao vértice;

Grau de saída: Número de arcos adjacentes saindo do vértice;

Teorema: Em um digrafo, a soma dos graus para fora é igual à soma do número de arcos, qual também é igual à soma dos arcos que entram em todos os vértices.

Podemos definir uma matriz dita adjacente para descrever as relações entre os vértices e suas arestas. Dado um grafo $G=(V,E)$ onde $V={1,2,…,n}$, a matriz $A$, $n\times n$, tal que seus elementos não diagonais $a_{ij}$ representam as arestas conectadas aos vértices $i$ e $j$ e um elemento diagonal é duas vezes o número de loops no vértice $i$.

A matriz incidente $B$ de um grafo $G$ é dada por: A linha $i$ de $B$ corresponde ao vértice $i$. A coluna $k$ corresponde à aresta $e_k$ para cada $k$. Se $e_k$ é uma aresta ligando os vértices $i$ e $j$, então as entradas $b_{ik}$ e $b_{ki}$ são 1 e todas as outras da coluna $k$ são zero. No caso de um digrafo, se $e_k$ liga os vértice i e j, definimos $b_{ik}=-1$ e $b_{jk}=1$, na coluna k.

Vetor de grau: Escrito como $d(G)$, é a sequência de graus de seus vértices ordenados de forma decrescente.

Um vetor $v$ é dito vetor gráfico se existe um grafo simples tal que $v$ é o vetor de grau deste grafo.

Teorema (Hakimi-Havel): Seja $v=[d_1\;d_2\;d_3\;...\;d_k]$ um vetor com k inteiros não negativos tal que nenhuma componente $d_i$ excede (k-1). Seja $v'$ o vetor obtido de $v$ ao excluir $d_1$ e subtrair 1 de cada elemento subsequente a $d_1$ em v. Seja $v_1$ o vetor obtido de $v'$ após reorganizar seus componente se necessário. Então, $v$ é um vetor gráfico se e somente se $v_1$ é um vetor gráfico.

Uma caminhada é uma sequência de vértices e arestas em um grafo, que podem ser repetidos. Pode ser fechada ou aberta. Caminhada aberta: Quando o vértice inicial é diferente do final;

Caminhada fechada: Quando o vértice inicial é o mesmo do final.

Uma trilha é uma caminhada aberta onde nenhuma aresta é repetida. Uma trilha fechada ocorre quando o vértice inicial é igual ao final.

Um circuito ocorre quando não repetimos arestas, mas os vértices podem ser repetidos e a caminhada é fechada.

Um caminho é quando nenhum vértice ou aresta são repetidos. Um caminho também é uma trilha, mas com caminhada aberta.

Um ciclo é um caminho onde o vértice inicial é igual ao final.

A teoria de planaridade investiga os ciclos de grafos. Que tipos de grafos podem ser desenhados em um plano sem que suas arestas se cruzem? Um exemplo seria a produção de um circuito em uma única placa sem que as conexões se cruzem.

Uma representação planar de um grafo pode ser dividida em regiões. Essas regiões são limitadas por arestas, exceto por uma região sem limites. Toda representação planar deve ter o mesmo número de regiões.

Teorema (fórmula de Euler): Seja $G$ um grafo conexo simples e planar com $v$ vértices e $e$ arestas. O número de regiões é dado por $r=e-v+(k+1)$ onde k é o número de componentes do grafo.

A seguinte desigualdade é consequência da fórmula de Euler. Seja G um grafo conexo planar com $e$ arestas e $v$ vértices, onde $v\geq 3$, então $e\leq 3v-6$. G não pode ter um vértice com grau maior do que 5.

Teorema de Kuratowski: Dados os grafos completos $K_{3,3}$ e $K_5$: nenhum grafo que contém um destes grafos como subfgrafo pode ser planar e nenhum grafo obtido desses grafos fazendo simples adição de vértices pode ser planar.

Uma propriedade é chamada de invariante quando é preservada por um isomorfismo. Alguns exemplos são: número de vértices e arestas, graus dos vértices, comprimento do ciclo, etc.

Um grafo não orientado é dito conexo se há um caminho entre qualquer par de vértices distintos.

Um grafo orientado é dito fortemente conexo se existe um caminho de a até b e de b a onde a e b são vértices do grafo. O grafo é dito fracamente conexo se o grafo não orientado subjacente é conexo.

Pontos de articulação são vértices que quando removidos, junto de suas arestas incidentes, resulta em um grafo com mais componentes conexos que o original. Análogo a esse conceito são as arestas de corte que quando removidas temos um subgrafo com mais componentes conexos. São chamadas de pontes.

Um conjunto de corte é formado por arestas que quando removidas de um grafo G deixa G desconexo.

Um grafo G é dito Euleriano se há uma trilha fechada que contém cada uma das arestas de G. Se o grafo é Hamiltoniano, então ele contém uma trilha fechada que passa apenas uma única vez por cada um dos vértices.

É o processo de designar uma cor diferente para cada vértice de um grafo tal que nenhum vértice adjacente tenha a mesma cor. A solução trivial desse problema é usar sempre uma cor diferente para cada vértice, mas não é a solução ótima.

O menor número de cores para colorir um grafo é chamada de número cromático e denotado por $\chi(G)$. Em um grafo planar, o problema de achar o número cromático é o mesmo de encontrar o menor número de cores.

Teorema das 4 cores: O número cromático de um gráfico planar não é maior do que 4.

Tem infinitos vértices, arestas ou ambos.

O problema clássico em grafos é o do caixeiro-viajante. Um vendedor de produtor deve passar por várias cidades, ligadas entre si por vias. É possível visitar cada cidade apenas uma vez sendo que o destino final é a cidade de partida? Obviamente que o problema pode ser modelado por um grafo, onde as cidades são os vértices e as vias as arestas. Uma cidade $v_x$ é conectada a outra $v_y$ se existir uma via $e_{xy}$ entre elas.

Uma das soluções para esse problema é modelá-lo como um restrição, por exemplo:

Onde $S$ é elemento de $\mathcal{S}$, o conjunto de todos os subconjuntos de $V$.

Outra forma é modelá-lo como um problema de otimização onde podemos eliminar sub-ciclos e utiliza Programação Linear Inteira na solução. Suponha um grafo com vértices {a,b,c,d} e as seguintes restrições:

onde exploramos as combinações de todos os caminhos. Podemos utilizar a matriz acima, junto dos pesos de cada aresta, para calcular a solução.

Analisemos dois importantes algoritmos em grafos: o de Kruskal e o de Floyd-Warshall.

O algoritmo de Kruskal é usado para encontrar a árvore geradora mínima (MST) de um grafo ponderado conectado. O MST é um subconjunto das arestas do grafo que conecta todos os vértices enquanto minimiza o peso total. Veja como o algoritmo de Kruskal funciona:

1. Comece com o gráfico original e classifique suas arestas em ordem crescente com base em seus pesos.
2. Crie um conjunto vazio para conter o MST.
3. Percorra as arestas classificadas, adicionando-as ao MST se elas não criarem um ciclo. Isso é feito verificando se a adição da borda cria um ciclo no MST construído até agora, usando técnicas como conjuntos disjuntos ou estruturas de dados de localização de união (Union Find).
4. Repita o processo até que todos os vértices estejam conectados e o MST esteja completo.

O algoritmo de Kruskal garante a construção de um MST com o peso total mínimo. É eficiente para grafos esparsos, onde o número de arestas é relativamente pequeno comparado ao número de vértices. Tem complexidade $O(Elog(E))$.

O algoritmo Floyd-Warshall é usado para encontrar os caminhos mais curtos entre todos os pares de vértices em um grafo ponderado. Ele funciona tanto para grafos direcionados quanto não direcionados e pode lidar com grafos com pesos de borda negativos, desde que não haja ciclos negativos. Veja como o algoritmo Floyd-Warshall funciona:

1. Crie uma matriz para representar as distâncias entre os vértices. Inicialmente, a matriz contém os pesos das arestas diretas, ou infinito se não houver aresta direta.
2. Percorra todos os pares de vértices e considere cada vértice como um possível nó intermediário.
3. Atualize a matriz comparando a distância entre dois vértices através do nó intermediário com a distância mínima atual. Se um caminho mais curto for encontrado, atualize a matriz de acordo.
4. Repita o processo até que todos os pares de vértices tenham sido considerados.

No final do algoritmo, a matriz contém as distâncias mais curtas entre todos os pares de vértices. Também pode ser estendido para rastrear os caminhos reais, permitindo a reconstrução dos próprios caminhos mais curtos.

O algoritmo Floyd-Warshall tem uma complexidade de tempo de $O(V^3)$, onde V é o número de vértices. É adequado para grafos densos, onde o número de arestas está próximo ao máximo de arestas possíveis.

Um problema intratável é aquele onde não há algoritmo em tempo polinomial que o resolva de forma determinística. Em um artigo, aos 24 anos, Turing descreveu alguns problemas que não podem ser solucionados mecanicamente.

Ver seção 13.14: P vs NP.

A busca em largura (BFS = breadth-first search) é um algoritmo simples de busca em grafo. É o modelo para algoritmos mais sofisticados como o de Dijkstra (caminho mais curto) e o de Prim (árvore mínima de cobertura).

Seja G=(V,E) um grafo e $s$ seu vértice inicial. Utilizamos a busca em largura para processar os vértices mais próximos de $s$ primeiro. Pode ser resumido nos seguintes passos:

1. Encontrar o vértice inicial $s$;
2. Explorar os arcos de G para encontrar todos os vértices alcançáveis começando de $s$;
3. Calcular a distância $d(s,v)$, dada pelo menor número de arcos, para cada vértice $v$ alcançável;
4. Gerar uma árvore de amplitude onde a raiz é $s$ e tem todos os vértices que podem ser alcançados;
5. Para cada $v$ alcançável de $s$, o caminho na árvore do passo 4 corresponde ao menos caminho entre eles em G.

O algoritmo analisa todos os vértices com distância $k$ a partir de $s$ antes de olhar aqueles cuja distância é $k+1$. Os vértices devem ser marcados com cores, onde o usual é um sistema com 3 delas: branco, azul e vermelho. Todos começam com a cor branca, passam para o azul e depois para o vermelho. A estrutura de dados do algoritmo deve conter:

• $cor[u]$ = informação da cor de cada vértice;
• $\pi[u]$ = informação do predecessor de cada vértice. É nulo caso não tenha um;
• $d[u]$ = valor da distância do vértice inicial até u.
• Fila tipo FIFO para armazenar e gerenciar os vértices de cor azul.

Na busca por profundidade exploramos cada vértice descoberto por completo, ou seja, dado o vértice inicial $s$, a cada vértice $v$ adjacente, exploramos suas conexões de forma recursiva. Como no caso de busca em largura, precisamos armazenar as informações do vértice predecessor, mas temos agora uma árvore e não apenas um vetor de fila. O algoritmo deve ter a informação do tempo de descoberta de um vértice $d[v]$ e também a informação de quando $v$ foi totalmente examinada $f[v]$.

Encontrar o menor caminho entre dois vértices $v$ e $u$ em grafos sem ponderação é calcular o caminho de modo que $d(v,u)$ seja mínimo. Dois algoritmos são recomendados:

• Bellman-Ford
• Dijkstra

O algoritmo de Bellman-Ford é usado para encontrar os caminhos mais curtos de um único vértice de origem para todos os outros vértices em um grafo. Ele pode lidar com gráficos com pesos de borda positivos e negativos, bem como detectar ciclos negativos. Veja como o algoritmo de Bellman-Ford funciona:

1. Comece inicializando as distâncias do vértice de origem para todos os outros vértices como infinito, exceto para a própria origem, que é definida como zero.
2. Relaxe as bordas repetidamente. Em cada iteração, examine todas as arestas e atualize as distâncias se um caminho mais curto for encontrado.
3. Repita o processo de relaxamento $V-1$ vezes, onde $V$ é o número de vértices no grafo. Isso garante que os caminhos mais curtos sejam encontrados, se existirem.
4. Verifique se há ciclos negativos executando mais uma iteração de relaxamento de borda. Se ocorrer uma atualização de distância nesta iteração final, um ciclo negativo estará presente no gráfico.

O algoritmo de Bellman-Ford é flexível e pode lidar com uma ampla gama de cenários, incluindo gráficos com pesos negativos e ciclos negativos. No entanto, sua complexidade de tempo é O(V * E), onde V é o número de vértices e E é o número de arestas, tornando-o menos eficiente em comparação com outros algoritmos como o algoritmo de Dijkstra.

O algoritmo de Dijkstra é usado para encontrar os caminhos mais curtos de um único vértice de origem para todos os outros vértices em um grafo com pesos de borda não negativos. Garante os caminhos mais curtos desde que o grafo não contenha pesos ou ciclos de aresta negativos. Veja como o algoritmo de Dijkstra funciona:

1. Comece inicializando as distâncias do vértice de origem para todos os outros vértices como infinito, exceto para a própria origem, que é definida como zero.
2. Crie uma fila de prioridade para armazenar os vértices, priorizados com base na distância provisória da origem.
3. Abra o vértice com a menor distância provisória da fila de prioridade e considere seus vizinhos.
4. Atualize as distâncias dos vizinhos se um caminho mais curto for encontrado. Se ocorrer uma atualização, coloque o vizinho na fila de prioridade.
5. Repita o processo até que todos os vértices tenham sido processados ou a fila de prioridade fique vazia.

O algoritmo de Dijkstra garante o caminho mais curto da fonte para cada vértice quando usado em grafos sem pesos ou ciclos de borda negativos. Tem uma complexidade de tempo de O((V + E) * log(V)), onde V é o número de vértices e E é o número de arestas, tornando-o mais eficiente que o algoritmo de Bellman-Ford em cenários onde arestas negativas pesos não estão presentes.

Ambos os algoritmos de Bellman-Ford e Dijkstra são ferramentas essenciais na teoria dos grafos, fornecendo soluções eficientes para o problema de encontrar caminhos mais curtos de um único vértice de origem para todos os outros vértices, considerando diferentes restrições como pesos ou ciclos de arestas negativas.

Um grafo acíclico ou floresta é um grafo sem ciclos. Uma árvore é um grafo acíclico conexo. Então, cada componente de uma floresta é uma árvore e toda árvore é uma floresta conexa.

Teorema: O centro de uma área é ou um conjunto único, constituído de um único vértice, ou um conjunto de dois vértices adjacentes.

Um subgrafo conexo acíclico de G é chamado de árvore geradora em G.

Teorema: Um grafo é conexo se e somente se possui uma árvore geradora.

Teorema: Seja G um grafo simples com n vértices. Se um subgrafo gerador H satisfaz duas de três das seguintes propriedades, então satisfaz a terceira também:

1. H é conexo;
2. H tem $(n-1)$ arestas;
3. H é acíclico.

Se para cada vértice temos uma ponderação ou valoração chamamos de árvore valorada.

Um grafo direcionado acíclico (DAG) é um digrafo que não tem ciclos. Exemplos: Hierarquia de classes em orientação de objetos, pré-requisitos entre disciplinas, restrições de cronograma entre tarefas de um projeto.

Toda árvore direcionada é um DAG e todo caminho num digrafo acíclico é simples, sem repetição de vértices.

Quando permutamos os vértices de um digrafo temos uma sequência em que cada vértice aparece apenas uma vez. Chamamos de ordenação topológica a permutação dos vértices $v_1, v_2, ..., v_n$ em um digrafo acíclico, tal que, para qualquer aresta $e_{ij}=(v_i, v_j)$, $i j$.

Digrafos cíclicos não podem ter ordenação topológica. Por outro lado, todo DAG admite ordenação topológica.

Algoritmo de ordenação de Kahn:

1. Encontra os vértices “fonte” (com grau de entrada zero) e os insere em um vetor S (se o grafo é acíclico, ao menos um desses existe);
2. Remove da fila os vértices fonte (pelo fato de que removendo os vértices e seus arcos, o grafo resultante ainda é um DAG);
3. Etiqueta os vértices em ordem de remoção;
4. Remove os arcos dos vértices.

Pode se usar também busca em profundidade, através do algoritmo de Tarjan.

Referências:

1. Graph Theory - Schaum Outline
2. Teoria dos Grafos - Paulo Feofiloff
3. Mathematics - Graph Theory Basics
4. Grafos - Moacir Ponti Jr. (ICMC - USP)
5. Teoria dos Grafos - Jorge César Abrantes de Figueiredo (UFCG)