Conjuntos Independentes - Definições e Características

Conjuntos Independentes Erika Morais Instituto de Informática Universidade Federal de Goiás Definições Definição 1 Seja G um grafo Um subconjunto S V G é um conjunto independente se todos os vértices de S são dois a dois não adjacentes Em outras palavras um conjunto S de vértices de um grafo G é independente se o grafo induzido GS não possui arestas 1 3 7 4 2 5 8 6 Definições Definição 1 Seja G um grafo Um subconjunto S V G é um conjunto independente se todos os vértices de S são dois a dois não adjacentes Em outras palavras um conjunto S de vértices de um grafo G é independente se o grafo induzido GS não possui arestas 1 3 7 4 2 5 8 6 Definições Definição 1 Seja G um grafo Um subconjunto S V G é um conjunto independente se todos os vértices de S são dois a dois não adjacentes Em outras palavras um conjunto S de vértices de um grafo G é independente se o grafo induzido GS não possui arestas 1 3 7 4 2 5 8 6 Definições Definição 1 Seja G um grafo Um subconjunto S V G é um conjunto independente se todos os vértices de S são dois a dois não adjacentes Em outras palavras um conjunto S de vértices de um grafo G é independente se o grafo induzido GS não possui arestas 1 3 7 4 2 5 8 6 Definições Definição 1 Seja G um grafo Um subconjunto S V G é um conjunto independente se todos os vértices de S são dois a dois não adjacentes Em outras palavras um conjunto S de vértices de um grafo G é independente se o grafo induzido GS não possui arestas Definições Definição 1 Seja G um grafo Um subconjunto S V G é um conjunto independente se todos os vértices de S são dois a dois não adjacentes Em outras palavras um conjunto S de vértices de um grafo G é independente se o grafo induzido GS não possui arestas 1 3 7 4 2 5 8 6 Definições Definição 2 Um conjunto independente S é maximal se S não é subconjunto próprio de nenhum outro conjunto independente de G 1 3 7 4 2 5 8 6 Definição 3 Um conjunto independente S é máximo se nenhum outro conjunto independente S de G satisfaz S S Definições Definição 2 Um conjunto independente S é maximal se S não é subconjunto próprio de nenhum outro conjunto independente de G 1 3 7 4 2 5 8 6 Definição 3 Um conjunto independente S é máximo se nenhum outro conjunto independente S de G satisfaz S S Definições Definição 2 Um conjunto independente S é maximal se S não é subconjunto próprio de nenhum outro conjunto independente de G 1 3 7 4 2 5 8 6 Definição 3 Um conjunto independente S é máximo se nenhum outro conjunto independente S de G satisfaz S S Definições Definição 4 O número de vértices em um conjunto independente máximo de G é chamado de número de independência de G e é denotado por αG 1 3 7 4 2 5 8 6 αG 6 Determine a αKn b αCn Exemplo Grafo da rainha Um tabuleiro de xadrez n n tem n2 quadrados Uma rainha em uma dada posição controla todos os quadrados na mesma linha na mesma coluna e nas duas diagonais que contêm este quadrado Um grafo simples pode ser usado para determinar o número máximo de rainhas que podem ser colocadas no tabuleiro de forma que elas não se ataquem mutualmente Exemplo Grafo da rainha 3por3 O grafo simples tem 9 vértices um para cada quadrado e dois vértices são adjacentes se uma dama do jogo de xadrez pode saltar de um deles para o outro em um só movimento Questão Calcule αG onde G é o grafo da rainha 3por3 αG 2 Exemplo Grafo da rainha 3por3 O grafo simples tem 9 vértices um para cada quadrado e dois vértices são adjacentes se uma dama do jogo de xadrez pode saltar de um deles para o outro em um só movimento Questão Calcule αG onde G é o grafo da rainha 3por3 αG 2 Exemplo Grafo da rainha 3por3 O grafo simples tem 9 vértices um para cada quadrado e dois vértices são adjacentes se uma dama do jogo de xadrez pode saltar de um deles para o outro em um só movimento Questão Calcule αG onde G é o grafo da rainha 3por3 αG 2 Exemplo Grafo da rainha 3por3 O grafo simples tem 9 vértices um para cada quadrado e dois vértices são adjacentes se uma dama do jogo de xadrez pode saltar de um deles para o outro em um só movimento Questão Calcule αG onde G é o grafo da rainha 3por3 αG 2 Exemplo Grafo da rainha 3por3 O grafo simples tem 9 vértices um para cada quadrado e dois vértices são adjacentes se uma dama do jogo de xadrez pode saltar de um deles para o outro em um só movimento Questão Calcule αG onde G é o grafo da rainha 3por3 αG 2 Cobertura Definição 5 Um subconjunto K V G tal que toda aresta de G tem pelo menos um vértice em K é chamado uma cobertura de G Definição 6 O número de vértices em uma cobertura mínima de G é chamado de número de cobertura de G e é denotado por βG Cobertura Definição 5 Um subconjunto K V G tal que toda aresta de G tem pelo menos um vértice em K é chamado uma cobertura de G Definição 6 O número de vértices em uma cobertura mínima de G é chamado de número de cobertura de G e é denotado por βG Cobertura Definição 5 Um subconjunto K V G tal que toda aresta de G tem pelo menos um vértice em K é chamado uma cobertura de G Definição 6 O número de vértices em uma cobertura mínima de G é chamado de número de cobertura de G e é denotado por βG Cobertura Definição 5 Um subconjunto K V G tal que toda aresta de G tem pelo menos um vértice em K é chamado uma cobertura de G Definição 6 O número de vértices em uma cobertura mínima de G é chamado de número de cobertura de G e é denotado por βG Cobertura Teorema 1 Um subconjunto S V G é um conjunto independente se e somente se V S é uma cobertura de G Demonstração Por definição S é um conjunto independente de G se e somente se nenhuma aresta de G tem ambos vértices finais em S Isto é se cada aresta tem pelo menos um vértice em V S Logo S é independente se e somente se V S é uma cobertura de G Conjunto independente e cobertura Corolário 1 α β n Demonstração Seja S um conjunto independente máximo e K uma cobertura mínima de G Então pelo Teorema 1 V K é um conjunto independente e V S é uma cobertura de G Logo n β V K α e n α V S β Combinando as duas desigualdades temos que α β n Cobertura Aplicação Vigilância em galeria de arte Considere uma galeria de arte com muitos corredores e curvas Esta galeria está exibindo pinturas muito valiosas e o gerente deseja mantêlas seguras Ele planeja instalar câmeras de segurança em cada corredor de modo que as câmeras monitorem todas as pinturas à vista Se houver uma câmera de segurança em um corredor ela poderá monitorar todas as pinturas no corredor Se houver uma câmera no canto onde dois corredores se encontram a curva a camera pode monitorar as pinturas em ambos os corredores O gerente planeja comprar o mínimo de câmeras necessárias para monitorar todos os corredores da galeria Determine o número minímo de câmeras que o gerente deve comprar para monitorar todos os corredores da galeria Cobertura Aplicação Solução Considere que os vértices representam os lugares onde os corredores se encontram ou quando um corredor se torna um beco sem saída e as arestas representam os corredores Uma cobertura mínima representa o número mínimo de câmeras que o gerente deve comprar para monitorar todos os corredores da galeria Cobertura Aplicação Solução Considere que os vértices representam os lugares onde os corredores se encontram ou quando um corredor se torna um beco sem saída e as arestas representam os corredores Uma cobertura mínima representa o número mínimo de câmeras que o gerente deve comprar para monitorar todos os corredores da galeria Cobertura Aplicação Solução Considere que os vértices representam os lugares onde os corredores se encontram ou quando um corredor se torna um beco sem saída e as arestas representam os corredores Uma cobertura mínima representa o número mínimo de câmeras que o gerente deve comprar para monitorar todos os corredores da galeria Cobertura Aplicação Solução Considere que os vértices representam os lugares onde os corredores se encontram ou quando um corredor se torna um beco sem saída e as arestas representam os corredores Uma cobertura mínima representa o número mínimo de câmeras que o gerente deve comprar para monitorar todos os corredores da galeria Cobertura Aplicação Solução Considere que os vértices representam os lugares onde os corredores se encontram ou quando um corredor se torna um beco sem saída e as arestas representam os corredores Uma cobertura mínima representa o número mínimo de câmeras que o gerente deve comprar para monitorar todos os corredores da galeria Conjuntos independentes cliques Definição 7 Uma clique maximal em um grafo G é um subgrafo induzido de G que é um grafo completo e que não está estritamente contido em outras cliques Definição 8 O número de clique de um grafo G denotado por ωG é o tamanho máximo de uma clique de G Conjuntos independentes cliques Definição 7 Uma clique maximal em um grafo G é um subgrafo induzido de G que é um grafo completo e que não está estritamente contido em outras cliques Definição 8 O número de clique de um grafo G denotado por ωG é o tamanho máximo de uma clique de G Conjuntos independentes cliques Observação ωG α G Conjuntos independentes cliques Observação ωG α G