Notas de Aula: Teoria dos Grafos

Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Notas de aula da disciplina Teoria dos Grafos Esse material é um compilado dos seguintes Sedgewick R Algorithms in C part 5 graph algorithms 3rd ed AddisonWesley 2002 Bondy J A Murty U S R Graph Theory Graduate Texts in Mathematics Springer New York 2008 Lintzmayer C N Mota G O Notas de aulas Análise de algoritmos e estruturas de dados Em construção 14 Aula 19 emparelhamentos e conjuntos independen tes Um emparelhamento em um grafo G é um conjunto M EG tal que quaisquer duas arestas de M não têm extremos em comum As arestas de M são duas a duas nãoadjacentes Uma aresta sozinha já forma um emparelhamento então os problemas mais inte ressantes aqui envolvem encontrar um emparelhamento de maior tamanho possível Ou de maior custo possível caso as arestas do grafo tenham custos associados Um conjunto independente em um grafo G é um conjunto I V G tal que os vértices em I são dois a dois nãoadjacentes Ou seja EGI Note que uma aresta sozinha já forma um emparelhamento assim como um vértice sozinho já forma um conjunto independente Então os problemas mais interessantes aqui são de maximização Qual o maior conjunto independente de um dado grafo Qual o maior emparelhamento de um dado grafo Caso o grafo tenha custos associados às arestas então o custo de um emparelha mento deixa de ser sua cardinalidade e passa a ser a soma dos custos das arestas contidas nele De forma equivalente caso o grafo tenha custos associados aos vértices então o custo de um conjunto independente também deixa de ser sua cardinalidade e passa a ser a soma dos custos dos vértices contidos nele Encontrar o maior emparelhamento ou o mais custoso em um grafo é um problema fácil no sentido de que existem algoritmos de tempo polinomial que o resolvem Encontrar o maior conjunto independente ou o mais custoso por sua vez é um problema NPdifícil 100 141 Emparelhamentos Seja M um emparelhamento em um grafo G para uv M dizemos que u e v estão emparelhados por M e escrevemos Mu v e Mv u para X V G dizemos M cobre X se cada vértice de X é extremo de alguma aresta em M M é perfeito se cobre V G M é maximal de não está contido em outro emparelhamento M é máximo se G não possui outro emparelhamento maior do que M se v V G não é coberto por M então v é dito livre em M Note que nem todo grafo possui um emparelhamento perfeito Qual o número de arestas que um emparelhamento perfeito tem Qual o maior número de arestas que um emparelhamento pode ter Motivação casamento estável residentes e hospitais doação de rins Problemas de interesse Verificar se um dado emparelhamento é máximo Decidir se um grafo possui um emparelhamento perfeito Encontrar um emparelhamento de tamanho máximo em um grafo algoritmo de Egerváry Húngaro se G é bipartido OV E algoritmo de HopcroftKarp se G é bipartido OE log V algoritmo de Edmonds OV 2E algoritmo de Blum OE log V melhor conhecido Seja M um emparelhamento em um grafo G um caminho Malternante em G é um caminho cujas arestas alternam entre arestas de M e de EG M um ciclo Malternante em G é um ciclo cujas arestas alternam entre arestas de M e de EG M O teorema a seguir apresenta uma caracterização de emparelhamento máximo em qualquer grafo 101 Teorema 141 Berge 1957 Seja G um grafo e M um emparelhamento em G O emparelhamento M é máximo se e somente se G não possui um caminho M alternante cujos extremos são livres Demonstração Primeiro vamos mostrar que se M é máximo então G não possui um caminho Malternante cujos extremos são livres Seja M um emparelhamento máximo em G Suponha para fins de contradição que exista um tal caminho P em G Seja M MEPEPM Note que nenhuma aresta de MEP é incidente a vértices de P pois os extremos de P são livres Logo M é um emparelhamento Como ambos extremos de P são livres EP M EP M 1 Então M M EP EP M M EP EP M 1 M 1 uma contradição Agora vamos provar que se G não possui um caminho Malternante com extremos livres então M é máximo Suponha que nenhum caminho Malternante em G tem os extremos livres e suponha para fins de contradição que M não é máximo Seja então M máximo logo M M Seja H GM M M M Note que as componentes de H são caminhos ou ciclos cujas arestas alternam entre M e M Então H 2 Além disso cada ciclo de H tem um número par de arestas Assim como M M ao menos uma componente de H é um caminho P que tem mais arestas de M do que de M As arestas nos extremos de P portanto são de M Mas então P é um caminho Malternante com os extremos livres em M uma contradição Lembrese que dado um grafo G e um conjunto S V G o conjunto GS é o conjunto de arestas uv EG u S e v S isto é o conjunto de arestas que cruzam o corte S V G S O teorema a seguir nos dá uma caracterização de grafos bipartidos que possuem um emparelhamento que cobre uma parte Seu resultado implica que basta mostrar um subconjunto de X com poucos vizinhos para provar que G não possui um emparelhamento que cobre X onde X é uma das partes da bipartição 102 Teorema 142 Hall 1935 Seja G um grafo conexo X Y bipartido com X Y O grafo G possui um emparelhamento que cobre X se e somente se NS S para todo S X Demonstração Primeiro vamos provar que se G possui um emparelhamento que co bre X então NS S para todo S X Seja M um emparelhamento de G que cobre X Tome um S X qualquer Para todo u S o vértice Mu está em NS Assim NS S Agora vamos provar que se NS S para todo S X então G possui um emparelhamento que cobre X Suponha para fins de contradição que G não possui um emparelhamento que cobre X Seja M um emparelhamento máximo em G e seja a X um vértice livre em M Seja Z v V G existe avcaminho Malternante em G Sejam S Z X e T Z Y Note que a S Considere um percurso em um caminho Malternante que começa em a Note que chegamos em T por arestas de EG M e saímos de T por arestas de M Exceto por a chegamos em S a por arestas de M Então os vértices de T estão emparelhados aos vértices de S a por M Ou seja todo vértice de T é coberto por M e portanto T S 1 e T NS Assim T NS S 1 S contrariando a hipótese 103 142 Conjuntos independentes Seja I um conjunto independente em um grafo G I é maximal se não está contido em nenhum outro conjunto independente I é máximo se G não possui outro conjunto independente maior do que I Denotamos por αG a cardinalidade de um conjunto independente máximo em G também chamado número de estabilidade de G Em inglês um conjunto independente pode ser chamado de independent set ou de stable set Uma clique em um grafo G é um conjunto S V G tal que os vértices em S são dois a dois adjacentes Ou seja GS é um grafo completo Novamente um único vértice já é uma clique então sempre é interessante encontrar cliques máximas Denotamos por ωG a cardinalidade de uma clique máxima em G O resultado a seguir implica que αG ωG Teorema 143 Seja G um grafo e S V G Então S é uma clique em G se e somente se S é um conjunto independente em G Para mostrar resultados do tipo αG k basta apresentar um conjunto indepen dente que tenha tamanho k ou então mostrar k vértices que com certeza tenham que fazer parte de qualquer conjunto independente em G E para mostrar resultados do tipo αG k Por exemplo αG V G Ou então αG V G ωG 1 Lema 144 Para todo grafo G αG EG δG Demonstração Seja X um conjunto independente máximo de G Note que a quan 104 tidade de arestas que tém algum extremo em X é Dd de HG XG aG5G vEx vEx Por outro lado a quantidade de arestas no grafo é EG d0ydv Assim EG aGdG de onde o resultado segue O e O resultado do lema anterior nao pode ser melhorado pois aC n2 LLECn0Cn J e Por outro lado aK 1 e EKdKn n2 Lema 145 Para todo grafo G aG oT Demonstragao Seja X um conjunto independente maximal em G Note que todo vértice de VG X tem pelo menos um vizinho em X caso contrério X nao seria maximal Entao IVQX So dv vex Por outro lado todo vértice de X tem no maximo AG vizinhos Entao de XIAG vex Juntando as duas inequacoes temos IVG X XAG VG X X XAG X IVG XAG 1 E 0 resultado segue pois X aG oO e O resultado do lema anterior nao pode ser melhorado pois aK 1 NK JST 2 2 e Por outro lado a Kn n mas AK1 I x 2 105 15 Aula 19 coloração de vértices e de arestas Seja G um grafo Uma kcoloração própria de G é uma função c V G 1 k tal que cx cy para toda xy EG Cada inteiro i 1 k é chamado de cor Definição equivalente é uma partição C C1 C2 Ck de V G em conjuntos independentes isto é Ci Cj para todo i j e V G k i1Ci Cada conjunto independente Ci é chamado de classe de cor Uma karestacoloração própria de G é uma função c EG 1 k tal que cxy cxz para todo xy xz EG e y z Definição equivalente é uma partição M M1 Mk de EG em emparelha mentos Claramente todo grafo de ordem n possui uma ncoloração assim como todo grafo com m arestas possui uma marestacoloração então o interessante nesses problemas é minimizar o número de cores usadas Os dois problemas são igualmente difíceis 106