Teoria do Grafos -slide

Report
Teoria do Grafos
Prof. Luiz Fernando L. Nascimento
Versão 1.0 - 2014
Introdução aos Grafos
- A história das pontes é de 300 anos atrás. Königsberg foi uma importante cidade
da Prússia, localizada ao norte da Europa, próximo à costa do Mar Báltico, e que
hoje é chamada de Kaliningrado.
A cidade possuía duas ilhas cortadas pelo Rio Pregel e, na época, seis pontes as
ligavam às margens e outra fazia a ligação das duas ilhas entre si.
Por volta de 1735, os moradores de Königsberg se desafiaram com o seguinte
problema:
Como seria possível fazer um passeio a pé pela cidade de forma a passar uma
única vez por cada uma das sete pontes e retornar ao ponto de partida.
Introdução aos Grafos
Mapa
2014
Google Maps
Introdução aos Grafos
Na época, foi o matemático Leonhard Euler quem decifrou o enigma, revelando ser
impossível tal façanha.
Euler raciocinou da seguinte maneira:
Ao atravessar cada ponto, são gastos exatamente duas linhas, uma para entrar no
ponto e outra para sair. Para atravessar qualquer vértice, são gastas duas linhas, uma
para entrar no vértice e outra para sair.
Conclusão, cada vértice deve ter grau par de linhas.
Como o grafo das pontes de Königsberg tem pontos de grau ímpar, o problema não pode
ter solução.
Definições Básicas
Definição 1:
Denomina-se grafo (G) o par G=(V,A) em que:
V é o conjunto de vértices ou nodos, sendo esse um conjunto finito.
A é o conjunto de arestas, sendo que essas arestas são formadas por pares
ordenados e = (v,w), onde v e w ∈ V, isto é, A é subconjunto de V.
Exemplo:
V={1,2,3,4}
A={(1,2),(1,3),(2,3),(2,4),(3,4)}
Nota: É também referenciada pela letra E (edges)
Definições Básicas
Definição 2:
Um grafo G é definido por G = (V, E), sendo que V representa o conjunto de nós
e E, o conjunto de arestas (i, j), onde i, j ∈ V . Dois nós i, j são vizinhos, denotado
por i ∼ j, se eles estão conectados por uma aresta.
Exemplos de grafos.
O grafo G1 consiste dos conjuntos
V = {a, b, c, d, e} e
E = { e1, e2, e3, e4, e5, e6 };
G2 possui o nó c que não é
conectado a nenhum outro nó
do grafo.
Definições Básicas
Exemplo:
G=(V,A)
V={1,2,3,4}
A={(2,1),(1,3),(3,2),(4,2),(4,3)}
arcos
( Digrafo )
Definições Básicas
Exemplo: G=(V,A)
V={1,2,3,4}
A={(1,2),(1,3),(2,3),(2,4),(3,4)}
Os vértices v e w dizem-se adjacentes (vizinhos) se existe uma aresta
incidente em ambos.
(Incidente = sai de um vértice e chega em outro)
v
w
O número de arestas incidentes em v diz-se o grau de v
G’=(V’,A’)
V’={1,2,3}
A’={(1,2),(1,3),(2,3)}
Lê-se: V’ é subconjunto de V
A’ é subconjunto de A
Definições Básicas
Multigrafo ou pseudografo :
É um grafo não dirigido que pode possuir arestas múltiplas (ou paralelas), ou seja, arestas
com mesmos nós finais. Assim, dois vértices podem estar conectados por mais de uma
aresta.
Formalmente, um multigrafo G é um par ordenado, sendo:
V: um conjunto de vértices ou nós,
E: um multiconjunto de pares não-ordenados de vértices, chamado arestas ou linhas.
Definições Básicas
Grafo (simples)
Um grafo é dito ser simples se não existirem arestas paralelas (mais do que 1
aresta entre um par de vértices),nem lacetes (arestas com ambos os extremos no
mesmo vértice)
Multigrafo
Com lacetes e/ou
arestas paralelas
Definições Básicas
Ordem (cardinalidade)
A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo
número de vértices de G.
G1
ordem(G1) = 4
ordem(G2) = 6
G2
Definições Básicas
Vértices Vizinhos (neighbors)
Defini-se como vértices vizinhos os vértices que estão conectados as mesmas arestas que o
vértice em questão:
Para descobrir os vértices vizinhos (vizinhança) de um vértice u verifica-se se existe um
vértice w que pertence ao conjunto de vértices de G tal que a aresta identificada por u w
pertença ao conjunto de arestas de G.
Exemplo:
O grafo dos estados do Brasil é definido assim:
cada vértice é um dos estados da República
Federativa do Brasil; dois estados são
adjacentes se têm uma fronteira comum.
Quantos vértices tem o grafo? Quantas
arestas?
Definições Básicas
Conjunto independente e Clique
No grafo G os conjuntos {3,5,6} e {1,4,6,8} são independentes;
No caso de {1,4,6,8} temos um conjunto independente de cardinalidade máxima pois não
há naquele grafo conjunto independente com 5 ou mais vértices.
Nesse mesmo grafo, {8}, {6,7} e {1,2,5} são cliques, o último de cardinalidade máxima.
Considerando o grafo G
Definições Básicas
Definição 1:
Dizemos que o grafo H é um subgrafo do grafo G se, e somente se,
V (H) ⊆ V (G) e E(H) ⊆ E(G)
e nesse caso escrevemos H ⊆ G para indicar que H é subgrafo de G.
Definição 2:
Um sub-grafo de um grafo G é um grafo H cujos vértices e arestas estão todos em G.
Se H é sub-grafo de G, também pode-se dizer que G é um super-grafo de H.
Introdução aos Grafos
Grau
O grau de um vértice é dado pelo número de arestas que lhe são incidentes.
O grau de um nó u (ou valência), denotado por dG(u) é o número |E(u)| de arestas em u.
Um nó de grau 0 é um nó isolado.
Definições Básicas
Um vértice que possui grau zero é um vértice isolado.
Caso o grafo não contenha nenhuma aresta, todos os vértices são isolados e o grafo é
chamado grafo nulo
Vértice Isolado (ou trivial)
Grafo Nulo
Chamamos G0 = (∅,∅) de grafo vazio e todo grafo de ordem 1 de grafo trivial.
Definições Básicas
Grafo Regular
Um grafo é dito ser regular quando todos os seus vértices tem o mesmo grau.
O grafo G4, por exemplo, é dito ser um grafo regular-3, pois todos os seus vértices tem
grau 3.
Grau 1
Grau 2
Grau 3
Grau4
Um grafo no qual todos os vértices têm o mesmo grau r é chamado grafo
regular de grau r.
Exemplo: 2-regular (quadrado)
Introdução aos Grafos
Grafo Completo
Definição 1:
Um grafo é dito ser completo quando há uma aresta entre cada par de seus vértices.
Estes grafos são designados por Kn, onde n é a ordem do grafo.
Um grafo Kn possui o número máximo possível de arestas para um dados n. Ele é, também
regular-(n-1) pois todos os seus vértices tem grau n-1.
K1 = Grafo Trivial
Definição 2:
Um grafo completo G=(V,E) com |V| vértices, denotado por K|v|, é um grafo simples onde
todo par de vértices é ligado por uma aresta. Em outras palavras, um grafo completo é um
grafo simples que contém o número máximo de arestas.
Lemas e Teoremas
Grafo Completo
Teorema 1-1: O número de arestas em um grafo completo é n(n-1)/2.
Prova: A prova é por indução matemática. Chamaremos Gn um grafo que contém n vértices.
Consideramos primeiro o caso, um grafo trivial. Nesse caso, como existe somente um vértice, é
impossível definir uma aresta que não seja um laço. Então não pode existir nenhuma aresta.
Portanto n(n-1)/2 = 0.
Suponhamos que a hipótese é verdadeira para Gn, onde n ≥ 1. Seja agora o grafo Gn+1.
Precisamos provar que o número de vértices nesse grafo é n(n+1)/2.
Seja vn+1 o vértice adicional que se encontra em Gn+1 e não em Gn. O número máximo de arestas
no grafo Gn+1 é igual ao número máximo no grafo Gn mais todas as ligações possíveis entre vn+1 e
cada vértices de Gn. Como esse número de ligações é igual ao número de vértices em Gn, temos:
Uma outra maneira de chegar a esse resultado e considerar o fato que o número de arestas em
um grafo completo de n vértices corresponde a todos os pares possíveis (u, v), onde u e v são
vértices. Assim, o número de vértices é:
Lemas e Teoremas
Lema 1.1.
A soma dos graus de todos os vértices de um grafo é um número par.
Prova:
Suponhamos que um grafo G tenha n vértices e m arestas. Como cada aresta contribui
com dois graus, a soma dos graus relacionados a todas as arestas de G é duas vezes o
número de arestas, ou seja,
Teorema 1-2:
O número de vértices de grau ímpar de um grafo é sempre par.
Prova:
Separando os vértices de grau par e os de grau ímpar, a soma pode ser separada em duas
somas:
onde PAR e IMPAR são os conjunto de vértices de grau
par e impar, respectivamente. Como a soma na esquerda é par (=2m) e a primeira soma do
lado de direita também é par, por ser uma soma de números pares, a segunda também
tem que ser par. Como todo valor d(vl) é ímpar, a quantidade de itens na soma tem que ser
par
Definições Básicas
Grafo Bipartido
Um grafo é dito ser bipartido quando seu conjunto de vértices V puder ser particionado
em dois subconjuntos V1 e V2, tais que toda aresta de G une um vértice de V1 a outro
de V2.
Chamamos um grafo G de grafo bipartido se existem dois conjuntos
independentes A e B em G que particionam V (G), isto é, tais
que A ∩ B = ∅ e A ∪ B = V (G).
Por exemplo, o seguinte grafo é bipartido pois V (G) = {1,2,3,4,5} ∪ {6,7,8} e
tanto {1,2,3,4,5} quanto {6,7,8} são conjuntos independentes.
Desenhar o grafo
Definições Básicas
Problema: Você tem que levar água, luz e esgoto para 3 casas de uma cidade.
As fornecedoras de água (A), luz (L) e esgoto (E) permitem que os canos distribuidores não
sejam retos. São canos flexíveis e podem ser arrumados da forma que você desejar.
Os canos JAMAIS podem se cruzar e/ou invadir a região interna de qualquer casa e de
qualquer fornecedora.
A profundidade de encanamentos sob os terrenos da cidade que a prefeitura tolera é
única. Ou seja, assuma no esquema que todos os canos são como linhas no mesmo plano.
Solução: Segundo o Teorema de Kuratowski, um grafo planar não pode apresentar nem o
grafo completo K5 nem o grafo bipartido K3,3 como subgrafos. A prova de que o K3,3 não é
planar pode ser feita de duas formas: por indução e por construção, enquanto a do K5 é
feita apenas por construção.
Não é possível redesenhar estes grafos sem que suas arestas se cruzem.
Definições Básicas
Grafo Conexo
Um grafo diz-se conexo se quaisquer que sejam os vértices distintos u e v existe
sempre um caminho que os une. Quando tal não acontece o grafo diz-se
desconexo.
A representação gráfica destes grafos contém no mínimo duas "partes" e cada
uma dessas partes é uma componente conexa.
Para além de grafos conexos e desconexos podemos ainda encontrar grafos
totalmente desconexos, quando não existe nenhuma aresta.
Considerando o conceito de componente conexa, um grafo é dito ser conexo
se ele possui apenas uma única componente conexa.
Lemas e Teoremas
Grafo Conexo
Teorema 1-3: Se um grafo (conexo ou desconexo) contém exatamente dois vértices de grau
ímpar, existe um caminho ligando esses dois vértices.
Prova:
Seja G um grafo onde todos os vértices são de grau par, exceto os vértices v1 e v2. Segundo
o Teorema 1-2, não existe um grafo (ou um componente) que tem um número ímpar de
vértices que possuem grau ímpar. Então v1 e v2 devem pertencer ao mesmo componente,
e deve existir um caminho entre eles.
Definições Básicas
Conectividade é um dos conceitos básicos da teoria dos grafos: fala sobre o
número mínimo de elementos (vértices ou arestas) que precisam ser removidas
para desconectar os vértices restantes uns dos outros.
É um tema fortemente ligado a teoria dos problemas de fluxo de redes.
A conectividade de um grafo é uma importante medida da robustez de uma
rede.
Rede conexa utilizando
Diferentes equipamentos portáteis
Exemplo (simulação NS2)
Sensor – RSSF
Modulo Zibee
Exemplo de conectividade
em Rede de Sensores Sem Fio
https://www.youtube.com/watch?v=vn0pmkj3S-A
Definições Básicas
Vértice de articulação ou vértice de corte: é um vértice de um grafo conexo
em que sua remoção torna o grafo desconexo.
Qualquer grafo que contenha um vértice de articulação é considerado frágil.
Vértice de corte
(articulação)
A conectividade de vértices k(G) de um grafo G=(VA) é o menor número de vértices
cuja remoção desconecta G ou o reduz a um único vértice, isto é, quantos vértices
são necessário para que o grafo se torne desconexo.
K = Kappa (Letra Grega)
Definições Básicas
Vértice de articulação ou vértice de corte: é um vértice de um grafo conexo
em que sua remoção torna o grafo desconexo.
Qualquer grafo que contenha um vértice de articulação é considerado frágil.
Remoção do vértice 4 criou duas componentes conexas
Definições Básicas
Ponte ou aresta de corte: é a aresta de um grafo conexo em que sua remoção
torna o grafo desconexo.
Qualquer grafo que também contenha uma única aresta de corte é
considerado frágil.
d
g
a
f
c
b
e
h
Aresta de corte (ponte)
e={c,f}
A conectividade de arestas K'(G) de um grafo G=(V,A) é o menor número de
arestas cuja remoção resulta em um grafo não conexo.
K = Kappa (Letra Grega)
Definições Básicas
Ponte ou aresta de corte: é a aresta de um grafo conexo em que sua remoção
torna o grafo desconexo.
Qualquer grafo que também contenha uma única aresta de corte é considerado
frágil.
d
g
a
f
c
b
e
h
A conectividade de arestas K'(G) de um grafo G=(V,A) é o menor número de
arestas cuja remoção resulta em um grafo não conexo.
K = Kappa (Letra Grega)
Introdução aos Grafos
Grafos Planares
Um grafo pode ser desenhado no plano sem cruzamento de arestas se e somente se o
grafo não contém um sub-grafo completo K5, nem um sub-grafo bipartido K3,3
Uma aplicação que utiliza o conceito de grafos planares é a disposição de circuitos
impressos numa placa.
Um circuito eletrônico pode ser considerado um grafo onde as junções são vértices e as
arestas são os fios ligando as junções.
Definições Básicas
Representação do grafo
Uma das formas mais simples de representar um grafo no computador é usando
matrizes. Representar grafos por matrizes permite usar as ferramentas da álgebra
linear para tratar grafos.
As representações usuais: Matriz de adjacência e Matriz de incidência.
Definições Básicas
Vetor de grau
O vetor de grau d(G) de um grafo G é a sequência dos graus dos vértices de G em ordem
não crescente.
Note que dois grafos não isomorfos podem ter o mesmo vetor de grau.
Por exemplo, o vetor de grau do grafos G é o seguinte: [3,3,3,3,2,2,2,2]
Introdução aos Grafos
Matriz de Adjacência
Definição:
Se G é um grafo com vértices {1,2,3,...,n}, sua matriz de adjacência é a matriz n x n cujo
elemento ij é o número de arestas ligando o vértice i ao vértice j;
Definições Básicas
Lista de Adjacência
Como a matriz de adjacência e a matriz de incidência são compostas, em sua maior parte,
por zeros, é possível construir uma representação mais eficiente, no que diz respeito ao
uso de memória.
Definição:
Uma lista de incidência é uma tabela que lista, para cada vértice v, todos as arestas
incidentes em v.
Definições Básicas
Matriz de Incidência
Idéia: associar vértices às linhas e arestas às colunas elemento da matriz indica se aresta
incide sobre o vértice.
Matriz de incidência
Matriz n x m (n vértices, m arestas)
aij = 1 , se vértice i incide sobre aresta j
aij = 0 , caso contrário
Definições Básicas
Exercício: Construir o Grafo G com baseado na seguinte matriz de incidência
Definições Básicas
Isomorfismo:
Definição1:
Dois grafos G1=(V1,E1) e G2=(V2,E2) são ditos isomorfos entre si se existe uma
correspondência entre os seus vértices e arestas de tal maneira que a relação de incidência
seja preservada.
Em outros termos, temos |V1|= |V2| e existe uma função unívoca f: V1→V2, tal que (i,j) é
elemento de E1 se e somente se (ƒ(i),f(j)) é elemento de E2.
Definição2:
Dados os grafos simples 1=(1, 1) e 2=(2, 2 ), esses são isomorfos se:
• 1 e 2 possuírem a mesma quantidade de vértices e arestas
• 1 e 2 possuírem o mesmo vetor de graus
• Existir uma função bijetora :1→2 tal que  e  são adjacentes em 1 se (a) e ()
são adjacentes em 2
• A função  é chamada de um isomorfismo
Definições Básicas
Isomorfismo:
Para ver o isomorfismo dos grafos acima, podemos utilizar a seguinte função:
f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 8, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 4.
Observação: Analise primeiro a quantidade de vértices, arestas, o vetor de graus e por fim a
relação de correspondência.
Isomorfismo de Grafos
Exercício:
Verifique se o grafos G e H e K são isomorfos
Definições Básicas
Exercícios Construa a matriz de adjacência dos seguintes grafos e verifique se G e H são
grafos isomorfos.
G
H
G
H
Definições Básicas
Clique:
Clique ou grafo completo é um grafo, ou subgrafo, em que seus vértices são interligados
ou adjacentes dois a dois; de forma que o caminho mais curto entre quaisquer dois
vértices v e w é a aresta (v,w).
Definições Básicas
Clique:
Clique ou grafo completo é um grafo, ou subgrafo, em que seus vértices são interligados
ou adjacentes dois a dois; de forma que o caminho mais curto entre quaisquer dois
vértices v e w é a aresta (v,w).
Clique { 2,3,4}
Clique Máxima
{ 4,5,6,7}
Definições Básicas
Clique Máxima:
Uma clique C é máxima se não existe clique C' que seja maior que C.
Clique Máxima: {7,8,9,10}
Clique Maximal:
Uma clique C é maximal se não existe clique C' que seja superconjunto próprio de C.
Isto é, uma clique maximal é um grafo C tal que ele é um grafo completo.
Clique Maximal
C = C´
Exercícios
Exercício. Um químico deseja embarcar os produtos A,B,C,D,E,F,X usando o menor
número de caixas. Alguns produtos não podem ser colocados numa mesma caixa porque
reagem. Os produtos A,B,C,X reagem dois-a-dois; A reage com F e com D e viceversa; E também reage com F e com D e vice-versa.
Descreva o grafo que modela essa situação, mostre um diagrama desse grafo e use esse
grafo para descobrir o menor número de caixas necessárias para embarcar os produtos
com segurança.
Definições Básicas
Exercício. Adaltina esperava 4 amigas Brandelina, Clodina, Dejaina e Edina para um lanche
em sua casa.
Enquanto esperava preparou os lanches: Bauru, Misto quente, Misto frio e X-salada.
Brandelina gosta de Misto frio e de X-salada; Clodina de Bauru e X-salada; Dejaina gosta de
Misto quente e Misto frio; Edina gosta de Bauru e Misto quente.
Descreva o grafo que modela essa situação, mostre um diagrama desse grafo e use esse
grafo para descobrir se é possível que cada amiga de Adaltina tenha o lanche que gosta.
Exercícios
Exercícios 1. Prove que se V(G) possui Δ(G) ímpar o grafo é sempre par. (Prova por contra
exemplo)
Exercícios 2. Prove que num grafo G com (G) > 0 e |E(G)| < |V(G)| existem pelo menos
dois vértices de grau 1. (Prova por contra exemplo)
Exercícios 3. Mostre que todo grafo com dois ou mais vértices tem pelo menos dois
vértices de mesmo grau.
Definições Básicas
Caminho:
Um caminho é qualquer grafo da forma ({v1, v2, . . . , vn} , {vivi+1 : 1 ≤ i < n}). Em
outras palavras, um caminho é um grafo C cujo conjunto de vértices admite uma
permutação (v1, v2, . . . , vn) tal que
{v1v2, v2v3, . . . , vn−1vn} = A(C)
Os vértices v1 e vn são os extremos do caminho. O caminho que acabamos de descrever
pode ser denotado simplesmente por v1v2 · · · vn .
Por exemplo, o grafo ({u, v, w, z}, {wz, vz, uw}) é um caminho, que pode ser denotado por
uwzv.
Circuito e Caminho Euleriano
Caminhos eulerianos são caminhos nos quais se utilizam todas as arestas uma e uma só
vez num dado grafo.
Podemos ter um caminho aberto ou fechado (circuito).
A diferença entre um caminho euleriano aberto e um fechado está no final do
caminho.
Caso se parta e se chegue no mesmo vértice teremos um caminho fechado.
Caso a partida não coincida com a chegada teremos um caminho euleriano aberto.
Nos caminhos eulerianos, precisamos passar por todas as arestas do grafo e não
podemos repeti-las.
Uma forma de identificar um caminho eureliano é desenhar o grafo com lápis sem
tirá-lo do papel e sem redesenhar nenhuma parte .
Circuito e Caminho Euleriano
Exemplo 01:
Quais dos grafos direcionados abaixo possuem um circuito Euleriano?
Entre os que não tem, quais tem um caminho Euleriano?
Circuito e Caminho Euleriano
Exemplo 01:
Quais dos grafos direcionados abaixo possuem um circuito Euleriano?
Entre os que não tem, quais tem um caminho Euleriano?
Em H1 Existe um um caminho
Euleriano sem no entanto a
possibilidade de fechar circuito
Em H2 Existe um um
caminho e um circuito
Euleriano. Nesse o caminho
pode ser assim descrito.
{d-f-a-g-c-b-g-e-d}
Em H3 Não foi possível passar
por todas as arestas do grafo,
logo H3 não possui caminho
nem circuito.
Circuito e Caminho Euleriano
Exemplo 02:
G1
Quais dos grafos abaixo possuem caminho Euleriano?
G2
G3
Circuito e Caminho Euleriano
Exemplo 02:
Quais dos grafos abaixo possuem caminho Euleriano?
G1
Ao contrário do exemplo
anterior , o grafo G1 não é
orientado. Nesse caso,
existe somente um caminho
euleriano.
{d-c-b-a-d-b}
G2
Em G2 Não foi possível
passar por todas as arestas
do grafo.Logo G2 não
possui caminho nem
circuito euleriano.
G3
Em G3 Também não foi
possível passar por todas as
arestas do grafo.
Logo não há caminho nem
circuito euleriano.
Exercícios
Exemplo 02:
Quais dos grafos não direcionados abaixo possuem um circuito Euleriano?
Entre os que não tem, quais tem um caminho Euleriano?
Circuito e Caminho Euleriano
Teorema: Um grafo conexo G = (V, A) admite caminho euleriano se, e somente
se, todos os vértices tiverem grau par ou, apenas dois tiverem grau ímpar.
Prova: Se os vértices inicial e final do caminho são distintos, eles são os únicos
que podem ter grau ímpar, se orientados as arestas pelo sentido do caminho,
cada vértice intermediário terá d( xi ) /2 entradas e d( xi ) /2 saídas, onde d( xi )
representa o grau do vértice xi , ou então o caminho não poderá prosseguir, em
um dado momento sem repetir a aresta: logo, d( xi ) deverá ser par, para todo
vértice intermediário. Se o caminho é fechado todo vértice será intermediário e
não poderão existir vértices de grau ímpar.
Circuito e Caminho Hamiltoniano
Hamiltoniano:
Um circuito passando exatamente uma vez por cada vértice de um grafo é
chamado de circuito hamiltoniano, em homenagem ao matemático irlandês
William Rowan Hamilton (1805-1865), que estudou este problema no grafo
determinado pelas arestas de um dodecaedro regular.
• Caminho Hamiltoniano é caminho que passa por todos os vértices do
grafo uma única vez
• Circuito Hamiltoniano é circuito que parte de um vértice, visita todos os
outros vértices uma única vez e então retorna ao vértice inicial
Exercícios
Questão 00:
Quais dos grafos abaixo possuem um caminho Hamiltoniano?
Entre os que não tem, quais os grafos que possuem circuitos
Hamiltoniano?
Exercícios
Questão 01
Construa um algoritmo em texto puro , que leia um grafo G
qualquer e que apresente como resultado seu vetor de graus.
Observação:
O algoritmo deverá varrer o grafo todo utilizando apenas a ideia
de busca.
Questão 02
Construa um segundo algoritmo , também em texto puro, que
leia um grafo G qualquer, capaz identificar a clique máxima desse
grafo.
Observação:
Utilize o mesmo procedimento de busca feito na questão 01 e
quantifique quantas operações foram realizadas em função da
quantidade de vértices.
Complexidade de algoritmos em grafos.
Neste texto entendemos por complexidade do algoritmo a complexidade de tempo no pior
caso.
Exemplo:
Sejam A e B dois algoritmos distintos que executam a mesma tarefa sobre um grafo G =(V,E).
O algoritmo A gasta, no pior caso, |V |2 passos para executar a tarefa e o algoritmo B gasta
(|V | + |E|)log |E|passos no pior caso.
Para grafos com |V |2∕4 arestas o primeiro algoritmo é sempre melhor enquanto que para
grafos com 1.000|V | arestas o segundo algoritmo é assintoticamente melhor (melhor
para |V |≥ 16.645, enquanto que o primeiro é melhor para |V |≤ 16.644).
Para entradas pequenas (até 25 mil vértices) a ordem das funções são comparadas nos gráficos

similar documents