Alexandre Renato Rodrigues de Souza

Teoria da Computação

Clique de um Grafo

1

✤ Definição 1: grafo é uma estruturas utilizada para representar relações entre elementos de um dado conjunto.

Tais elementos são representados por pontos denominados vértices, e tais relações são representadas por segmentos unindo dois destes pontos, denominados arestas.

✤ Definição 2: um grafo é um conjunto de pontos, chamados vértices, conectados por linhas, chamadas de arestas.

✤

2

O que é um grafo?

O que é um grafo?

✤ Ferramenta de modelagem.

✤ Abstração matemática que representa situações reais através de um diagrama.

✤

3

O que é um grafo?

✤ Abstração que permite codificar relacionamentos entre pares de objetos.

✤ Que objetos? Ex.: pessoas, cidades, empresas, países, páginas web, filmes, etc...

✤ Que relacionamentos? Ex. amizade, conectividade, produção, língua falada, etc.

✤ Simétrico ou assimétrico.

4

Aplicação dos grafos

✤ Redes sociais

✤

5

Porque estudar grafos

✤ Importante ferramenta matemática com aplicação em diversas áreas do conhecimento: genética, química, pesquisa operacional, telecomunicações, engenharia elétrica, redes de computadores, conexão de vôos aéreos, restrições de precedência, fluxo de programas, dentre outros.

✤ Utilizados na definição e/ou resolução de problemas.

✤ Em computação: estudar grafos é mais uma forma de solucionar problemas computáveis.

✤ Os estudos teóricos em grafos buscam o desenvolvimento de algoritmos mais eficientes.

6

Grau de um vértice: definição

✤ Grau de um vértice V: número de vértices adjacentes a V Grau mínimo de um vértice: zero Grau máximo de um vértice: número total de vértices - 1

✤ Obs.: o último e os 3 primeiros casos da figura anterior possuem grau máximo em todos os vértices.

7

Grafo completo: definição

✤ Grafo simples em que existe exatamente uma aresta entre cada par de vértices distintos.

✤ Todos os vértices tem grau máximo.

✤ Notação de grafo completo: Kn onde n é o número de vértices.

✤ Exemplos:

8

Subgrafo induzido: definição

✤ Se G2 é um subgrafo de G1 e possui toda a aresta (v, w) de G1 tal que ambos, v e w, estejam em V2, então G2 é o subgrafo induzido pelo subconjunto de vértices V2.

✤

9

Clique de um grafo: definição

✤ Denomina-se clique de um grafo G a um subgrafo (induzido) de G que seja completo.

✤ O clique é denotado como Kn, onde n é o número de vértices do clique.

✤ Um clique de um grafo é um conjunto de vértices adjacentes entre si que não está estritamente contido em outros cliques (conceito similar para dígrafos).

✤ Pode-se pensar em um clique como um conjunto “totalmente relacionado” de vértices de um grafo.

10

Clique de um grafo: exemplos

✤ O tamanho (número de vértices) do maior clique de (dí)grafo G é chamado número de clique, ω(G).

11

Clique de um grafo: exemplos

✤ a) 3 cliques de 3 vértices

✤ b) 1 clique de 4 vértices (considerando G2 um subgrafo induzido)

12

Clique de um grafo: exemplos

✤ Subgrafo {2,3,4,6} é um clique de tamanho 4 (K4):

✤ 4 cliques de 3 vértices: tamanho 3 (K3)

13

Clique de um grafo: exemplos

14

Clique de um grafo: exemplos

✤ Em um mesmo grafo, podemos encontrar cliques de diferentes ordens, pois podem existir diferentes subgrafos que podem ser induzidos de G tal que formem um subgrafo completo.

✤ No grafo abaixo podemos observar dois destaques, a aresta f1; 6g (destaca em azul e pontilhado) forma uma clique de tamanho 2. Isso pois se analisarmos o subgrafo induzido por vértices G[S], com S = f1; 6g ele é um grafo completo. Outras cliques de tamanho 2 também estão presentes no grafo. O destaque em vermelho e pontilhado denota uma clique de tamanho 3, pois se analisarmos o subgrafo induzido por vértices G[S], com S = f2; 4; 5g ele é também um grafo completo.

✤

15

Clique de um grafo: aplicações

✤ A determinação de cliques modela diversas outras situações reais, dentre as quais podem ser citados:- problemas de otimização em pesquisa operacional- atribuição de frequências em comunicação a rádio- criptografia- determinação de trilhas em circuitos impressos- emparelhamento de sequências de aminoácidos em proteínas

16

Clique de um grafo: aplicações

✤ O problema de identificar agrupamentos de objetos relacionados frequentemente se reduz a encontrar grandes cliques em grafos.

✤ Exemplo: empresa de fabricação de peças por meio de injeção plástica que fornece para diversas outras empresas montadoras. Para reduzir o custo relativo ao tempo de preparação das máquinas injetoras (setups), pode-se aumentar o tamanho dos lotes produzidos para cada peça encomendada. É preciso identificar os clientes que adquirem os mesmos produtos, para negociar prazos de entrega comuns e assim aumentar o tamanho dos lotes produzidos.

✤ Solução: construir um grafo com cada vértice representando um cliente e ligar com uma aresta os que adquirem os mesmos produtos. Um clique no grafo representa o conjunto de clientes que adquirem os mesmos produtos.

17

Clique de um grafo: aplicações

✤ Outro exemplo de situação na qual se enquadra este problema:

✤ Suponha que, em um laboratório farmacêutico, seja necessário dimensionar o depósito de substâncias composto por alguns refrigeradores, tendo em mãos uma lista de pares de substâncias que não podem ser armazenadas em um mesmo refrigerador. Assim, o clique máximo do grafo formado por tais incompatibilidades é um limitante inferior para a quantidade de refrigeradores necessários para armazenar todas as substâncias.

18

Algoritmos de determinação

✤ Em um grafo com N vértices, existem 2N possibilidades para um possível clique, e um algoritmo de força bruta deveria testar todas elas, sendo exponencial em N.

✤ Algoritmos Gulosos

✤ Heurística de Maior Grau (GREEDY1)

✤ Heurística de Maior Vizinhança (GREEDY2)

✤ Heurística de Maior Expansibilidade (GREEDY3)

✤ Algoritmo de Verificação e Eliminação (BINARY)19

Alexandre Renato Rodrigues de Souza

Teoria da Computação

Clique de um Grafo

20