If you can't read please download the document
Upload
doannhi
View
251
Download
9
Embed Size (px)
Citation preview
Teoria dos Grafos2011/1
Clique em Grafos
Professora: Claudia BoeresAluno: Maycon Maia Vitali
Agenda Definio do Problema Formulao do Problema Mtodos de Soluo Aplicaes ;-) Concluso
Definio do Problema
Definio do Problema
Definio do Problema
Definio do Problema
Representao em Grafos
1
3
2
4
Formulao do Problema
Um clique em um grafo no orientadoG=(V , E) um subconjunto do conjunto de vrtices CV ,tal que para cada par de vrtices u e vV de C ,
existe uma aresta {u , v }E.
Formulao do Problema
Um clique em um grafo no orientadoG=(V , E) um subconjunto do conjunto de vrtices CV ,tal que para cada par de vrtices u e vV de C ,
existe uma aresta {u , v }E.
Todo vrtice um clique do grafo. Toda aresta liga dois vrtices que formam um clique do grafo.
Clique Maximal
Um clique maximal um clique que no subconjunto de outro clique ,ou seja ,
um subconjunto C V que clique emG e queno exista um outro subconjunto C+{v }V que
tambm seja clique emG , para v V .
Clique Mximo
Um clique mximo um clique C V de G ,tal queno exista outro clique C ' V comC '>C, ou seja ,
o clique mximo um clique que possui o maior nmero devrtices possveis.
Mtodos de Soluo Algoritmo Exato
Heursticas Abordagem Gulosa Algoritmos Genticos etc
Aplicaes Aplicaes em Redes Sociais
Aplicaes em outras reasConjunto mximo independenteColorao em grafos planaresCaixeiro viajanteAcoplamento mximoEtc
NP-Completo \o/
Aplicaes Aplicaes em Redes Sociais Aplicaes em outras reas
Conjunto mximo independenteColorao em grafos planaresCaixeiro viajanteAcoplamento mximoEtc
NP-Completo \o/
Aplicaes Aplicaes em Redes Sociais Aplicaes em outras reas
Conjunto mximo independenteColorao em grafos planaresCaixeiro viajanteAcoplamento mximoEtc
NP-Completo \o/
Aplicaes Aplicaes em Redes Sociais Aplicaes em outras reas
Conjunto mximo independente Colorao em grafos planares
Caixeiro viajanteAcoplamento mximoEtc
NP-Completo \o/
Aplicaes Aplicaes em Redes Sociais Aplicaes em outras reas
Conjunto mximo independente Colorao em grafos planares Caixeiro viajante
Acoplamento mximoEtc
NP-Completo \o/
Aplicaes Aplicaes em Redes Sociais Aplicaes em outras reas
Conjunto mximo independente Colorao em grafos planares Caixeiro viajante Acoplamento mximo Etc
NP-Completo \o/
Aplicaes Aplicaes em Redes Sociais Aplicaes em outras reas
Conjunto mximo independente Colorao em grafos planares Caixeiro viajante Acoplamento mximo Etc
NP-Completo \o/
Aplicaes Aplicaes em Redes Sociais Aplicaes em outras reas
Conjunto mximo independente Colorao em grafos planares Caixeiro viajante Acoplamento mximo Etc
NP-Completo \o/
Concluso
Dvidas
Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22