Teoria dos Grafos 2011/1 Clique em Grafosclaudiaboeres.pbworks.com/f/Clique em Grafos - Maycon.pdf · Teoria dos Grafos 2011/1 Clique em Grafos ... tal que paracada par de vérticesue

  • 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