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