Conjuntos Dominantes e o Problema das Rainhas

Conjuntos Dominantes 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 dominante se para todo v V G Nv S 1 Exemplo a b c d e f g h i Na S Nb S Ng S a h Nc S Nd S Ne S Nf S i Nh S a h i Ni S h i Nv S 1 Definições Definição 2 Seja G um grafo Um subconjunto S V G é um conjunto dominante se para todo v V G Nv S 1 Exemplo a b c d e f g h i Definições Definição 3 Um conjunto dominante D é dito conjunto dominante minimal se não existir um conjunto dominante D tal que D D Exemplo Definições Definição 3 Um conjunto dominante D é dito conjunto dominante minimal se não existir um conjunto dominante D tal que D D Exemplo a b c d e f g h i Definições Definição 3 Um conjunto dominante D é dito conjunto dominante minimal se não existir um conjunto dominante D tal que D D Exemplo a b c d e f g h i Definições Definição 3 Um conjunto dominante D é dito conjunto dominante minimal se não existir um conjunto dominante D tal que D D Exemplo a b c d e f g h i Definições Definição 4 O número de dominação é a cardinalidade do menor conjunto dominante minimal de G e é denotado por γG Exemplo de grafo com γG 2 Definições Definição 4 O número de dominação é a cardinalidade do menor conjunto dominante minimal de G e é denotado por γG Exemplo de grafo com γG 2 a b c d e f g h i O problema das rainhas O problema O problema consiste em determinar o número mínimo de rainhas dispostas sobre um tabuleiro de xadrez de forma que todas as posições do tabuleiro podem ser atacadas por pelo menos uma rainha ou esteja ocupada por uma Regra do Xadrez Segundo as regras do xadrez uma rainha pode se movimentar horizontalmente verticalmente ou nas diagonais O problema das rainhas O problema O problema consiste em determinar o número mínimo de rainhas dispostas sobre um tabuleiro de xadrez de forma que todas as posições do tabuleiro podem ser atacadas por pelo menos uma rainha ou esteja ocupada por uma Regra do Xadrez Segundo as regras do xadrez uma rainha pode se movimentar horizontalmente verticalmente ou nas diagonais O problema das rainhas O problema O problema consiste em determinar o número mínimo de rainhas dispostas sobre um tabuleiro de xadrez de forma que todas as posições do tabuleiro podem ser atacadas por pelo menos uma rainha ou esteja ocupada por uma Regra do Xadrez Segundo as regras do xadrez uma rainha pode se movimentar horizontalmente verticalmente ou nas diagonais O problema das rainhas O número mínimo para dominar um tabuleiro de xadrez de 8 8 é cinco Uma solução possível O problema das rainhas O problema das rainhas pode ser definido de forma mais geral como um problema de conjunto dominantes em grafos Como Seja um tabuleiro r s em que r é o número de linhas e s o número de colunas Cada vértice representa uma posição do tabuleiro Existe uma aresta vw se e somente se uma rainha localizada na posição definida pelo vértice v puder se movimentar para o vértice w Solucionar o problema das rainhas é equivalente a encontrar o menor conjunto dominante no grafo que representa o tabuleiro Limites para o número de dominação Um limite óbvio 1 γG n Limites para o número de dominação Teorema Se S V G é um conjunto dominante minimal de um grafo conexo G V E então V S também é um conjunto dominante Demonstração Seja S V G um conjunto dominante minimal de G Como S é dominante todos os vértices de V S também são adjacentes a um vértice de S Como S é minimal todo vértice v de S também é adjacente a algum vértice de V S senão S v seria também dominante LogoV S também é dominante Limites para o número de dominação Corolário Seja G V E um grafo sem vértices isolados e de ordem n Então γG n2 Conjuntos dominantes e conjuntos independentes Conjunto independente 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 Conjunto independente maximal Um conjunto independente S é maximal se S não é subconjunto próprio de nenhum outro conjunto independente de G Conjunto independente e conjunto dominante Um conjunto independente maximal é sempre dominante Um conjunto dominante mínimo pode não ser independente a b c d e f g h i