Sobre Algoritmo de Emparelhamento Máximo e Grafos p ... · PDF fileANDRÉ DA CUNHA RIBEIRO Sobre Algoritmo de Emparelhamento Máximo e Grafos p-extensíveis Dissertação defendida

Mod

eloUNIVERSIDADE FEDERAL DE GOIÁS

INSTITUTO DE INFORMÁTICA

ANDRÉ DA CUNHA RIBEIRO

Sobre Algoritmo de EmparelhamentoMáximo e Grafos p-extensíveis

Goiânia2008



Dissertação apresentada ao Programa de Pós–Graduação doInstituto de Informática da Universidade Federal de Goiás,como requisito parcial para obtenção do título de Mestre emCiência da Computação.

Área de concentração:Algoritmos e Teoria dos Grafos.

Orientadora: Profa. Diane Castonguay

Goiânia2008



Dissertação defendida no Programa de Pós–Graduação do Instituto deInformática da Universidade Federal de Goiás como requisito parcialpara obtenção do título de Mestre em Ciência da Computação, aprovadaem 28 de Março de 2008, pela Banca Examinadora constituída pelosprofessores:

Profa. Diane CastonguayInstituto de Informática – UFG

Presidente da Banca

Prof. Fábio ProttiInstituto de Matemática – UFRJ

Prof. Humberto José LongoInstituto de Informática – UFG

Todos os direitos reservados. É proibida a reprodução totalou parcial dotrabalho sem autorização da universidade, do autor e do orientador(a).

André da Cunha Ribeiro

Possui graduação em Ciência Habilitação em Matemática pela Universidadede Rio Verde (1994) e pós-graduação lato sensu em Ciências da Computaçãopela Universidade Católica de Goiás (1998). Atualmente é professor titular doCentro Federal de Educação Tecnologica de Rio Verde-GO. Tem experiênciana área de Ciência da Computação, atuando principalmente nos seguintes te-mas: software livre, banco de dados, algoritmo e programação de computado-res. Durante o Mestrado, na UFG - Universidade Federal de Goiás, foi bolsistada CAPES pelo Programa Institucional de Qualificação Docentepara a RedeFederal de Educação Profissional e Tecnológica (PIQDTEC) e desenvolveuum trabalho teórico sobre grafos extensíveis.

Dedico este trabalho a Vanessa Cunha e Maria Helena da Cunha.

Agradecimentos

Agradeço primeiramente a Deus, pela força e saúde que tive para superar todos

os obstáculos encontrados. Agradeço a toda a minha família pelo apoio recebido, princi-

palmente a minha esposa, meus pais, minha irmã e meus sobrinhos. Agradeço a minha

orientadora, professora Diane, pela atenção dispensada e pela confiança que sempre de-

monstrou ter em mim, desde o início do curso. Agradeço ao professor Rommel, ao apoio

na realização deste trabalho e pela possibilidade de realizar um intercâmbio na COPPE da

UFRJ. Agradeço aos professores Fábio e Humberto pela colaboração no aprimoramento

dessa dissertação. Agradeço a todos os professores e colegas que colaboraram, direta ou

indiretamente na realização do meu mestrado. Agradeço ao CEFET Rio Verde pela libe-

ração e apoio financeiro para a realização desse trabalho.

"O que vale na vida não é o ponto de partida e sim a caminhada.Caminhando e semeando, no fim terás o que colher."

Cora Coralina,Poetisa goiana.

Resumo

Ribeiro, André da Cunha.Sobre Algoritmo de Emparelhamento Máximo eGrafos p-extensíveis. Goiânia, 2008.85p. Dissertação de Mestrado. Institutode Informática, Universidade Federal de Goiás.

Um grafo G = (V,E), de ordem parn = |V|, é p-extensível, ondep é um número

entre 0 e(n/2)−1, seG tem emparelhamento perfeito e se todo conjunto dep arestas

independentes se estende para um emparelhamento perfeito.Exibimos várias famílias de

grafosp-extensíveis. A extensibilidade deG é o maior valor dep, tal queG é p-extensível.

Estudamos limites para a extensibilidade de algumas classes de grafos. Estruturamos o

algoritmo de Kameda e Munro, que encontra o emparelhamento máximo em um grafo

com a complexidade de tempoO(nm). Baseado neste algoritmo de emparelhamento

máximo trabalhamos na estruturação do algoritmo de Lou, Saito e Teng, que determina

se um grafoG é 1-extensível emO(m2).

Palavras–chave

Grafos, Emparelhamento Máximo, Emparelhamento Perfeito,Grafos p-

extensíveis, Extensibilidade.

Abstract

Ribeiro, André da Cunha.Maximum matching algorithm and p-extendablegraphs. Goiânia, 2008.85p. MSc. Dissertation. Instituto de Informática, Uni-versidade Federal de Goiás.

A graphG = (V,E) of even ordern = |V| is p-extendable, withp an integer such that

0≤ p < n/2, if it contains a perfect matching and if every matching ofp independent

edges extends to a perfect matching ofG. In this dissertation, we present a large family of

examples ofp-extendable graphs. The extendability ofG is the maximum value ofp, such

that G is p-extendable. We study limits for the extendability of some classes of graphs.

We structure the algorithm of Kameda and Munro, that finds themaximum matching in

a graph with the complexity of timeO(nm). Based on this algorithm, we structure the

algorithm present by Lou, Saito and Teng, which determine ifa graph is 1-extendable in

O(m2).

Keywords

Graphs, Maximum Matching, Perfect Matching,p-extendable Graphs, Extend-

ability.

Sumário

Lista de Figuras 10

Lista de Algoritmos 13

Introdução 14

1 Preliminares 17

2 Emparelhamento 252.1 Emparelhamento máximo 262.2 Algoritmo de Emparelhamento Máximo 292.3 Correção do algoritmo de emparelhamento máximo 422.4 Complexidade do algoritmo de emparelhamento máximo 442.5 Emparelhamento máximo em grafos bipartidos 45

3 Grafos p-extensíveis 493.1 Definições Básicas 493.2 Grafos bipartidos 553.3 Grafos fator-crítico 593.4 Grafos planares 603.5 Grafos livre de K1,3 643.6 Árvores 663.7 Grau mínimo 67

4 Algoritmos para grafos extensíveis 694.1 Algoritmo 1-extensível 694.2 O problema p-extensível é co-NP 75

Conclusão 79

Referências Bibliográficas 81

Índice Remissivo 84

Lista de Figuras

1.1 Grafo simples. 171.2 2−regular. 181.3 K3. 181.4 Grafos bipartidos. 19

(a) GrafoK2,2 19(b) Grafo bipartido 19(c) CompletoK3,3 19

1.5 Subgrafos induzidos. 20(a) GrafoG 20(b) GrafoH 20(c) GrafoI 20

1.6 Subgrafos geradores. 20(a) G 20(b) H 20(c) I 20

1.7 Emparelhamentos. 22(a) Maximal. 22(b) Máximo e Perfeito. 22

1.8 Cubo. 231.9 Fator-crítico. 24

(a) 1−fator-crítico. 24(b) 2−fator-crítico. 24

1.10 3−fator-crítico. 24

2.1 Grafo bipartido. 252.2 Broto 262.3 Emparelhamento M 272.4 Caminho P 282.5 Emparelhamento P⊕M 282.6 Caminhos nos brotos. 33

(a) GrafoG 33(b) GrafoH 33

2.7 Processo de rotulação. 33(a) CaminhoM-alternante 33(b) S1 33(c) S2 33

2.8 Rotulação do broto. 36(a) Broto 36

(b) S1 36(c) S2 36

2.9 Encontro de um broto e um sub-broto. 38(a) Encontro do sub-broto 38(b) S1 38(c) S2 38(d) Rotulação do broto e sub-broto 38(e) S1 38(f) S2 38

2.10 Caminho aumentante. 402.11 Teorema de Hall. 462.12 Grafos bipartidos com emparelhamento perfeito. 47

(a) k−regular 47(b) não regular 47

2.13 Grafos (X,Y)−bipartidos. 47(a) Com emparelhamento perfeito 47(b) Sem emparelhamento perfeito 47

2.14 Sem emparelhamento perfeito. 48

3.1 Grafos extensíveis. 50(a) 1−extensível 50(b) 2−extensíveis 50

3.2 Grafo C8. 523.3 Grafos extensíveis. 53

(a) Bipartido 53(b) Bicrítico 53(c) 1-extensível 53

3.4 Produto de grafos. 54(a) 54(b) 1-extensível 54(c) 2-extensível 54

3.5 Conjuntos A. 55(a) Estende 55(b) Não estende 55

3.6 Grafos da família Gn,p. 56(a) G4,1 56(b) G6,2 56(c) G8,3 56

3.7 Família 2Ct . 563.8 Grafo residual. 583.9 Grafos bipartidos. 60

(a) 0-fator-crítico 60(b) n-fator-crítico 60

3.10 Grafo com o componente borboleta. 603.11 Grafo G3

1. 623.12 Grafo H4

1 . 623.13 Grafo H4

2 . 63

3.14 F(1,3). 653.15 Grafo R(2), As arestas dos K9 não são mostradas. 663.16 Livre K1,3. 663.17 Árvores. 67

(a) Sem emparelhamento 67(b) Com emparelhamento 67

3.18 4-regular. 68

4.1 Grafo 1-extensível. 72(a) GrafoG 72(b) x0y0 /∈M 72(c) SubgrafoH 72

4.2 Grafo que não é 1-extensível. 73(a) GrafoG 73(b) x0y0 /∈M 73(c) SubgrafoH 73

Lista de Algoritmos

2.1 MétodoBerge 292.2 EmparelhamentoMáximo 302.3 caminho-aumentante() 322.4 caminho-alternante() 352.5 encontrar-broto() 372.6 verificar-pilhas() 392.7 atualizar-pilhas() 402.8 aumentar-emparelhamento() 414.1 1-extensível 704.2 diminuir-lista() 714.3 1-extensível-ingênuo 754.4 Decisão co-NP 764.5 Extensível 77

Introdução

A ciência da computação é o estudo dos algoritmos e de suas aplicações, bem

como das estruturas matemáticas indispensáveis à sua formulação. Ela precisa desses

conceitos fundamentais tanto para a teoria da complexidadecomputacional, quanto para

a computação aplicada.

Na complexidade computacional estudamos a classificação dos problemas de

decisão. Um problema de decisão é o problema que possui apenas duas respostas: sim

ou não. Nesta dissertação restringimos a problemas de decisão. Indiretamente, porém,

tratamos de outros tipos de problemas. Afinal, a existência de um algoritmo polinomial

para o problema de decisão implicaria em um algoritmo polinomial para o problema de

otimização. Outra maneira de entender problemas de decisãoé como reconhecimento de

linguagens. Todo problema de decisão pode ser visto como, dada uma entradax, decidir

sex∈ L para uma linguagem específicaL.

A classeP é o conjunto de problemas de decisão que pode ser resolvidos por

um algoritmo polinomial. A sigla P surgiu dedeterministic polinomial time(tempo

polinomial determinístico), pois uma outra definição para aclasseP é a classe dos

problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing

determinística e essas máquinas modela o computador que temos hoje.

A classeNP é um conjunto de problemas de decisão que tem um algoritmo de

verificação em tempo polinomial para um certificado polinomial quando a resposta for

sim. A siglaNP surgiu denon-deterministic polinomial time(tempo polinomial não de-

terminístico), pois uma outra definição para a classeNP é a classe dos problemas que

podem ser resolvidos em tempo polinomial por uma máquina de Turing não determinís-

tica. Sem entrarmos em muitos detalhes, uma máquina de Turing não determinística é um

modelo para um computador que pode, a cada instrução executada, se bifurcar em dois ca-

minhos de processamento distintos, respondendo sim caso algum caminho responda sim

e não, caso todos os caminhos respondam não. A máquina de Turing não determinísitica,

diferente da máquina de Turing determinística, modela um computador que, pelo menos

por enquanto, não sabemos como construir fisicamente. A classe co-NP de problemas de

decisão é a que possui certificado polinomial para a respostanão.

A classeNP-completo é o subconjunto dos problemas de decisão da classeNP,

15

de tal modo, que todo problema de decisão emNP se reduz polinomialmente a ele. Em

maio de 2000, o Clay Mathematics Institute[9], com sede em Cambridge, Massachusetts,

propôs o que designou por problemas do milênio. Trata-se de um conjunto de sete

problemas, dos quais um deles é provar queNP= P. O instituto oferece um milhão de

dólares americanos pela resolução desse problema.

Pode-se dizer que os problemas da classeNP-completo são os mais difíceis da

classeNP. A razão é que se conseguíssemos encontrar uma maneira de resolver qualquer

problemaNP-completo em tempo polinomial, então poderíamos utilizar algoritmos para

resolver todos os problemasNPem tempo polinomial, provando queNP= P.

Vários dos problemas da classeNP-completo podem ser modelados usando gra-

fos. Muitos dos problemas sobre grafos tornaram-se célebres como desafios intelectuais

ou por suas importantes aplicações práticas, como no exemplo a seguir.

Seja um grafo cujos vértices representam projetos que podemser executados

em uma unidade de tempo. Todo projeto que utiliza recursos comuns a um outro projeto

são interligados por uma aresta. O conjunto independente máximo representa o conjunto

maximal de projetos, que podem ser executados em paralelo (simultaneamente) em um

único período de tempo. Dado um grafoG, o problema de determinar se há um conjunto

independente de tamanhok é um problema da classeNP-completo. Apesar disso, em

algumas classes de grafos é possível encontrar o conjunto independente máximo através

de algoritmos polinomiais, como por exemplos os grafos livre deK1,3 e os grafosp-

extensível. Neste último caso, temos um limite superior, que depende dep, para a

cardinalidade de um conjunto independente máximo.

O conceito de grafop−extensível foi introduzido por Plummer em 1980. Um

grafoG de ordem parn é p−extensível, ondep é um número inteiro entre 0 e(n/2)−1,

se o grafoG tem emparelhamento perfeito e se cada conjunto dep arestas independentes

estão contidas em algum emparelhamento perfeito.

Um emparelhamento no grafo G é um conjunto de arestas independentes,

tal que, quaisquer duas arestas nesse conjunto não possuem vértices em comum. Um

emparelhamento éperfeito se o conjunto de arestas incidem em todos os vértices do

grafoG.

O conjunto de todos os grafos que satisfazem uma dada propriedade constitui

uma família de grafos. Temos na literatura diversas famílias que vêm sendo, ao longo

do tempo, exaustivamente estudadas, como por exemplo: os grafos conexos, planares,

árvores, dentre outros. Nesta dissertação, estudaremos a família dos grafosp-extensíveis.

Normalmente, a definição de uma família consiste em mencionar a propriedade

satisfeita pelos grafos que a constituem, exatamente como fizemos no exemplo acima.

Em vários casos, essa propriedade pode ser acrescida de novas condições, originando

propriedades mais específicas, que definem subfamílias.

16

Quando uma nova família de grafos é definida, um importante problema compu-

tacional a ser resolvido é o do reconhecimento, que consisteem obter um algoritmo para

verificar se um grafo qualquer pertence ou não à família em questão. Em alguns casos,

verificar diretamente se o grafo dado satisfaz ou não à propriedade, conduz a algoritmos

não polinomial (ineficientes).

Um dos objetivos desta dissertação é apresentar os resultados sobre grafosp-

extensíveis, apresentando um texto de forma clara e simples, melhorando algumas provas

e classificando algumas subfamílias de grafosp-extensíveis. Outro objetivo é estudar um

algoritmo que encontra um emparelhamento máximo nos grafosgerais, para ser usado nos

algoritmos de grafosp-extensíveis. E por fim, será apresentado o algoritmo polinomial 1-

extensível. Veremos que o reconhecimento de grafosp-extensíveis é um problema co-NP.

Esta dissertação foi organizada em quatro capítulos. No capítulo 1 mostraremos

algumas definições, notações básicas e alguns resultados sobre grafos.

No capítulo 2, abordaremos os principais conceitos e teoremas sobre empare-

lhamento máximo em grafos. Também será estudado o algoritmode emparelhamento

máximo de Kameda e Munro, iremos demonstrar a correção e a complexidade dele.

No capítulo 3, revisaremos os principais conceitos e teoremas sobre grafosp-

extensíveis. Os grafosp-extensíveis também serão estudados nas principais famílias de

grafos, tais como: grafos bipartido, grafos fator-crítico, grafos planares, grafos livre de

K1,3, árvores e os grafos com grau mínimo.

No capítulo 4, estudaremos os algoritmos sobre grafos extensíveis. O primeiro

algoritmo determina se um grafo geral é ou não 1-extensível.Também estudaremos

a demonstração e a complexidade desse algoritmo. Neste capítulo, mostraremos outro

algoritmo para grafos 1-extensíveis. Mostraremos que o problemap-extensível éco-NP.

Finalmente, apresentaremos as conclusões deste trabalho.

CAPÍTULO 1Preliminares

Este capítulo antecede os assuntos principais deste trabalho e serão introduzidas

as definições, notações básicas e alguns resultados de grafos utilizados nesta dissertação.

Para este capítulo, usamos as seguintes referências: Diestel [3], Scheinerman[29] e West

[30].

Um grafo G = (V,E) é um par de conjuntos, ondeV é um conjunto não vazio

e finito cujos elementos são chamados devértices e E é um conjunto de pares não

ordenados de vértices que são chamados dearestas. Dada uma arestae = vw∈ E ou

e= (v,w) ∈ E, os vérticesv e w são denominadosextremidadesda arestae, e dizemos

quee é incidentenos vérticesv e w. Comumente, iremos denotarV(G) como o conjunto

de vértices de um grafoG eE(G) como o conjunto de arestas de um grafoG.

Neste trabalho, todos os grafos considerados serão simples. Um grafo é chamado

desimplesquando ele não possui arestas múltiplas e nem laços.Arestas múltiplas são

arestas que têm as mesmas extremidades. Umlaço é uma aresta da formaxx, ou seja,

cujas extremidades são iguais.

SejaG = (V,E) um grafo qualquer. A cardinalidade de vértices deG é chamado

deordem do grafo e ela é denotada por|V|. A cardinalidade de arestas deG é denotada

por |E|. Usaremos sempre as convençõesn = |V| em= |E|.Podemos visualizar um grafo através de umarepresentação geométricade um

ponto, para cada vértice, sobre uma superfície e para cada arestavw uma reta (ou curva)

ligandov a w. Se dois vértices são conectados por uma aresta, então eles são chamados

deadjacentes. O exemplo abaixo mostra uma representação geométrica de umgrafo.

•a

•b •c

•d

•e

Figura 1.1: Grafo simples.

18

Um grafo éplanar se existir uma representação geométrica do grafo no plano

sem cruzamentos de arestas.

Osvizinhos, ou avizinhança, de um vérticex é o conjunto de todos os vértices

adjacentes ax. O conjunto de vizinhos de um vérticex é denotado porNG(x) ou

simplesmenteN(x). Por exemplo, no grafo da figura1.1temosN(b) = {a,c,d}.O grau de um vérticex de um grafo é o número de arestas que incidem emx,

denotado pordG(x) ou simplesmented(x). O grau mínimo de um grafo é denotado por

δ(G) e ograu máximo por ∆(G). Na figura1.1, temosd(b) = 3, δ(G) = 2 e∆(G) = 3.

A proposição abaixo mostra uma relação direta entre os grausdos vértices e a quantia de

arestas de um grafo.

Proposição 1.1(West[30]) A soma dos graus de todos os vértices de um grafo é igual a

duas vezes o número de arestas.

Prova. Uma aresta com extremidadesx e y contribui com uma unidade parad(x) e outra

parad(y). Portanto, cada aresta contribui exatamente duas unidadespara a soma dos

graus. �

Vamos nos inteirar de alguns tipos especiais de grafos. Uns desses tipos são

os grafos regulares. Um grafoG = (V,E) é regular se todos os vértices do grafo têm

o mesmo grau, ou seja, quandoδ(G) = ∆(G). Um grafo é chamado dek-regular se

δ(G) = ∆(G) = k. Alguns grafos recebem denominação especial de acordo com ovalor

dek, como por exemplo: parak = 3, temos um grafocúbicoe parak = 2, temos umciclo.

O exemplo abaixo mostra um ciclo.

•a •b

•c

•d

Figura 1.2: 2−regular.

Outro tipo especial de grafo são os grafos completos. Um grafo G = (V,E) é

completo, se todos os pares de vértices distintos são adjacentes. Um grafo completo com

n vértices é denotado porKn. Os grafos completos são muito importantes, pois vários

resultados sobre grafos podem ser aplicados a eles.

•a

•b •c

Figura 1.3: K3.

19

Um tipo especial de grafos são os que não tem ciclos ímpares, chamados de

grafos bipartidos. Um grafoG = (V,E) é bipartido , se existe uma partição do conjunto

de todos os vértices em dois subconjuntosX e Y, tal que nenhuma aresta do grafo

tenha ambas as extremidades emX ou ambas as extremidades emY. Outra característica

importante dos grafos bipartidos é o fato de que esses grafospodem ser coloridos com

apenas duas cores, ou seja, um cor para cada partição de vértice.

Um grafo bipartido é chamado decompletoquando todos os vértices da partição

X estão ligado a todos os vértices da partiçãoY. Ele é denotado porKs,t , ondes= |X| et = |Y|. A figura1.4exemplifica grafos bipartidos.

•a •b

•c

•d

(a) GrafoK2,2

•a •b •c

•d

•e

•f

(b) Grafo bipartido

•a •b •c

•d

•e

•f

(c) CompletoK3,3

Figura 1.4: Grafos bipartidos.

Proposição 1.2Seja G= (V,E) um grafo bipartido. A soma dos graus dos vértices de

uma partição é igual ao número de arestas de G.

Prova. SejaG um grafo com a bipartiçãoX eY. Pela definição de grafo bipartido, temos

que toda aresta que incide na partiçãoX também incide na partiçãoY. Então, cada

aresta contribui exatamente com uma unidade para a soma dos graus dos vértices de uma

partição. Portanto,∑v∈X d(v) = ∑v∈Y d(v) = m. �

Um grafo H é um subgrafo do grafoG, desde que os vértices deH estejam

contidos nos vértices deG e as arestas deH estejam contidas nas arestas deG. Um

subgrafo é obtido através da remoção de vértices ou de arestas. Temos um tipo especial

quando removemos somente vértices ou somente arestas. No primeiro caso temos um

subgrafo induzido e no segundo caso temos um subgrafo gerador, como mostrar as

definições e os exemplos abaixo.

Um grafoH é umsubgrafo induzidodo grafoG se, e somente se,V(H)⊆V(G)

eE(H) = {xy∈E(G) | x∈V(H) ey∈V(H)}, ou seja, as únicas remoções permitidas

de G para obterH são as remoções de vértices e suas arestas incidentes. Denotaremos

G[V1] o subgrafo induzido pelo subconjunto de vérticesV1. Para qualquer subconjuntoS

deV(G), denotamos porG−So subgrafo induzidoG[V(G)−S]. Sev é um vértice deG,

entãoG− v é o subgrafo induzido deG, obtido da remoção do vérticev. Os grafos das

figuras1.5(b)e1.5(c)são subgrafos induzidos do grafo da figura1.5(a).

20

•a

•b •c

•d

•e

(a) GrafoG

•a

•b •c

(b) GrafoH

•b •c

•d

•e

(c) GrafoI

Figura 1.5: Subgrafos induzidos.

Um grafoH é umsubgrafo gerador do grafoG se, e somente se,H for um

subgrafo deG com os vértices deH sendo todos os vértices deG, ou seja,H e G têm os

mesmos vértices e as únicas remoções permitidas deG para obterH são as remoções de

arestas. Seeé uma aresta deG, entãoG−eé o subgrafo gerador deG, obtido da remoção

da arestae. Os grafos das figuras1.6(b) e 1.6(c) são subgrafos geradores do grafo da

figura1.6(a).

•a

•b •c

•d

•e

(a) G

•a

•b •c

•d

•e

(b) H

•a

•b •c

•d

•e

(c) I

Figura 1.6: Subgrafos geradores.

Um fator de um grafoG é um subgrafo gerador deG. Um k-fator é um subgrafo

geradork-regular. Na figura1.6 os grafosH e I são subgrafos geradores deG, logo eles

sãofatoresdeG. De fato, o grafoI é 2−fator deG, pois ele é um subgrafo 2−regular.

Pela sua importância, em Teoria de Grafos, vamos destacar asseqüências de

vértices e arestas. Umcaminho entre dois vérticesx e y de um grafoG é uma seqüência

de vérticesP = (v1,v2,v3, . . . ,vk) onde,x = v1, y = vk, e vivi+1 pertence às arestas do

grafo, para todoi = 1, . . . ,k−1. Um caminho é denominadosimplesse os vértices que o

constituem são todos distintos. Um caminho simples dek vértices é denotado porPk, seu

comprimento é dek−1 arestas.

Existe um tipo especial de caminho de comprimento maior ou igual a 3, em que

o primeiro e o último vértices coincidem, esse caminho é denominado deciclo. Um ciclo

simplesé um ciclo onde todos os vértices que o constituem são distintos, à exceção do

primeiro e do último vértices que coincidem. Um ciclo simples dek vértices é denotado

21

porCk, seu comprimento é dek arestas. Uma propriedade importante dos grafos bipartidos

é que não existem ciclos ímpares.

Um caminho (ciclo)hamiltoniano é um caminho (ciclo) simples que contém

todos os vértices do grafo.

Um grafo éconexose para qualquer par de vértices(v,w), existe um caminho

simples com extremosv e w, caso contrário, o grafo édesconexo. Um subgrafo conexo

H de um grafoG é maximal, seH não pertence a nenhum subgrafo conexo deG. Um

componentede um grafo é um subgrafo conexo maximal. A partir da definiçãode grafo

conexo e componente, podemos afirmar que um grafo é conexo se,e somente se, tiver um

único componente. Se um grafo não tem arestas, então cada um de seus vértices constitui

um componente conexo.

SejamG um grafo conexo eB ⊆ V(G) um subconjunto dos vértices deG.

O conjuntoB é chamadoseparador do grafoG, desde queG−B tenha mais de um

componente.

A conectividadede G, κ(G), é o tamanho do menor conjunto separadorB.

Dizemos queG é k−conexo, seκ(G) ≥ k, ou seja, se|V(G)| > k e G−B for conexo

para todoB ⊆ V com |B| < k. Para todo grafoG, temos que 0< κ(G) ≤ n− 1. Um

grafo conexo é 1-conexo e vice-versa. Quando não temos um conjunto separador, então

κ(G) = n−1, esse é o caso dos grafos completos.

Proposição 1.3(West[30]) Se Kn é um grafo completo entãoκ(G) = n−1.

Prova. SejaKn um grafo completo, então temos que mostrar queκ(G) = n− 1. Para

isso, Kn não pode ter conjunto separador. SejaX ⊆ V um conjunto separador deKn.

Por definiçãoG−X, tem mais de um componente, consideramosx e y dois vértices

pertencentes a componentes distintos. Como o grafoKn é completo, existe uma aresta

entrex ey. Logo eles estão na mesma componente deG−X, uma contradição. �

Um emparelhamentono grafoG é um conjunto de arestas independentes, tal

que, quaisquer duas arestas nesse conjunto não possuem vértices em comum. Os vértices

incidentes nas arestas de um emparelhamento são chamados desaturadose os vértices

não incidentes são ditos de não saturados.

Um emparelhamentoM é chamadomaximal se não existir outro emparelha-

mentoM∗ que o contenha, ou seja, ele não é subconjunto próprio de outro emparelha-

mento do grafo.

O emparelhamento de maior cardinalidade do grafo é chamado de emparelha-

mentomáximo. A cardinalidade de um emparelhamento máximo é denotado porα′(G).

Todo emparelhamento máximo é maximal, mas nem todo emparelhamento maximal é

máximo, como mostra o exemplo da figura1.7.

22

As arestas, que estão em negrito nos grafos da figura1.7, mostram dois empa-

relhamentos. O emparelhamento na figura1.7(a)é maximal, mas não é máximo. O em-

parelhamento da figura1.7(b)é maximal e máximo, também podemos observar que ele

satura todos os vértices do grafo e com as arestas desse emparelhamento máximo temos

um sugbrafo gerador 1-fator.

•1 •2

•3 • 4

•5

•6

(a) Maximal.

•1 •2

•3 • 4

•5

•6

(b) Máximo e Perfeito.

Figura 1.7: Emparelhamentos.

Um tipo particular de emparelhamento máximo deve ser destacado: o empare-

lhamento perfeito. Um emparelhamento éperfeito quando satura todos os vértices de um

grafo. É evidente que todo emparelhamento perfeito é máximoe maximal. Um empare-

lhamento perfeito só existe num grafo de ordem par e é um emparelhamento contendo

n/2 arestas.

As arestas que pertencem a algum emparelhamento perfeito são chamadas de

arestas permitidase as arestas que não pertençam a nenhum emparelhamento perfeito

são chamadas dearestas proibidas. Um grafoG de ordem par éelementarse as arestas

permitidas formam um subgrafo conexo.

Seja um grafoG. Dizemos que um subconjunto de vérticesS⊆ V(G) é um

conjunto independente, desde que não haja dois vértices adjacentes emS. Em outras

palavras, um subconjuntoS⊆V(G) é independente se, e somente se, o subgrafo induzido

G[S] não tem arestas.

Um conjunto independente maximalé aquele que não faz parte de um outro

conjunto independente maior. O maior conjunto independente do grafo é chamado de

conjunto independente máximo. Onúmero de independênciade um grafo é o tamanho

do maior conjunto independente, denotado porα(G).

O grafo da figura1.8 tem vários conjuntos independentes, tais como:{a, f},{b,e}, {c,h}, {d,g}, {a,d,e,h} e{b,c, f ,g}. No grafoG, temos conjuntos independentes

maximal de tamanho igual a dois, masα(G) = 4.

Os conceitos de emparelhamento máximo e conjunto independente estão relaci-

onados com a quantidade de arestas e vértices, respectivamente, onde o emparelhamento

máximo é o maior conjunto de arestas independentes e o conjunto independente é o maior

conjunto de vértices independentes. Para encontrar o emparelhamento máximo de um

23

•a •b

•c •d

•e

•f

•g

•h

Figura 1.8: Cubo.

grafo temos algoritmos polinomiais, mas não temos nenhum algoritmo polinomial para

encontrar o conjunto independente máximo, ou seja, encontrar um conjunto independente

de tamanhok é um problema que está na classeNP. Veja em[11]. Apenas para algumas

classes de grafos, é possível encontrar o número de independência em tempo polino-

mial, em outras classes temos limites superiores ou inferiores para esse número, como

por exemplo, a classe de grafosp-extensíveis, que tem um limite deα(G) = n/2− p.

Seja G um grafo conexo de ordem par. Um grafoG é p-extensível , onde

p é um número inteiro entre 0 e(n/2)− 1, seG tem emparelhamento perfeito e se

quaisquer conjunto dep arestas independentes (não adjacentes) estende-se para um

emparelhamento perfeito deG, isto é, quaisquerp arestas independentes estão contidas

em algum emparelhamento perfeito deG.

Neste trabalho, vamos estudar a relação dos grafosp-extensíveis ek-fator-crítico.

Essa relação é muito importante, porque temos um limite superior para o número de

independência dos grafosp-extensíveis que não são bipartidos. Um grafo de ordemn

é k−fator-crítico , ondek é um inteiro 0≤ k ≤ n e n+ k é par, seG−X admite um

emparelhamento perfeito para todo conjuntoX de k vértices. Um grafo é chamado de

bicrítico se ele é 2-fator-crítico.

Os grafosk-fator-crítico não são(k−1)-fator-crítico, pois temos pela definição

quek+ n tem que ser par, ou seja, eles são de mesma paridade. Mas quando fazemos

k− 1, temos quek fica com paridade diferente den, contradizendo assim a definição.

Porém, temos o resultado abaixo para(k−2)-fator-crítico.

Proposição 1.4(Favaron[5]) Se G é um grafo k-fator-crítico de ordem n≥ k+2, então

G é(k−2)-fator-crítico.

Um grafo que ék−fator-crítico não é necessariamente(k+2)-fator-crítico, como

mostra o exemplo da figura1.10 que é um grafo 3-fator-crítico, mas não é 5-fator-

24

•a

•b •c

•d

•e

(a) 1−fator-crítico.

•a

•b •c

•d

•e

•f

(b) 2−fator-crítico.

Figura 1.9: Fator-crítico.

crítico, pois se os vértices(a,c,d, f ,g) forem retirados, o grafo fica desconexo e não

tem emparelhamento.

•a

•b •c

•d

•e

•f

•g

Figura 1.10: 3−fator-crítico.

CAPÍTULO 2Emparelhamento

Neste capítulo serão abordados os principais conceitos e teoremas sobre empa-

relhamento máximo em grafos. Também será estudado um algoritmo de emparelhamento

máximo, a demonstração da correção e a complexidade desse algoritmo.

Uma das possíveis aplicações de emparelhamento máximo em grafo é mostrado

no seguinte exemplo: suponha que há quatro candidatosc1, c2, c3 e c4 para as três vagas

de uma empresa que serão chamadas dev1, v2 e v3 e que nem todos os candidatos tenha

competência para todas as vagas. O candidatoc1 pode concorrer para as vagasv2 e v3, c2

para as vagasv1 e v2, c3 para as vagasv1 e v3 e, finalmente,c4 para a vagav3. Isso pode

ser representado por um grafo bipartido, mostrado na figura2.1, onde cada aresta liga um

candidato a uma vaga que ele poderia eventualmente ocupar.

◦c1

• v1

◦c2

• v2

◦c3

• v3

◦c4

Figura 2.1: Grafo bipartido.

Será possível preencher todas as vagas disponíveis pela empresa? Uma combi-

nação possível seria a de escolher o candidatoc1 para a vagav2, o candidatoc2 para a

vagav1 e finalmente o candidatoc3 para a vagav3. Também é possível trocar o candidato

c3 pelo candidatoc4, obtendo, assim, outra combinação. Encontrar um emparelhamento

máximo no grafo é um dos problemas estudados em teoria de grafos e será estudado com

mais detalhe na próxima seção.

2.1 Emparelhamento máximo 26

2.1 Emparelhamento máximo

Nesta seção estudaremos as definições e resultados sobre emparelhamento má-

ximo que serão necessários para o entendimento do algoritmopolinomial que encontra o

emparelhamento máximo. Uma boa referência sobre o assunto éo livro do Plummer[15].

SejaM um emparelhamento qualquer. Umcaminho M-alternante é um ca-

minho simples que alterna arestas emM e arestas que não estão emM. Um caminho

M-aumentanteé um caminhoM-alternante, onde os extremos não são saturados pelas

arestas deM. Pela definição podemos observar que um caminhoM-aumentante é neces-

sariamente de comprimento ímpar. Umciclo M-alternante é um ciclo formado por um

caminhoM-alternante de comprimento par.

Um broto é um ciclo ímpar que é um caminhoM-alternante. O único vértice do

broto que não é saturado por arestas deM que estão no broto é chamado debasedo broto.

•1 •2

•3

Figura 2.2: Broto

Na figura2.2, temos a aresta 12, que pertence ao emparelhamento e o vértice

3 é a base do broto, pois o vértice não está saturado por arestado emparelhamento que

pertence ao broto.

Sejam A e B dois conjuntos, adiferença simétrica entre esses conjuntos é

denotado porA⊕B = (A−B)∪ (B−A), ou seja, a diferença simétrica entreA e B é

o conjunto cujos elementos são os elementos deA, que não estão emB, junto com os

elementos deB que não estão emA.

Vamos ver os resultados envolvendo a diferença simétrica entre dois emparelha-

mentos e a diferença simétrica entre um caminhoM-aumentante e um emparelhamento

qualquer. Esses resultados serão usados na demonstração doteorema2.4 de Berge e nos

algoritmos sobre emparelhamento máximo e grafos extensíveis.

Lema 2.1 (West [30]) Sejam M1 e M2 dois emparelhamentos de um grafo G, então

o subgrafo gerador G∗(V,M1⊕M2) é composto de vértices isolados, de caminhos

alternantes e de ciclos alternantes.

Prova. SejamM1 e M2 dois emparelhamentos e seja o subgrafoG∗(V,M1⊕M2). Como

M1 eM2 são emparelhamentos, todos os vértices do subgrafo tem no máximo uma aresta

de cada emparelhamento, assim o subgrafo tem no máximo duas arestas para cada vértice,

ou seja,∆(G∗)≤ 2. Logo, os componentes deG∗ são os seguintes:


• Vértices isolados que não têm aresta.

• Caminho alternante, ou seja, as extremidades do caminho têm grau um e os outros

vértices no centro do caminho têm grau dois. Portanto, o caminho alternante pode

começar com uma aresta deM1, ou M2, e termina com uma aresta deM2, ou M1,

respectivamente, ou ainda, esse caminho alternante pode começar e terminar com

arestas deM1, ouM2, respectivamente.

• Ciclo alternante tem todos os vértices de grau dois e, portanto, a mesma quantidade

de arestas deM1 e deM2.

�

O lema abaixo mostra a principal idéia do teorema de Berge, queé procurar os

caminhosM-aumentantes, para aumentar o emparelhamento em uma aresta.

Lema 2.2 (West[30]) Sejam M um emparelhamento e P um caminho M-aumentante,

então P⊕M é um emparelhamento de cardinalidade|M|+ 1. Observamos que P⊕M

satura todos os vértices saturados por M.

Prova. Queremos mostrar queP⊕M é um emparelhamento de cardinalidade|M|+ 1.

Pela definição, temos que um caminhoM-aumentante é um caminhoM-alternante, onde

as extremidades não são saturadas porM. O caminhoP começa e termina com uma

aresta que não está emM e alterna com arestas que estão emM, assim temos uma

cardinalidade de 2k+1 arestas para o caminhoP, ondek é o número de arestas emP que

estão emM. Portanto,|P⊕M|= |(P∪M)− (P∩M)|= |P|+ |M|− |P∩M|− |P∩M|=|P|+ |M| − 2|P∩M| = 2k + 1+ |M| − 2k = |M|+ 1. Falta verificar queP⊕M é um

emparelhamento. Sabemos que as únicas arestas deM que incidem emP são as arestas

de M que estão emP, e essas arestas não pertencem aP⊕M. Portanto,P⊕M é um

emparelhamento. �

•2

•3

•4

•5

•6

•7

Figura 2.3: Emparelhamento M

A figura 2.3 mostra um emparelhamentoM, a figura2.4 mostra um caminhoP

que éM-aumentante. Por fim a figura2.5 mostra a diferença simétrica entre o empare-

lhamentoM e o caminhoP. O emparelhamentoP⊕M tem uma aresta a mais do que o

emparelhamentoM.


◦1

•2

•3

•4

•5

•6

•7

◦8

Figura 2.4: Caminho P

•1

•2

•3

•4

•5

•6

•7

•8

Figura 2.5: Emparelhamento P⊕M

Podemos observar que se um caminhoP for um caminhoM-alternante e ambas

as extremidades são saturadas por arestas deP, entãoP⊕M é um emparelhamento com

menos arestas. De fato,P é um caminho simples de 2k vértices, ondek é a quantidade de

arestas que está emM, pois todos os vértices do caminhoP estão saturados porM. Por

definição de caminho simples a quantidade de arestas do caminho P é 2k−1. Portanto,

|P⊕M|= |P|+ |M|−2|P∩M|= 2k−1+ |M|−2k = |M|−1. Logo,|P⊕M|= |M|−1.

Outro caso é quando um caminhoP for um caminhoM-alternante com uma

aresta da extremidade emM e a outra extremidade não saturada, entãoP⊕M é um

emparelhamento de mesma cardinalidade. De fato, um caminhoP tem a mesma quan-

tidade de arestas deM e arestas que não estão emM, logo |P|= 2k. Portanto,|P⊕M|=|P|+ |M|−2|P∩M|= 2k+ |M|−2k = |M|. Logo,|P⊕M|= |M|.

Quando um caminhoP for um caminhoM-alternante e uma ou ambas as

extremidades forem saturadas por arestas que não estão emP, entãoP⊕M não é um

emparelhamento, pois um ou ambos os vértices das extremidades do caminhoP, serão

saturados por arestas deM eP ao mesmo tempo, um absurdo.

O lema2.3 é um resultado que encontramos muito interessante e será usado no

algoritmo 1-extensível.

Lema 2.3 Sejam M um emparelhamento e C um ciclo M-alternante, então C⊕M é um

emparelhamento de cardinalidade|M|. Observamos que C⊕M satura os mesmos vértices

que M.

Prova. Queremos mostrar queC⊕M é um emparelhamento de cardinalidade|M|. Pela

definição, temos que um cicloM-alternante tem cardinalidade|C|= 2k, ondek é o número

de arestas no ciclo que estão emM. Portanto, podemos observar que o cicloM-alternante

é de comprimento par e|C⊕M| = |C|+ |M| − 2|C∩M| = 2k+ |M| − 2k = |M|. Logo,

|C⊕M|= |M|. �

2.2 Algoritmo de Emparelhamento Máximo 29

Em 1957, Berge obteve um resultado importante que caracteriza quando um

emparelhamento em um grafo é máximo.

Teorema 2.4 (Berge[2]) Um emparelhamento M tem cardinalidade máxima em G se, e

somente se, G não possui caminho M-aumentante.

Prova. Suponha queM é um emparelhamento de cardinalidade máxima eP um caminho

M-aumentante. Esse caminho é de comprimento ímpar e com as extremidades não

saturadas porM. Pelo lema2.2, temos queM⊕P é um emparelhamento de cardinalidade

|M|+1, uma contradição.

Suponha queG não tenha caminhoM-aumentante e queM não seja um em-

parelhamento máximo emG. Seja M∗ um emparelhamento de cardinalidade maior

que a cardinalidade deM. Pelo lema2.1, temos queM⊕M∗ é composto de caminhos

M-alternantes, vértices isolados e de ciclos. Todos os ciclos M-alternantes são de com-

primento par e contém o mesmo número de arestas deM e deM∗. Como pela hipótese

M∗ é um emparelhamento maior, então pelo menos um dos caminhosM-alternantes deve

conter mais arestas deM∗, ou seja, será um caminhoM-aumentante, uma contradição.�

O teorema de Berge conduz ao algoritmo MétodoBerge2.1, utilizado na maioria

dos algoritmos, para construir um emparelhamento maximal num grafo.

Algoritmo 2.1: MétodoBerge

Entrada: GrafoG qualquer

Saída: Um emparelhamento máximoM

início1

sejaM um emparelhamento emG2

enquantoexistir um caminho M-aumentante P em relação a3

M faça

construa um novo emparelhamentoM′ = M⊕P4

M = M′5

fim6

fim7

2.2 Algoritmo de Emparelhamento Máximo

Em 1965, Edmonds apresentou em [15] um algoritmo de complexidadeO(n4)

que encontra o emparelhamento máximo de um grafo em tempo polinomial. O algoritmo

utiliza a estratégia do teorema de Berge que é encontrar os caminhos M-aumentantes


para que o emparelhamento possa ser aumentado. Os caminhosM-aumentantes são

encontrados usando a idéia de florestas alternantes, árvores alternantes e contração

de brotos. No mesmo ano, Witzgall e Zahn apresentaram em[31] um algoritmo de

complexidadeO(n3).

A partir desse algoritmo muitos pesquisadores estudaram esse problema e,

progressivamente, algoritmos mais eficientes foram desenvolvidos.

Algoritmo 2.2: EmparelhamentoMáximo


Saída: Um emparelhamento máximoM∗

início1

M← /02

para cadavértice r∈V faça3

sevértice r não é saturadoentão4

S1← /0; S2← /05

Lista_Vértices← /06

secaminho-aumentante()então7

M← aumentar-emparelhamento()8

fim9

fim10

fim11

M∗←M12

fim13

Em 1974, Kameda e Munro apresentaram em[10] um algoritmo que encontra um

emparelhamento máximo em um grafo de complexidadeO(nm). Eles usam a estratégia

do teorema2.4 de Berge para encontrar o emparelhamento máximo. O melhor tempo

conhecido dos autores até agora é deO(m√

n) encontrado por Micali e Vazirani em[20]

no ano de 1980.

Neste trabalho, vamos utilizar o algoritmo de Kameda e Munro. Escolhemos esse

algoritmo por sua implementação simples e sua boa complexidade. O algoritmo original

de Kameda e Munro usa seqüências que não estão estruturadas,dificultando a análise do

mesmo. Estruturamos o algoritmo encontrado no artigo [10] dividindo o mesmo em vários

algoritmos. Outro objetivo da estruturação é facilitar a implementação do algoritmo.

De acordo com a estratégia de Berge, o algoritmoEmparelhamentoMáximo2.2

tem que procurar por caminhosM-aumentantes até que eles não existam mais. A cada

caminhoM-aumentante encontrado, o emparelhamento será aumentado em uma aresta

pela diferença simétrica entre o emparelhamento e o caminhoM-aumentante.


O algoritmo utiliza duas pilhas,S1 e S2, e uma lista de vértices, essa lista

é denominado porLista_Vértices, onde cada vérticev da Lista_Vértices contém os

parâmetros(v.NUM,v.po,v.pe). Esse parâmetros formam o rótulo do vértice. Através dos

rótulos é criado um novo subgrafo que forma o caminhoM-aumentante. Esse processo é

definido como rotulação dos vértices. A seguir temos a descrição de como esses vértices

são rotulados.

A Lista_Vértices será utilizada no processo de rotulação e cada vérticev é

composto pelos parâmetrosv.NUM, v.po e v.pe, onde v é o vértice que está sendo

analisado. O númerov.NUM recebe a ordem de seqüência do vérticev no subgrafo. Um

vérticev é par quandov.NUM é um número par e o vérticev é ímpar quando ov.NUM é

um número ímpar. O númerov.po recebe o número da seqüência anterior do caminhoM-

alternante, que junto com ov.NUM forma uma aresta do caminhoM-alternante que não

pertence ao emparelhamento e que está a uma distância ímpar da raiz até o vérticev ou

retorna−1, quando a aresta ainda não foi analisada. O númerov.pe recebe o número da

seqüência anterior do caminhoM-alternante que, junto com ov.NUM forma uma aresta

do caminhoM-alternante, que pertence ao emparelhamento e está a uma distância par da

raiz até o vérticev ou retorna−1, quando a aresta ainda não foi analisada.

Se o grafo não for bipartido, então o algoritmo pode encontrar na rotulação um

broto. Umbroto é um ciclo ímpar que aparece quando uma aresta não examinada conecta

dois vértices pares, ambos no subgrafo rotulado, formando um caminhoM-alternante

fechado de comprimento ímpar. A raiz do broto é o vertice não saturado pelas arestas do

emparelhamento que pertence ao ciclo. A identificação de um broto no subgrafo é feita

pelos rótulos dos seus vértices.

As pilhas são definidas porS1 e S2. A pilha S1 guarda os vértices do caminho

M-alternante. A pilhaS2 guarda os vértices dos brotos que ainda não foram analisados.

Depois de iniciar as pilhas e a lista, escolhe-se um vértice que não esteja saturado

e, a partir dele, procura-se um caminhoM-aumentante, usando a funçãocaminho-

aumentante(). Se o caminhoM-aumentante for encontrado, então a funçãoaumentar-

emparelhamento()será usada para aumentar uma aresta ao emparelhamentoM.

Para encontrar os caminhosM-aumentantes será usada a funçãocaminho-

aumentante(). A função usa a idéia de rotulação dos vértices. Os vértices serão rotulados,

como um novo subgrafo, para isso serão usadas as duas pilhas,S1 eS2, e a Lista_Vértices

do algoritmo2.2.


Funçãocaminho-aumentante

Entrada: Lista_Vértices,S1, S2, r, M

Saída: Verdadeiro, Falso

início1

/* Rotulação da raiz do subgrafo */

i← 0; S1← i; u← r; r.NUM← i; r.po←−1 ; r.pe← i2

enquantoVerdadeirofaça3

seexiste(u,v) /∈M e a aresta não foi examinadaentão4

sev 6= r e v não é saturadoentão5

/* Encontro de um caminho M-aumentante */

retorna Verdadeiro6

fim7

sev não é rotuladoentão8

/* Processo de rotulação */

caminho-alternante()9

senão10

sev.pe 6=−1 então11

/* Encontro de um broto */

encontrar-broto()12

severificar-pilhas()então13

/* Não existe caminho M-aumentante */

retorna Falso14

fim15

fim16

fim17

senão18

seatualizar-pilhas()então19

/* Não existe caminho M-aumentante */

retorna Falso20

fim21

fim22

fim23

fim24

O processo de rotulação cria um caminhoM-alternante, a partir de um vértice

não saturado chamado deraiz, até encontrar um outro vértice não saturado para ter um

caminhoM-aumentante. Os rótulos são criados de tal maneira que seja possível, a partir

de um vértice, retornar à raiz do subgrafo. Mesmo se o caminhoM-alternante encontrar


um broto, o processo de rotulação garante os rótulos necessários para recriar o caminho

de volta.

Podemos observar que se os rótulosv.po e v.pe são diferentes de−1, então o

vérticev.NUM faz parte de um broto, ou seja, a aresta(v.NUM,v.po) não pertence aM e

a aresta(v.NUM,v.pe) pertence aM. Com esses rótulos, o caminho tem a possibilidade

de, entrando pela raiz, seguir qualquer direção do broto. Essa direção vai depender de qual

vértice do broto o caminho irá seguir, como por exemplo, os caminhos da figura abaixo.

•2

•0 • 1

•3

• 4

(a) GrafoG

•2 • 4

•0 • 1

•3

(b) GrafoH

Figura 2.6: Caminhos nos brotos.

O primeiro rótulo é feito pela funçãocaminho-aumentante()na raiz do subgrafo

e a partir da raiz, o subgrafo é rotulado pela funçãocaminho-alternante(). Temos

na figura2.7 um exemplo desse processo de rotulação. Para as figuras seguintes que

representam o caminhoM-aumentante vamos utilizar o seguinte esquema: as arestas

contínuas são arestas já examinadas; as arestas pontilhadas são arestas que não foram

examinadas; as arestas finas são arestas que não pertence ao emparelhamentoM; as arestas

em negrito são arestas que pertence aM.

•6[−1,5]

•7[6,−1]

•

•5[4,−1] •8[−1,7] •

•4[−1,3] •

•3[2,−1] •

•2[−1,1]

•1[0,−1]

•0[−1,0]

(a) CaminhoM-alternante

876543210

(b) S1 (c) S2

Figura 2.7: Processo de rotulação.


Agora, vamos entender como é feito a rotulação dos vértices da figura2.7. A raiz

do subgrafo é o primeiro vértice que é rotulado, ele recebe o rótulo (0,−1,0). Depois o

algoritmo verifica se existe alguma aresta que incide na raizque ainda não foi examinada.

No exemplo temos a arestauv, ondeu é a raiz do subgrafo ev é o extremo da aresta

que não foi examinada. Agora o algoritmo testa se o vérticev está saturado, caso ele não

esteja saturado, então foi encontrado um caminhoM-aumentante. Como o vérticev já

está saturado então é chamado a funçãocaminho-alternante()para rotular o vérticev da

seguinte forma(1,0,−1) e o vérticem(v) como(2,−1,1). O vérticem(v) é o vértice do

outro extremo da aresta que pertence aM e que incide emv. Esses rótulos mostra que no

vérticem(v) temos a aresta 21, que pertence ao emparelhamento e no vértice v temos a

aresta 10, que não pertence ao emparelhamento.

Depois desse processo o algoritmo move o vérticem(v) para o vérticeu e faz

novamente o teste para saber se existe alguma aresta que ainda não foi examinada a partir

do vérticeu que agora é o vértice 2. Como podemos observar na figura temos duas arestas

que ainda não foram examinadas. O algoritmo escolhe uma das arestas e verifica que o

vértice é saturado, então é chamado funçãocaminho-alternante()para rotular os vértices

v em(v). O vérticev recebe o rótulo(3,2,−1) e o vérticem(v) recebe o rótulo(4,−1,3).

Esse processo é repetido até que o vértice que recebe o rótulo(8,−1,7) seja rotulado pelo

algoritmo.

O processo de rotulação continua criando o caminhoM-alternante, verificando

se alguma aresta ainda não foi examinada pela função, ou seja, uma aresta cujo vértice da

extremidade já foi ou não rotulado. Temos as seguintes condições para analisar:

• se uma aresta conecta um vértice par com um vértice que não foirotulado e não

está saturado pelo emparelhamento, então a função termina efoi encontrado um

caminhoM-aumentante;

• se uma aresta conecta um vértice par com um vértice que não foirotulado, mas está

saturado pelo emparelhamento, então foi encontrado um caminhoM-alternante e o

procedimentocaminho-alternante()será executado para continuar com a rotulação

dos vértices do caminhoM-alternante;

• se uma aresta conecta dois vértices pares rotulados comv.pe diferente de−1, então

foi encontrado um broto. O procedimentoencontrar-broto()será executado para

rotular os vértices do broto e depois a funçãoverificar-pilhas()será executada para

escolher o próximo valor para o vérticeu;

• se uma aresta conecta um vértice par a um vértice ímpar foi encontrado um ciclo

par e a função não precisa fazer nada.

Se não existir uma arestauv para ser examinada, então é executado a função

atualizar-pilha(). Essa função apaga os vérticesu e m(u) do topo da pilhaS1 e depois o


topo da pilhaS1 será escolhido como o novo vérticeu, e a partir deu a função continuará a

procurar o caminhoM-aumentante. Se as pilhas ficarem vazias, então a funçãocaminho-

aumentante()termina e nenhum caminhoM-aumentante foi encontrado.

O procedimentocaminho-alternante()é executado toda vez que um vérticev

saturado e que não foi rotulado é encontrado pela funçãocaminho-aumentante(). O

procedimento tem a função de aumentar o caminhoM-alternante através da rotulação

dos vértices da aresta que pertence ao emparelhamento. Como ovérticev é um vértice

saturado, então existe uma única arestam(v) pertencente ao emparelhamentoM.

O procedimento utiliza o vérticev e o vérticem(v) para fazer a rotulação do

caminhoM-alternante. O procedimento cria os rótulos do vérticev da seguinte maneira:

o v.NUM recebe o próximo vértice do subgrafo; ov.po recebe o vértice anterior, pois a

aresta(v.NUM,v.po) não pertence aM e o vérticev está a uma distância ímpar da raiz e

o v.pe recebe−1.

Depois os rótulos do vérticem(v) são criados da seguinte maneira: om(v).NUM

recebe o próximo vértice do subgrafo; om(v).pe recebe o vértice anterior, pois a aresta

(m(v).NUM,m(v).pe) pertence aM e o vérticem(v) está a uma distância par da raiz e o

m(v).po recebe−1.

Procedimentocaminho-alternante

Entrada: Lista_Vértices,S1, u, i

início1

/* Rótula o vértice v */

i← i +12

v.NUM← i; v.po← u.NUM; v.pe←−13

S1← i4

/* Rótula o vértice m(v) */

i← i +15

m(v).NUM← i; m(v).po←−1;6

m(v).pe← v.NUM

S1← i7

u←m(v)8

fim9

Quando a funçãocaminho-aumentante()encontra uma aresta que conecta dois

vértices pares rotulados comv.pe diferente de−1, foi encontrado um broto, ou seja, um

caminhoM-alternante fechado de comprimento ímpar.

A função não precisa tratar os caminhosM-alternantes fechados de comprimento

par, pois esses caminhos são ciclosM-alternantes, ou seja, alternam arestas que estão no

emparelhamento com arestas que não estão no emparelhamento.


Agora os caminhosM-alternantes fechados de comprimento ímpar tem um vér-

tice, denominado base do broto, com duas arestas que não pertençam ao emparelhamento,

ou seja, o processo de rotulação tem que indicar quais rótulos esses vértices têm que re-

ceber, para que seja possível criar um caminhoM-alternante. Os rótulos dos vértices dos

ciclosM-alternantes de comprimento ímpar, formam um caminho com duas direções pos-

síveis.

As funções e procedimentos do algoritmoEmparelhamentoMáximo2.2 reali-

zam operações com as pilhasS1 e S2, e essas funções e procedimentos utilizam algumas

funções para essas operações, que são as seguintes: A funçãoTOPO() retorna o topo de

uma pilha; A funçãoSegundoTOPO()retorna o primeiro elemento abaixo do topo da pi-

lha; A funçãoMOVE() move o topo de uma pilha para outra pilha; A funçãoREMOVE()

apaga o topo de uma pilha.

Quando um broto é encontrado, executa-se o procedimentoencontrar-broto().

Os vértices do broto são movidos da pilhaS1 para a pilhaS2 e seus rótulos são atualizados

de tal maneira, que todos os vértices tenham a identificação tanto da aresta que está em

M quanto da aresta que não está emM. A figura2.8 mostra um exemplo do processo de

rotulação do broto a partir da figura2.7.

A figura 2.8 mostra quando a funçãocaminho-aumentante()escolhe a aresta

que liga o vértice 8 ao vértice 4 e foi encontrado um broto, então a função executa o

procedimentoencontrar-broto()para que os vértices sejam rotulados. Os rótulos serão

dados da seguinte maneira: primeiro o vértice 8 recebe nopo o valor do vértice 4, depois

o vértice 7 recebe nope o valor do vértice 8. Esse procedimento será realizado até que

todos os vértices do broto sejam rotulados. O vértice 4 é o único que não recebe um rótulo

pois ele é a base do broto.

•6[7,5]

•7[6,8]

•

•5[4,6] •8[4,7] •

•4[−1,3] •

• •

•

•

•

(a) Broto

43210

(b) S1

5678

(c) S2

Figura 2.8: Rotulação do broto.


Logo depois é executada a funçãoverificar-pilhas(). Essa função verifica a

existência de vértice na pilhaS2, caso isso aconteça, o topo da pilhaS2 será colocado

no topo da pilhaS1 junto com uma marcação # e o topo deS1 passa ser o novo vérticeu.

Quando o procedimentoencontrar-broto(), achar um vértice na pilhaS1 com a

marcação #, então foi encontrado um sub-broto nesse caminho. O broto que está contido

em um outro broto é chamado porsub-broto. O procedimento apaga o vértice com a

marcação da pilhaS1 e o topoS1 passa ser a base do sub-broto.

Procedimentoencontrar-broto

Entrada: Lista_Vértices,S1, S2

início1

z← v; teste4← verdade2

enquantoteste4 faça3

x← z4

y.NUM← TOPO(S1)5

seSegundoTOPO(S1) 6= /0 então6

z.NUM← SegundoTOPO(S1)7

fim8

sey.NUM≤ v.NUM então9

teste4← f also10

senão11

sey.NUM não tem marcação# então12

/* Rotulação dos vértices do broto */

y.po← x.NUM; z.pe← y.NUM13

MOVE(S1,S2) /* move y.NUM de S1 para S2 */14

MOVE(S1,S2) /* move z.NUM de S1 para S2 */15

senão16

REMOVE(S1) /* apaga o valor y.NUM# de S1 */17

sez.NUM > v.NUM então18

/* Rotulação da base do sub-broto */

z.po← x.NUM∗ (y.NUM); z.NUM← z.pe19

senão20

teste4← f also21

fim22

fim23

fim24

fim25

fim26


Na seqüência, é verificado no subgrafo se a ordem do vérticez.NUM é maior do

que a ordem do vérticev.NUM, caso isso aconteça, foi encontrado a base do sub-broto

e o seu rótulo será atualizado parax.NUM∗ (y.NUM). Essa marcação indica qual aresta

o broto tem que seguir para criar o caminhoM-alternante, ondex.NUM é um vértice

do broto ey.NUM é o vértice de entrada do sub-broto. A figura2.9(d) mostra como é

encontrado e rotulado um broto e um sub-broto, seguindo as figuras2.7e2.8.

• • • 9[7,−1]

• • •10[−1,9]

• •11[10,−1]

• •12[2,11]

•

•

•

(a) Encontro do sub-broto

12111097#43210

(b)S1

78

(c)S2

• • • 9[7,10]

• • •10[11,9]

•4[9∗ (7),3] •11[10,12]

•3[2,4] •12[2,11]

•

•

•

(d) Rotulação do broto e sub-broto

210

(e)S1

34910111278

(f)S2

Figura 2.9: Encontro de um broto e um sub-broto.

Depois que a funçãocaminho-aumentante()encontrou e rotulou os vértices do

broto, será executada a funçãoverificar-pilhas()para escolher qual será o próximo valor

para o vérticeu. Esse novo valor pode ser um vértice de um broto ou apenas um vértice

do caminhoM-alternante. O vérticeu é usado na funçãocaminho-aumentante()para

continuar o processo de rotulação que cria o caminhoM-alternante. A funçãoverificar-

pilhas()executa um dos seguintes testes:

• se a pilhaS2 não estiver vazia, então o vérticeu recebe o topo da pilhaS2, sendo

esse valor pertencente a algum broto. Depois, a pilhaS1 recebeu.NUM juntamente

com a marcação #. Essa marcação indica em qual vértice do broto sai o caminho

M-alternante;

• se a pilhaS2 estiver vazia e a pilhaS1 não estiver vazia, então o vérticeu recebe

o topo da pilhaS1 e a funçãocaminho-aumentante()continua o processo de

rotulação, pois não temos vértice do broto que possa dar seqüência ao caminho

M-aumentante;

• se as duas pilhas estiverem vazias, então o caminhoM-aumentante não foi encon-

trado e será finalizada a funçãocaminho-aumentante(), pois todos os vértices dos

caminhosM-alternantes, saindo der, foram visitados e portanto rotulados.


Funçãoverificar-pilhas

Entrada: Lista_Vértices,S1, S2, u

Saída: Verdadeiro,Falso

início1

seS2 6= /0 então2

/* Escolhe um vértice do broto */

u← TOPO(S2); S1← u.NUM#3

senão4

seS1 6= /0 então5

/* Escolhe um vértice da pilha S1 */

u← TOPO(S1)6

senão7

/* Não existe mais vértices nas pilhas */

retorna Verdadeiro8

fim9

fim10

retorna Falso11

fim12

Quando todas as arestas incidentes no vérticeu já foram examinadas, então é

executada a funçãoatualizar-pilhas()para mudar o vértice que será examinado, e se for

o caso terminar a funçãocaminho-aumentante().

Se no topo deS1 tiver uma marcação #, então o vértice faz parte de um broto,

ou de um sub-broto, e não foi encontrada nenhuma aresta para sair do broto a partir do

vérticeu. Nesse caso, a funçãoatualizar-pilhas()apagaNUM(u) das pilhasS1 eS2, pois o

mesmo vértice fica nas duas pilhas quando temos a saída de um broto. Depois é executado

a funçãoverificar-pilhas()para escolher outro vérticeu, que pode ser da pilhaS2 ou S1,

o vérticeu será usado para continuar o caminhoM-alternante. Se as duas pilhas ficarem

vazias, então a funçãoatualizar-pilhas()termina.

Se no topo deS1 não tiver a marcação #, então não foi encontrada nenhuma aresta

incidente no vérticeu que ainda não foi examinada. Portanto, não é possível aumentar o

caminhoM-alternante a partir do vérticeu. A funçãoatualizar-pilhas()apaga duas vezes

o topo da pilhaS1 e tira essa aresta do caminho. Na seqüência o vérticeu recebe o novo

topo da pilhaS1.

Toda vez que a funçãocaminho-aumentante()encontra um caminhoM-

aumentante será executada a funçãoaumentar-emparelhamento(). Essa função utiliza os

rótulos da lista de vértices para criar o caminhoM-aumentante do vérticev até o vérticer.

A figura2.10mostra um subgrafo rotulado que começa no vértice 0 até o vértice 13, pode-


mos observar que o vértice 0 é a raiz do subgrafo e ele não é saturado. O último vértice do

caminhoM-aumentante é o vértice 13. Portanto, o caminhoM-aumentante é formado do

último vértice 13, até a raiz do subgrafo, o vértice 0. No exemplo da figura2.10, o caminho

M-aumentante é composto dos seguintes vértices:P = (13,3,4,8,7,9,10,11,12,2,1,0).

O emparelhamento é aumentado em uma aresta usando a operaçãoM⊕P.

Funçãoatualizar-pilhas

Entrada: Lista_Vértices,S1, S2, u

Saída: Verdadeiro,Falso

início1

seu.NUM em S1 tem marca# então2

/* Não existe aresta para examinar nesse vértice */

REMOVE(S1); REMOVE(S2)3

severificar-pilhas()então4

/* Não existe vértices nas pilhas */

retorna Verdadeiro5

fim6

senão7

/* Remove uma aresta do caminho */

REMOVE(S1); REMOVE(S1); u← TOPO(S1)8

fim9

retorna Falso10

fim11

•6[7,5]

•7[6,8]

• 9[7,10]

•5[4,6] •8[4,7] •10[11,9]

•4[9∗ (7),3] •11[10,12]

•3[2,4] •12[2,11]

•13[3,−1] •2[−1,1]

•1[0,−1]

•0[−1,0]

Figura 2.10: Caminho aumentante.


Funçãoaumentar-emparelhamento

Entrada: Lista_Vértices,v, M

Saída: Um emparelhamentoM′ = M⊕P

/* P é o caminho M-aumentante definido pela Lista_Vértices */

início1

i← Total(Lista_Vértices)-1;M′←M2

enquanto(v.NUM 6= r.NUM) e (i > 0) faça3

se(v.po contém∗) e (i não for par)então4

d← número depois do∗5

a← número antes do∗6

b← v7

/* Adiciona a aresta que sai do sub-broto */

M′←M′+(d,a); v← d; i← i−18

enquantob 6= v faça9

/* Examina as arestas de um broto */

sei for par então10

M′←M′− (v.NUM,v.pe); v← v.pe /* (v.NUM,v.pe) ∈M */11

senão12

M′←M′+(v.NUM,v.po); v← v.po /* (v.NUM,v.po) /∈M */13

fim14

i← i−115

fim16

v← a17

senão18


M′←M′− (v.NUM,v.pe); v← v.pe /* (v.NUM,v.pe) ∈M */20

senão21

M′←M′+(v.NUM,v.po); v← v.po /* (v.NUM,v.po) /∈M */22

fim23

i← i−124

fim25

fim26

retorna M′27

fim28

Nesse processo, a funçãoaumentar-emparelhamento()pode encontrar alguns

brotos ou sub-brotos, ou seja, o caminhoM-aumentante pode passar pelo broto entrando

em seus vértices ou na base broto. A base é o único vértice do broto que pode ser saturado

2.3 Correção do algoritmo de emparelhamento máximo 42

por uma aresta que está emM, mas que não pertence ao broto. Os outros vértices do broto

são todos saturados por arestas deM, que pertencem ao broto.

Quando o caminhoM-aumentante entra em um broto ou no sub-broto, pelos seus

vértices, temos que a aresta de entrada não pertence aM, pois todos os vértices do broto,

com exceção da base, são saturados, ou seja, sempre temos um caminhoM-alternante

de comprimento par, do vértice de entrada do broto até a sua base. Portanto, os próprios

rótulos do broto indicam quais arestas o caminho tem que seguir.

Quando o caminhoM-aumentante entra na base de um broto, ou sub-broto, com

uma aresta que não está emM e não pertence ao broto temos que ver o seguinte: o broto

é um vértice que pode ser saturado por arestas deM que não estão no broto ou não é

saturado porM. Se ele não for saturado, então a base é a raiz do subgrafo e temos um

caminhoM-aumentante. Se ele for saturado, então o caminho segue a aresta que está em

M.

Agora falta analisar quando um caminhoM-aumentante entra em um sub-broto

através de sua base, por uma aresta que está emM, onde o númerov.po da base tem uma

aresta do tipox.NUM∗ (y.NUM). Nesse caso, a aresta(x.NUM,y.NUM) é a aresta que

sai do sub-broto, e ela não é saturada pelo emparelhamento e será inserida no caminho.

O x.NUM é o que pertence ao sub-broto ey.NUM é o vértice do broto. Os rótulos do

vérticey.NUM indicam por onde o caminho tem que seguir até chegar a base do broto. O

vérticex.NUM indica por onde o caminhoM-aumentante tem que continuar. A figure2.10

mostra esse processo, pois quando o caminho chega no vértice4, encontramos uma base

de um sub-broto com a aresta 9∗ (7), então incluímos a aresta 79 no caminho, fazemos o

caminho de volta do vértice 7 até o vértice 4 e depois continuamos o caminho pelo vértice

9.

2.3 Correção do algoritmo de emparelhamento máximo

Os próximos resultados demonstram a correção do algoritmo2.2, que encontra

um emparelhamento máximo em um grafo.

Lema 2.5 (Kameda e Munro [10]) A funçãocaminho-aumentante()encontra correta-

mente, quando existir, um caminho M-aumentante.

Prova. SejamM um emparelhamento er um vértice não saturado porM. No final da

funçãocaminho-aumentante()é retornado como resposta verdade ou falso. Se a função

retorna verdade, então temos um caminhoM-aumentante a partir der.

Quando a função retornar falso, temos que mostrar que não existe um caminho

M-aumentante a partir der. Suponhamos que exista um caminhoM-aumentante a partir

de r, então o vérticey, o outro extremo do caminho, não é saturado e nem rotulado pelo

2.3 Correção do algoritmo de emparelhamento máximo 43

algoritmo. Sejau o último vértice par do caminhoM-aumentante. Seu foi rotulado quer

dizer que a aresta(u,y) não foi examinada, uma contradição, pois pelas linhas 5−7 da

função temos que o algoritmo retornaria verdade. Portanto,u não foi rotulado.

Podemos supor, então, que no final da função existem vértices, que são alcan-

çáveis por caminhosM-alternantes de comprimento par a partir der, que não foram ro-

tulados. Sejaw um vértice de menor distância até o vérticer, através de um caminho

M-alternante de comprimento par, que não foi rotulado no finalda função.

Consideramosu, v, w os últimos vértices desse caminho mínimo. Comow é par,

temos que a arestauv /∈ M e vw∈ M. Pela hipótese, o vérticeu é um vértice rotulado

pelo algoritmo. Então, arestauvserá examinada na linha 5 da função e temos as seguintes

condições. Sev não é rotulado, então pela funçãocaminho-alternante()os vérticesv e

m(v) = w serão rotulados, uma contradição.

Caso o vérticev é rotulado, como ele é saturado, o vérticem(v) = w também foi

rotulado, uma contradição. �

Teorema 2.6 O algoritmo2.2encontra um emparelhamento máximo.

Prova. Queremos mostrar que o algoritmo encontra corretamente umemparelhamento

máximo. O algoritmo procura por um caminhoM-aumentante em cada vértice do grafo,

usando a funçãocaminho-aumentante(). Consideramos através do lema2.5que a função

caminho-aumentante()encontra corretamente esse caminho, se ele existir.

SejaM∗ o emparelhamento encontrado pelo algoritmo. Suponha queM∗ não

seja um emparelhamento máximo. Pelo teorema2.4 de Berge existe um caminhoM∗-

aumentante.

Seja o vérticev um dos extremos do caminhoM∗-aumentante. Quando esse vér-

tice foi examinado pelo algoritmo, não existia caminho aumentante. Portanto, conside-

ramos a iteração do vérticew, na qual passa a existir um caminho aumentante saindo

de v, ou seja, não existe caminhoM∗-aumentante a partir dev, mas existe um cami-

nho M′-aumentante a partir dev, ondeM′ = M∗⊕P e P é um caminho aumentante a

partir dew. SejaC o caminhoM′-aumentante, a partir do vérticev, denotaremos por

C = (v0,v1, ...,vt), ondev = v0.

Como não existe caminhoM-aumentante a partir dev, temos queC eP têm pelo

menos uma aresta em comum. Sejavivi+1 a primeira aresta do caminhoC que esteja em

P. Observamos quei 6= 0, pois o vérticev0 é um vértice não saturado porM′ e os vértices

do caminhoP são todos saturados pelo emparelhamentoM′.

Vamos ver que a arestavivi+1 não pertence aM. Suponha que a arestavivi+1

pertença ao emparelhamentoM. Como ele pertence ao caminhoP, temos, por definição,

que ela não pertence ao emparelhamentoM′. Logo, a arestavi−1vi pertence aM′, pois

2.4 Complexidade do algoritmo de emparelhamento máximo 44

o caminhoC é um caminhoM′-aumentante. Como, por escolha doi, a arestavi−1vi não

pertence aP, temos que a arestavi−1vi pertence aM, pela definição deM′. Contradição,

poisvi está saturado por duas arestas deM. Concluímos que a arestavivi+1 não pertence

aM e, portanto, ela pertence aM′.

Agora queremos mostrar que a partir do vérticev tem um caminhoM-

aumentante. SejaP= (w0,w1, ...,w j ,w j+1, ...,ws) o caminhoM-aumentante, ondew j = vi

e w j+1 = vi+1. Queremos mostrar queCP= (v0,v1, ...,vi−1,w j ,w j−1, ...,w0) é um cami-

nhoM-aumentante. Mostramos quevivi+1 = w jw j+1 não pertence aM. Pela definição do

caminhoP, temos que a arestaw j−1w j pertence aM.

Por outro lado, o caminho(v0, ...,vi−1) é um caminhoM-alternante, pois ele é

M′-alternante e nenhuma aresta pertence aP pela escolha doi.

Falta só mostrar quevi−1vi não pertence aM. Mas isso segue do fato quevi está

saturado, emM, pela arestaw j−1w j . Portanto,CP é um caminhoM-aumentante a partir

dev, uma contradição. Logo,M∗ é um emparelhamento máximo. �

2.4 Complexidade do algoritmo de emparelhamento má-

ximo

O algoritmo2.2 procura a partir de cada um dos vértices um caminho aumen-

tante, encontrando esse caminho, o emparelhamento será aumentado em uma aresta. Para

obtermos a complexidade do algoritmo também temos que analisar a complexidade das

funções: caminho-aumentante e aumentar-emparelhamento.O resultado abaixo faz a aná-

lise da funçãocaminho-aumentante().

Lema 2.7 (Kameda e Munro [10]) Se o algoritmo encontra um caminho M-aumentante,

então podemos identificar um caminho M-aumentante no tempo proporcional ao número

de arestas do caminho.

O lema abaixo faz a análise da funçãoaumentar-emparelhamento().

Lema 2.8 (Kameda e Munro [10]) Seja B um broto aninhado com base b e v, todo vértice

(6= b) que pertence a B, um caminho M-alternante de tamanho par de u ab (dentro de B),

pode ser identificado no grafo pelos rótulos em tempo proporcional ao número de arestas

do caminho.

O teorema abaixo faz a análise da complexidade do algoritmo de emparelha-

mento máximo.

2.5 Emparelhamento máximo em grafos bipartidos 45

Teorema 2.9 (Kameda e Munro [10]) Um emparelhamento máximo pode ser encontrado

no tempo c1nm+c2, onde c1 e c2 são constantes.

Prova. O algoritmo2.2 começa com um grafoG(V,E) e um emparelhamentoM = /0,

depois é analisado todos os vértices deG. Para cada vértice não saturado é usada a função

caminho-aumentante()para encontrar um caminhoM-aumentante. Pelo resultado2.7,

temos que um caminhoM-aumentante é encontrado no tempo proporcional à quantidade

de arestas do caminho, ou seja, as arestas podem ser examinadas no máximo duas vezes.

Então, o tempo total gasto para encontrar um caminhoM-aumentante é limitado por

c1m, ondem= |E| e c1 é uma constante positiva. Pelo resultado2.8, temos que o tempo

necessário para identificar as arestas de um caminhoM-aumentante é limitado porc2m,

ondec2 é uma constante. Portanto, um emparelhamento máximo é alcançado em um

tempo dec1nm+c2, ou seja, no pior caso temos que o tempo éO(nm). �

2.5 Emparelhamento máximo em grafos bipartidos

Nesta seção, consideramos somente os grafos bipartidos. Podemos encontrar

mais facilmente um emparelhamento máximo em grafo bipartido, pois não temos ciclos

ímpares nesses grafos, ou seja, não encontramos nesse caso um broto. Portanto, podemos

utilizar uma versão simplificada do algoritmo de Kameda e Munro para encontrar esse

emparelhamento. Nessa versão não precisamos da funçãoencontrar-broto().

Além disso, o teorema de Hall fornece condições necessáriase suficientes para

determinar se um emparelhamento é máximo num grafo bipartido.

Teorema 2.10 (Hall [8]) Seja G um grafo(X,Y)-bipartido. O grafo G tem um empare-

lhamento que satura X se, e somente se,|N(S)| ≥ |S| para todos S⊆ X.

Prova. Queremos provar que se o grafoG tem um emparelhamento que saturaX, então

|N(S)| ≥ |S| para todosS⊆ X. Suponha que o grafoG tenha um emparelhamentoM que

satura todos os vértices da partiçãoX e sejaSum subconjunto deX. Como os vértices de

S estão saturados por arestas deM, e essas arestas têm vértices únicos emN(S), temos

que a cardinalidade dos vizinhos deSé no mínimo igual à cardinalidade do subconjunto

S, ou seja,|N(S)| ≥ |S|.Agora queremos provar que se|N(S)| ≥ |S| para todosS⊆ X, então existe um

emparelhamentoM que satura todos os vértices deX. Para isso, iremos provar o teorema

através da contrapositiva. SejaM um emparelhamento máximo emG que não saturaX.

Queremos encontrar um conjunto de vérticesS⊆ X tal que|N(S)|< |S|.


Sejau um vértice deX não saturado porM e sejaZ o conjunto dos vértices que

são alcançáveis por caminhosM-alternantes, a partir deu. ComoM é um emparelhamento

máximo, não há caminhosM-aumentantes eu é o único vértice não saturado emZ.

SejamS= Z∩X eT = Z∩Y, conforme exemplo abaixo.

S

X •u • • • • • •

Y • • • • • • • •

T = N(S)

Figura 2.11: Teorema de Hall.

Notamos que o vérticeu pertence aS e que os caminhosM-alternantes que

partem deu atingemY através de arestas que não estão emM e voltam paraX através

de arestas emM. Sendo assim, temos que caday∈ T é adjacente a umx∈ S−{u} por

uma aresta deM, ou sejaT ⊆ N(S).

Pela construção, temos que|T|= |S|−1 e queremos mostrar queT = N(S). Seja

y∈N(S), então por definiçãoy é adjacente a umv emS. Temos um caminhoM-alternante

deu a v, que termina com uma aresta deM. Sevy não pertence aM, temos um caminho

M-alternante deu a y, ou seja,y∈ T. Senão,vy pertence aM. Logov 6= u, pois o vértice

u não é saturado e na verdadevy tem que ser a última aresta do caminhoM-alternante de

u av. Portanto,y pertence aT.

Concluímos queT = N(S) e |N(S)| = |T| = |S| −1 < |S|. Isso completa nossa

prova. �

Uma aplicação para o teorema de Hall é encontrado no resultado abaixo.

Corolário 2.11 (West [30]) Seja G um grafo bipartido k−regular. Então G, tem um

emparelhamento perfeito.

Prova. SejaG um grafo k−regular (X,Y)−bipartido. Queremos mostrar que o grafo

G tem um emparelhamento perfeito. Para isso, demonstraremosas seguintes afir-

mações:|X| = |Y|, G tem um emparelhamentoM que saturaX, e M é um empa-

relhamento perfeito. Primeiramente temos que mostrar que|X| = |Y|. Pela proposi-

ção 1.2, temos que|E| = ∑x∈X d(x). Pela hipótese, o grafo ék−regular e temos que

∑x∈X d(x) = ∑x∈X k = k|X|. Da mesma forma paraY. Logo, k|X| = |E| = k|Y|. Como


k 6= 0, temos|X|= |Y|. Agora, temos que verificar se existe um emparelhamento emG que

saturaX. Será utilizado o teorema2.10para verificar se existe tal emparelhamento. Con-

sideremos um subconjuntoS⊆ X. Sejam o número de arestas incidentes emS. Podemos

observar que sexy é uma aresta,x∈ Se y /∈ S. Pela hipótese,G é k−regular em= k|S|,pois cada vértice deS incide emk arestas. Estas arestas também incidem emN(S). Da

mesma forma, temos pelo menosk|N(S)| arestas incidentes emN(S). Logom≤ k|N(S)|,porque podem ter arestas que incidem emN(S) mas não emS. Assim,k|S| ≤ k|N(S)|implica que|N(S)| ≥ |S|. Portanto, pelo teorema2.10, existe um emparelhamento que

saturaX. Por outro lado, qualquer emparelhamento emG que saturaX também satura

Y, pois |X| = |Y|. De fato, a quantidade de arestas de um emparelhamento que satura

X é |X| = 2|X|/2 = (|X|+ |Y|)/2 = n/2. Segue da definição, que tal emparelhamento é

perfeito. �

•a •b •c

•d

•e

•f

(a) k−regular

•a •b •c

•d

•e

•f

(b) não regular

Figura 2.12: Grafos bipartidos com emparelhamento perfeito.

O grafo da figura2.12(a)é um grafok-regular, bipartido e com emparelhamento

perfeito, como mostra as arestas em negrito. Porém, o grafo da figura2.12(b)é bipartido

com emparelhamento perfeito, mas não regular. Isso mostra que ser regular é uma

condição suficiente, mas não necessária para um grafo bipartido ter um emparelhamento

perfeito. Porém, a condição da igualdade das partições é necessaria.

•a •b

•c

•d

(a) Com emparelhamento perfeito

•a •b •c

•d

•e

•f

(b) Sem emparelhamento perfeito

Figura 2.13: Grafos(X,Y)−bipartidos.

Corolário 2.12 (West[30]) Se um grafo bipartido G tem emparelhamento perfeito, então

|X|= |Y|.

Prova. SejaG um grafo(X,Y)−bipartido. Suponha queG tenha um emparelhamento

perfeito. Por definição um emparelhamento perfeito deG em um grafo(X,Y)−bipartido


satura, em particular, todos os vértices da partiçãoX. Pelo teorema2.10, temos que

|N(S)| ≥ |S|, para todoS⊆ X. Em particular, paraS = X, temos que|N(X)| ≥ |X|.ComoN(X) ⊆ Y, temos que|N(X)| ≤ |Y|, assim|X| ≤ |Y|. Do mesmo modo tem que

o emparelhamento perfeito também saturaY e assim, temos que|Y| ≤ |X|. Portanto,

|X|= |Y|. �

Porém, a igualdade das partições não é uma condição suficiente. A figura2.13(b)

mostra um grafo bipartido com|X|= |Y| que não tem emparelhamento perfeito.

Para os grafos não bipartidos, a condição de serk-regular não garante que ele

tenha emparelhamento perfeito. Logo, podemos observar um exemplo de um grafo 3-

regular, não bipartido e que não tem emparelhamento perfeito. Pois, podemos observar

que não temos um caminhoM-aumentante do vértice 1 para o vértice 2.

•

• • •

• • •

• • 2 • • • • •1

• •

Figura 2.14: Sem emparelhamento perfeito.

CAPÍTULO 3Grafos p-extensíveis

Neste capítulo serão abordados os principais conceitos e teoremas sobre grafos

p-extensíveis. Os grafosp-extensíveis também serão estudados nas principais famílias de

grafos, tais como: grafos bipartido, grafos fator-crítico, grafos planares, grafos livre de

K1,3, árvores e os grafos com grau mínimo. Para maiores informações sobre os grafos

p-extensíveis damos ao leitor duas excelentes referências[26] e [27]. Nesses artigos,

Plummer fez uma coletânea detalhada sobre o assunto.

3.1 Definições Básicas

Seja G um grafo conexo de ordem par. Lembramos que um grafoG é p-

extensível, ondep é um número inteiro entre 0 e(n/2)−1, seG tem emparelhamento

perfeito e se quaisquer conjunto dep arestas independentes (não adjacentes) estende-

se para um emparelhamento perfeito deG, isto é, quaisquerp arestas independentes

estão contidas em algum emparelhamento perfeito deG. Pela definição de grafop-

extensível, podemos observar que todos os grafosp-extensíveis têm emparelhamento

perfeito, portanto são grafos 0−extensíveis. O conceito de 0-extensível corresponde ao

emparelhamento perfeito.

A extensibilidade de G é o maior valor dep, tal queG é p-extensível e a

denotaremos porext(G). Por convenção, um grafo que não ép-extensível por qualquer

p, ou seja, não possui emparelhamento perfeito, temext(G) = −1. Um dos principais

problemas estudados na classe de grafosp-extensível é encontrar esse valor em tempo

polinomial. Temos interesse no problema de decisão de saberse um grafo ép-extensível.

Os grafos da figura3.1 são grafos 1-extensíveis, ou seja, qualquer aresta está

contida em algum emparelhamento perfeito. O grafo da figura3.1(b) também é um

grafo 2-extensível, pois quaisquer duas arestas independentes estão contidas em algum

emparelhamento perfeito. Porém, o grafo da figura3.1(a) não é 2-extensível, pois as

arestasaced f não se estendem para um emparelhamento perfeito.

No próximo resultado podemos observar que se um grafoG tem extensibilidade

p, ele ék-extensível para qualquer valor dek entre 0 ep.

3.1 Definições Básicas 50

•a

•b •c

•d

•e

•f

(a) 1−extensível

•a

•b •c

•d

•e

•f

(b) 2−extensíveis

Figura 3.1: Grafos extensíveis.

Teorema 3.1 (Plummer[21]) Se G é um grafo p-extensível para p≥ 1, então G também

é (p−1)−extensível.

Prova. Suponha que um grafoG sejap-extensível mas não(p−1)-extensível. Em par-

ticular, sejaA um conjunto de(p− 1) arestas independentes que não se estende para

um emparelhamento perfeito e sejaM um emparelhamento perfeito deG. Então, pelo

lema2.1, temos queM⊕A consiste em ciclos pares, vértices isolados e no mínimo dois

caminhosA-aumentantes, pois|M| − |A| = n/2− (p−1) ≥ p+ 1− p+ 1 = 2. Portanto

|M| ≥ |A|+ 2 e as extremidades dos dois caminhosA-aumentantes têm que pertencer a

M. SejaP um desses caminhos. O lema2.2, mostra queP⊕A é um conjunto dep arestas

independentes que, por hipótese, pode ser estendida para umemparelhamento. Além

disso, esse emparelhamento perfeito tem no mínimo uma arestae, que não está emP⊕A,

pois |P⊕A| = p e n/2 > p. ComoP⊕A satura os vértices que são saturados por A,

então a arestaeé independente de A. ComoA é um conjunto de arestas independentes de

cardinalidade|A| = p−1 e a arestae é independente deA, entãoA∪{e} é um conjunto

de p arestas independentes que se estende para um emparelhamento perfeito contendoA,

uma contradição. �

O teorema3.3 mostra a ligação entre o conceito de extensibilidade com o

de conectividade. Primeiramente, vamos ver uma definição e um resultado, que são

necessários para a prova do teorema.

Sejax um vértice eSum conjunto de vértices. Um(x,S)-fan é um conjunto de

caminhos disjuntos dex paraS, desde que eles compartilham apenas o vérticex.

Teorema 3.2 (Menger, Dirac[4]) Um grafo com pelo menos k+1 vértices é k-conexo se,

somente se, para quaisquer x e S,|S| ≥ k, existe um(x,S)-fan de tamanho k.

Teorema 3.3 (Plummer[21]) Se G é p-extensível, então G é(p+1)-conexo.


Prova.Vamos provar por indução emp. Parap = 0, temos queG é um grafo 0-extensível,

e por definição, ele tem emparelhamento perfeito e é conexo, portantoG é 1-conexo.

Parap = 1, temos queG é um grafo 1-extensível e queremos mostrar queG é 2-conexo.

Suponha quev é um vértice de corte eC1, ...Ck são os componentes deG−v comk≥ 2.

Sejavxuma aresta que liga o vérticev a um vérticex deC1. Então, pela hipótese, a aresta

vx estende para um emparelhamento perfeito deG, isso implica que|V(C1)| é ímpar e os

componentes|V(C2)|, |V(C3)|, ..., |V(Ck)| são todos pares, pois o grafo é 1-extensível. Por

outro lado, sejavy uma aresta qualquer que liga o vérticev ao vérticey do componente

C2, segue similarmente que|V(C2)| é ímpar, uma contradição.

Suponha que o resultado é verdadeiro para algump−1≥ 0. Queremos mostrar

que o resultado é válido parap. SejaG um grafo p-extensível comn ≥ 2p+ 2. Pelo

teorema3.1, G é (p−1)-extensível e pela hipótese da induçãoG é p-conexo.

Suponhamos queG não seja(p+1)-conexo. Assim,G tem um conjunto de corte

S de cardinalidadep. SejaC1, . . . ,Ck com k ≥ 2, os componentes deG−S. Notamos

que |V(C1)|+ |V(C2)|+ . . . + |V(Ck)| = |V(G)| − |S| ≥ 2p+ 2− p = p+ 2 > p+ 1 e

pela variação do Teorema3.2 de Menger por Dirac, existe um conjuntoL de p arestas

independentes que ligamSa∪ki=1V(Ci).

Primeiramente, vamos supor que existe algumCi com |V(Ci)| ≥ p. Então, na

verdade, o teorema de Dirac afirma que existep caminhos disjuntos emG ligandoS a

V(Ci) e portanto existe um conjuntoL, dep arestas independentes ligandoV(Ci) aS, que

cobreS. Sejaei uma aresta qualquer deL, ondeei = c1s1 es1 ∈ S. ComoS−s1 não é um

conjunto de corte deG, existe uma arestae′1 ligandos1 a algum vértice deCj para algum

j 6= i. Além disso, seL′ = (L−{e1})∪{e′1}, entãoL′ também é um conjunto de p arestas

independentes emG.

Agora iremos supor quep é par. Existe um emparelhamento perfeito deG que

contémL, portanto|V(Ci)| é par. Por outro lado, temos queL′ também estende para

um emparelhamento perfeito deG, segue que|V(Ci)| é ímpar, uma contradição. Uma

contradição semelhante é alcançada quandop for ímpar.

Portanto, podemos supor que para cada um dos componentes|V(Ci)| ≤ p−1. Assuma que para algumi, 2 ≤ |V(Ci)| = q ≤ p− 1 e sejaV(Ci) = {u1, ...,uq}.ConsideramosR1 = {u1, ...,uq−1}. Temos que|V(G)− (S+V(Ci))| = |V(G)| − |S| −|V(Ci)| ≥ 2p+2− p−q = p−q+2. Escolhamos qualquer conjuntoR2⊂ (V(G)− (S+

V(Ci))), desde que|R2|= p−q+1. Então,|R1∪R2|= q−1+ p−q+1= p e novamente,

usando o teorema de Dirac temosp caminhos disjuntos emG, ligandoSàR1∪R2. Então,

existe um conjuntoL de p arestas ligandoq−1 vértices deCi e p− (q−1) vértices de

(V(G)− (S+V(Ci))) paraS. Sejau o vértice deCi que não é saturado porL. Como

|S| = p, temos queL saturaS e se estende para um emparelhamento perfeitoM de G.

Suponhamos que existe uma arestae = uv independente deL. Comou ∈ V(Ci), então


v /∈V(Cj) para quaisquerj 6= i. ComoL saturaS, v /∈ S. Então,v∈V(Ci). Mas, todos os

vértices deV(Ci), excetou, são saturados porL, uma contradição.

Assim temos que para todoi, 1≤ i ≤ q, |V(Ci)| = 1. Desde queG tenha um

emparelhamento perfeito, segue queq≤ p, logo |V(G)| ≤ 2p, contradizendo a hipótese

de quen≥ 2p+2. �

Seguem das definições e resultados anteriores que os grafosp-extensíveis têm

um limite inferior para o emparelhamento maximal.

Corolário 3.4 Seja G um grafo e M um emparelhamento maximal de G. Se G é p-

extensível, então|M| ≥ p+1.

Prova. SejaM um emparelhamento maximal deG. Suponhamos que|M| = k≤ p. Pela

hipótese, temos queG é p-extensível. Pelo teorema3.1, temos queG é k-extensível. Por-

tanto,M se estende a um emparelhamento perfeito. ComoM é maximal, isso implica que

M é um emparelhamento perfeito, ou seja,|M|= n/2. Logo,n/2≤ p, uma contradição.�

Poderíamos nos perguntar seext(G) = p, será que sempre existe um emparelha-

mento maximal comp+ 1 arestas? A resposta é não, como ilustra o grafoC8 da figura

3.2que tem extensibilidade 1, mas nenhum emparelhamento maximal de cardinalidade 2.

Podemos somente afirmar que, parap 6= ((n/2)−1), existe um emparelhamento maximal

de cardinalidade entrep+1 e((n/2)−1).

• •

• •

• •

• •

Figura 3.2: Grafo C8.

Temos através do resultado abaixo a caracterização de todosos grafos que são

((n/2)−1)-extensíveis.

Proposição 3.5(Ananchuen and Caccetta[1]) Seja G um grafo com n= 2p+2 e k= n/2.

Então G é(k−1)-extensível se, e somente se, G for um Kk,k ou K2k.

Uma condição necessária para um grafo ser 2−extensíveis é dada no seguinte

teorema.


Proposição 3.6(Plummer [21]) Se G é um grafo2-extensível, então G é bipartido

elementar ou bicrítico.

◦a1 •a2

•b1 ◦b2

◦c1

•c2

•d1

◦d2

(a) Bipartido

•a1 •a2

•b1 •b2

•c1

•c2

•d1

•d2

(b) Bicrítico

•a1 •a2

•b1 •b2

•c1

•c2

•d1

•d2

(c) 1-extensível

Figura 3.3: Grafos extensíveis.

O grafo da figura3.3(a)é 2-extensível e bipartido, mas não é bicrítico, pois se

os vérticesa1 e c1 forem apagados, o grafo não terá emparelhamento perfeito. Ografo

da figura3.3(b) é 2-extensível e bicrítico, mas não é bipartido, pois os vértices a1, b1

e c1 formam um ciclo ímpar. O fato de um grafo ser bicrítico não garante que ele seja

2-extensível, como por exemplo, o grafo da figura3.3(c).

No artigo[27], Plummer faz referência a dois resultados sobre o produto carte-

siano de grafosp-extensíveis, esses resultados exibem maneiras de construir grafos com

um número de extensibilidade maior, a partir de um grafo com extensibilidade conhecida.

SejaG1 eG2 dois grafos quaisquer. Oproduto cartesianodeG1×G2 é definido

da seguinte maneira: os vértices do produto são definidos comoV(G1×G2) = {x1x2|x1 ∈V(G1),x2 ∈ V(G2)} e dois vértices do produto{x1,x2} e {y1,y2} são adjacentes se, e

somente se,x1 = y1 ex2y2 ∈ E(G2), ou,x2 = y2 ex1y1 ∈ E(G1).

Teorema 3.7 (Plummer[7]) Sejam G1 e G2 grafos pi-extensíveis, para i= 1,2 e pi 6= 0,

então G1×G2 é (p1 + p2 +1)-extensível.

Teorema 3.8 (Liu e Yu[13]) Se G1 é p-extensível e G2 é conexo e p6= 0, então G1×G2

é (p+1)-extensível.

Com esses resultados podemos criar vários grafos extensíveis, a figura3.4

demonstra um exemplo de tal construção. A figura3.4(a)é um grafo conexo. A figura

3.4(b)é um grafo 1-extensível. O grafo da figura3.4(c)foi obtido através do teorema3.8,

fazendo o produto do grafo da figura3.4(a)pelo grafo da figura3.4(b), obtendo assim um

grafo 2-extensível.

Encontramos um resultado importante, que se refere ao reconhecimento de

grafosp-extensíveis através do reconhecimento apenas de grafos com emparelhamento


◦A

•B

(a)

•aa ◦ba

◦ab

•bb

(b) 1-extensível

◦Aaa •Aba

•Baa

◦Bba

◦Bab

•Bbb

•Aab

◦Abb

(c) 2-extensível

Figura 3.4: Produto de grafos.

perfeito. Se para todos os conjuntosA, ondeA⊆ E(G), o grafoG tem emparelhamento

perfeito, entãoG é p-extensível.

Proposição 3.9Seja G um grafo e A um conjunto de arestas independentes com|A| <|V|/2. O conjunto A se estende para um emparelhamento perfeito se,e somente se, o

subgrafo G−V(A) tem um emparelhamento perfeito.

Prova. SejaA um subconjunto de arestas independentes com|A| < |V|/2. Suponha que

A se estende para um emparelhamento perfeitoM. Por definição, esse emparelhamento

tem|M|= |V|/2 arestas independentes. Considere que|A|= p, logo |V(A)|= 2p, pois as

arestas deA são independentes, ou seja, elas não compartilham vértices. Consideramos,

G′ = G−V(A), onde|V(G′)| = |V| − |V(A)| = |V| − 2p. Queremos mostrar queM′ =

M−A é um emparelhamento perfeito deG′. Temos queM′ ⊆ E(G′) e M′ é um conjunto

de arestas independentes. Além disso,|M′| = |M−A| = |M|− |A| = |V|/2− p = (|V|−2p)/2. Segue da definição queM′ é um emparelhamento perfeito deG′.

Suponha queG′ = G−V(A) tem um emparelhamento perfeitoM′. Temos que

|V(G′)| = |V(G)| − |A| = |V(G)| − 2p. Logo, |M′| = |V(G′)|/2 = (|V(G)| − 2p)/2.

Queremos mostrar queA se estende para um emparelhamento perfeito deG. Con-

sideramosM = M′ ∪ A. Esse conjunto é um emparelhamento deG, pois temos

que as arestas deM′ não compartilham vértices com o conjuntoA. Por outro lado,

|M|= |M′|+ |A|= (|V(G)|−2p)/2+ p = (|V(G)|−2p+2p)/2 = |V(G)|/2 e segue da

definição queM é um emparelhamento perfeito deG. �

No exemplo da figura3.5, as arestas em negrito são arestas que pertencem ao

conjunto A. Com esse resultado podemo ter um algoritmo ingênuo de complexidade

exponencial para identificar se um grafo ép-extensível. Para isso, basta verificar para todo

conjuntoA de p arestas independentes, se o subgrafoG−V(A) tem um emparelhamento

perfeito usando o algoritmo de emparelhamento máximo, visto no capítulo 2.

3.2 Grafos bipartidos 55

•a •b

•d

•c

(a) Estende

•a

•f •b

•e

•c

•d

(b) Não estende

Figura 3.5: Conjuntos A.

Outro resultado muito importante para os algoritmos de grafos extensíveis é

encontrado na proposição abaixo. Esse resultado será usadono algoritmo4.5p-extensível,

esse algoritmo determina se um grafo ép-extensível. O algoritmo verifica para toda aresta

e de G, se o subgrafo geradorG− e é (p− 1)-extensível. Se for verdade para todas as

arestas, então o grafoG é p-extensível. Os algoritmos para grafosp-extensíveis serão

estudados no próximo capítulo.

Proposição 3.10(Plummer[22]) O grafo G é p-extensível, onde p≥ 1, se, e somente se,

para qualquer aresta e pertencente a E(G), G−e é(p−1)-extensível.

3.2 Grafos bipartidos

No artigo[17], Maschlanka e Volkmann mostram como construir uma família de

grafos bipartidos,p-extensíveis,(p+ 1)-regular e(p+ 1)-conexo para quaisquerp e n,

onden≥ 2p+ 2 e n par. Esses grafos são chamados do tipoGn,p e são construídos da

seguinte forma:

• V(Gn,p) = A∪B ondeA = {a0, ...,a(n/2)−1} eB = {b0, ...,b(n/2)−1};

• E(Gn,p) consiste de todas as arestas do ciclo hamiltonianoC =

(a0,b0, ...,a(n/2)−1,b(n/2)−1,a0) e as cordasab, a ∈ A, b ∈ B, com distância

ímpar emC de no máximop;

• sepé par, então as arestasaib(i+(p/2))(mod(n/2)), 0≤ i≤ (n/2)−1 serão adicionadas.

Pela definição da famíliaGn,p, podemos observar que o grafoGn,1 é um ciclo de

tamanhon, ver o exemplo da figura3.6(a). Os grafos da figura3.6 são grafos da família

Gn,p.


◦a0 •b0

•b1

◦a1

(a) G4,1

◦a0

•b2 •b0

◦a2

◦a1

•b1

(b) G6,2

◦a0 •b0

•b3 ◦a1

◦a3

•b1

•b2

◦a2

(c) G8,3

Figura 3.6: Grafos da família Gn,p.

Construimos uma família de grafos bipartidos, planares e 2−extensíveis, a partir

de dois ciclos de tamanhot, comt par,t ≥ 4, da seguinte forma:

• V(2Ct) = A∪B ondeA = {a0,b1...,at−2,bt−1} eB = {b0,a1...,bt−2,at−1};

• as arestas são formadas:

– todas as arestas do ciclo externo(a0,b1, ...,at−2,bt−1,a0);

– todas as arestas do ciclo interno(b0,a1, ...,bt−2,at−1,b0);

– as cordasaibi paraai ∈ A ebi ∈ B.

◦a0 •b1

•b0 ◦a1

◦a3

•b2

•b3

◦a2

Figura 3.7: Família2Ct .

Através da ligação de dois ciclo pares encontramos a famíliade grafos 2Ct , essa

família de grafos são 2-extensíveis. A família de grafos 2Ct é um caso especial da família

de grafosGn,p, como veremos no resultado seguinte. Esse resultado mostraque podemos

ter grafos planares na famíliaGn,p. Porém, não são todos os grafos da famíliaGn,p que


são planares, como por exemplo, o grafoG6,2 da figura3.6(b), que é isomórfico aoK3,3,

conhecido como não planar.

Lembramos que um grafoH é isomórfico a um grafoG (H ∼= G) se existe uma

bijeção f : V(H)→V(G), tal que a arestaxy pertence aE(H) se, e somente se, a aresta

f (x) f (y) também pertence aE(G).

Proposição 3.11O grafo2Ct é isomórfico ao grafo G2t,2, para t par e t≥ 4.

Prova. ConsideramosH = 2Ct e G = G2t,2. Queremos mostrar queH ∼= G. Con-

sidere f como sendo a identidade. Agora, temos que mostrar que toda aresta de

E(H) também pertence aE(G) e vice-versa. Pela definição da família 2Ct , temos

que E(H) = Ee∪ Ei ∪ Ec onde: Ee = {a0b1,b1a2, ...,at−2bt−1,bt−1a0} é o ciclo ex-

terno; Ei = {b0a1,a1b2, ...,bt−2at−1,at−1b0} é o ciclo interno eEc = {aibi para

0 ≤ i ≤ t − 1} são as arestas que ligam os dois ciclos. As arestas dos ciclospo-

dem ser descritas da seguinte forma:Ea = {aib(i+1 mod t) para 0 ≤ i ≤ t − 1}e Eb = {bia(i+1 mod t) para 0 ≤ i ≤ t − 1} e Ee ∪ Ei = Ea ∪ Eb, então te-

mos que E(H) = Ea ∪ Eb ∪ Ec. Agora pela definição da famíliaG2t,2 temos

E(G) = E1∪E2 onde:E1 = {a0b0,b0a1, ...,bt−2at−1,at−1bt−1,bt−1a0} é ciclo hamilto-

niano eE2 = {aib(i+1 mod t) para 0≤ i ≤ t−1} são as cordas. Observamos que

as arestas deEc juntas com as arestasEb formam o ciclo hamiltoniano deG e Ea = E2.

Então as arestasE(H) = Ee∪Ei ∪Ec = Ea∪Eb∪Ec = E1∪E2 = E(G) e temos a bijeção

desejada. �

A extensibilidade dos grafos bipartidos pode ser encontrada por algoritmos com

complexidade de tempo polinomial. No artigo[12], Lakhal e Litzler apresentam um

algoritmo com complexidade deO(m.min(k30 + n,k0n)), ondek0 é a conectividade do

grafo direcionado. Se tiver, o algoritmo encontra um emparelhamento perfeito do grafo

bipartido, transforma-o em grafo direcionado usando o emparelhamento. Depois, ele

encontra a conectividade desse grafo, que é a extensibilidade do grafo inicial.

Vimos no capítulo 1 a definição dek-conexo através de um conjunto de corte, os

próximos resultados mostram outra maneira de definir conectividade. Dois caminhos de

u av sãodisjuntos internamente, se eles têm apenas os extremos em comum.

Teorema 3.12 (Menger [19]) Seja G um grafo com pelo menos k+ 1 vértices. G é k-

conexo se, e somente se, para quaisquer dois vértices de G, existem k caminhos disjuntos

internamente entre eles.

Lembramos que aconectividadeé definida como o menor inteirok, tal queG é

k-conexo. Usaremos o próximo resultado como definição paraaresta-conexo.


Teorema 3.13 (Menger [19]) Seja G um grafo com pelo menos k+ 1 vértices. G é k-

aresta-conexo se, e somente se, para quaisquer dois vértices de G, existem k caminhos

disjuntos em arestas entre eles.

A aresta-conectividadeé definida como o menor inteirok, tal que quaisquer

pares distintos de vértices sejamk-aresta-conexo.

Zhang, em seu artigo[32], apresentou um algoritmo que encontra a extensibili-

dade de grafos bipartidos na complexidade de tempoO(nm). O algoritmo de Zhang usa a

idéia de aresta-conectividade em grafos direcionados.

Um grafo direcionado ou digrafo é uma tripla composta de um conjunto de

vérticesV(G), um conjunto de arestasE(G) e uma função que atribui a cada aresta um

par de vértices ordenados. Essa ordem indica que a aresta terá uma orientação do primeiro

para o segundo vértice.

Esse algoritmo funciona da seguinte maneira: sejaG um grafo bipartido com

emparelhamento perfeitoM. Os vértices de uma partição deG recebem a cor branca e os

vértices da outra partição recebem a cor preta. Uma orientação deG em relação àM é

definida da seguinte maneira:

• oriente todas as arestas deM dos vértices brancos para os vértices pretos;

• oriente todas as arestas que não estão emM dos vértices pretos para os vértices

brancos.

O grafo direcionado obtido, denotado porG(~M), é chamado de grafo residual.

◦1 •2

•6 ◦7

•8

◦ 3

◦5

•4

Figura 3.8: Grafo residual.

No grafo residual apresentam-se dois tipos de aresta-conectividade. A aresta-

conectividade dos vértices brancos para os pretos, denotado porλbp, pela construção do

grafo residual podemos observar queλbp = 1.

O outro tipo é a aresta-conectividade dos vértices pretos para os brancos, de-

notada porλpb. O resultado seguinte mostra a relação entre extensibilidade dos grafos

bipartidos eλpb.

3.3 Grafos fator-crítico 59

Teorema 3.14 (Zhang[32]) Seja G um grafo bipartido com um emparelhamento perfeito

M. Então ext(G) = λpb.

Teorema 3.15 (Zhang [32]) Se G é um grafo bipartido com emparelhamento perfeito,

então ext(G) pode ser computado na complexidade de tempo O(nm).

3.3 Grafos fator-crítico

O conceito de grafop-extensível ek-fator-crítico estão relacionados, desde

que n e k sejam par. Segundo a definição, temos que todo grafok−fator-crítico, com

k < n, é k/2−extensível. Na outra direção, será que existe uma função nãonula f (p)

tal que todo grafop−extensível sejaf (p)−fator-crítico? Essa função é possível se o

grafo p−extensível não for bipartido. Na verdade, veremos que quasenão existem grafos

bipartidos que sejamk-fator-crítico. Caracterizamos os grafos bipartidos que são k-fator-

crítico:

Teorema 3.16Seja G um grafo bipartido. O grafo G é k−fator-crítico se, e somente se,

k = 0 e G tem emparelhamento perfeito ou k= n.

Prova. De acordo com a definição, qualquer grafo bipartido com emparelhamento perfeito

é 0−fator-crítico e todo grafo én-fator-crítico.

SejaG um grafo(X,Y)−bipartido, podemos supor sem perda de generalidade

que|X| ≤ |Y|. Suponha agora queG sejak−fator-crítico. Sek é igual a 0, então o grafoG

é 0−fator-crítico e segue da definição queG tem emparelhamento perfeito.

Podemos supor que 0< k < n. Consideremos um subconjuntoSdek vértices de

X. Se não temos vértices suficientes, completamos com os vértices deY. Se 0< k≤ |X|,entãoS⊆ X. O grafo G− S é um grafo(X − S,Y)−bipartido. ComoG é k−fator-

crítico e |S| = k, entãoG− S tem um emparelhamento perfeito. Pelo colorário2.12,

um grafo bipartido com emparelhamento perfeito tem as duas partições iguais, ou seja,

|X−S|= |Y|. Por outro lado,|X−S|= |X|−k. Logo,|X|−k= |Y|> |X|, uma contradição.

Se |X| < k < n = |X ∪Y| = |X|+ |Y|, entãoX ⊆ S⊆ V(G) = X ∪Y. O grafo

G−Sé um grafo( /0,Y−S)−bipartido. Como pela hipóteseG ék−fator-crítico e|S|= k,

entãoG− S tem um emparelhamento perfeito. Usando o corolário2.12, temos que

|Y−S| = 0. Por outro lado,|Y−S| = |X∪Y|− |S| = n− k. Portanto,n− k = 0 en = k,

uma contradição. �

Em 1980, Plummer foi o primeiro a encontrar uma relação entregrafosp-fator-

crítico ep-extensível, quandop = 2, ver[21]. Anos depois, em 2000, Favaron encontrou

uma relação para qualquer valor dep par, ver[6], generalizando assim o resultado de

Plummer. Essa relação é descrita no seguinte teorema.

3.4 Grafos planares 60

•a •b •c

•d

•e

•f

(a) 0-fator-crítico

•a •b •c

•d

•e

•f

(b) n-fator-crítico

Figura 3.9: Grafos bipartidos.

Teorema 3.17 (Favaron [6]) Seja G um grafo p-extensível, não bipartido e de ordem

n > 2p, onde p≥ 0 e p par. Então o grafo G é p-fator-crítico.

Lembramos que encontrar o número de independência de um grafo é um pro-

blemaNP-completo. O resultado abaixo mostra que os grafosp-extensíveis que não são

bipartidos, possuem um bom limite superior para o número de independência.

Corolário 3.18 (Favaron [6]) Seja G um grafo p−extensível, não bipartido. Então

α(G)≤ (n/2)− p.

3.4 Grafos planares

Nesta seção, consideramos grafosp-extensíveis e planares, mas antes precisamos

introduzir alguns novos conceitos.

Um grafoG é localmente conexo, se para cadav∈V(G), o subgrafo induzido

pelos vizinhos dev, N(v), é conexo.

Sejae1 = u1v1 e e2 = u2v2, duas arestas independentes em um grafo conexo.

Se o grafoG−{u1,v1,u2,v2} contém um componente ímparC0, o subgrafo induzido

G[V(C0)∪{u1,v1,u2,v2}] é chamado de componente borboleta (ou grafo borboleta) eC0

é chamado de corpo do grafo borboleta.

•6

•1 •2

•5

•3

•4

Figura 3.10: Grafo com o componente borboleta.

Os grafos que contém um componente borboleta têm duas arestas que não podem

se estender para um emparelhamento perfeito e, portanto, não são 2−extensíveis. A


figura 3.10 mostra um exemplo de um grafo com um componente borboleta. Podemos

observar que as arestas 13 e 24 são as duas arestas que não podem se estender para

um emparelhamento perfeito. O vértice 5 é o componente ímparque forma o corpo da

borboleta.

Porém, não é possível garantir que um grafo que não tenha componente borboleta

seja 2-extensível. Em seu artigo [24], Plummer mostra um contra-exemplo de um grafo

de 170 vértices, planar, sem componente borboleta, mas que não é 2-extensível.

Plummer encontrou alguns resultados importantes sobre extensibilidade de gra-

fos planares. No resultado seguinte temos um limite superior para a extensibilidade dos

grafos planares, ou seja,ext(G)≤ 2.

Teorema 3.19 (Plummer[23]) Nenhum grafo planar é3−extensível.

Os seguintes resultados apresentam algumas famílias de grafos pelos quais a

extensibilidade é dois.

Proposição 3.20(Plummer[28]) Seja G um grafo de ordem par,5-conexo e planar, então

G é2−extensível.

Proposição 3.21(Plummer[28]) Seja G um grafo de ordem par,4-conexo, local conexo,

planar e sem o componente borboleta, então G é2−extensível.

Vamos apresentar duas famílias de grafos, introduzidas em[28], que atendam

todas as hipóteses da proposição3.21. Os grafos da primeira família,ϕ3 = {G3i }∞

i=1, é

construídos da seguinte maneira:

• G31 é o grafo mostrado na figura3.11;

• este grafo tem um quadrilátero interno{ j,k, l ,m} e um quadrilátero externo

{ j ′,k′, l ′,m′} identificados na figura3.11;

• para obter o grafoG32, precisam de duas cópias do grafoG3

1. Pegue a primeira cópia

do grafoG31 e coloque os vértices do quadrilátero externo sobre os vértices do

quadrilátero interno da segunda cópia do grafoG31. Assim, |V(G3

2)| = 2 x 28 - 4

= 32;

• no geral, para obter um grafoG3i , pegue um grafoG3

i−1 e identifique o quadrilátero

externo do grafoG31 sobre o seu quadrilátero interno. Logo,|G3

i |= 24i +4.

Os grafos da segunda família,ϕ4 = {G4i }∞

i=1, são construídos da seguinte ma-

neira:

• o grafoG41 é igual ao grafoG3

1 da figura3.11;


•j′

•h •a

• e

•A •B

•

• •

•j

•m′ •d • • m •k • •b •k′

•l

• •

•

•D

•C

•g •c • f

•l ′

Figura 3.11: Grafo G31.

•A •B

•a1

•h1 •

b1

•

•g1 • • • c1

•

•f1 •d1

•e1

•D

•C

Figura 3.12: Grafo H41 .


• consideramosH41 , o subgrafo de 16 vértices do grafoG4

1. O subgrafo é mostrado na

figura3.12e consideramos o subgrafoH40 = H4

1−{A,B,C,D};

• consideramosC1, o ciclo de 8 vértices do subgrafoH41 , dado por C1 =

(a1,b1,c1,d1,e1, f1,g1,h1). Esse ciclo é identificado pelas arestas em negrito na

figura3.12;

• pegamos uma cópia do subgrafoH40 e colocamos outro cicloC2 de 8 vértices em

volta do cicloC1;

• sejaC2 o ciclo de 8 vértices do subgrafoH42 , ondeC2 = (a2,b2,c2,d2,e2, f2,g2,h2).

O ciclo é identificado pelas arestas pontilhadas mostrado nafigura3.13;

•A •B

•a2

•h2 • •b2

• ••

•g2 • • • • •c2

•• •

•f2 • •d2

•e2

•D

•C

Figura 3.13: Grafo H42 .

• agora ligue os vértices do cicloC2 com os vértices do cicloC1 da seguinte forma:

– ligue as arestasx1x2, ondex∈ (a,b,c,d,e, f ,g,h);

– faça um ciclo com os vértices:(a1,b2,c1,d2,e1, f2,g1,h2).

• coloque novamente os vérticesA,B,C eD, ligando-os aos vértices correspondentes

a C2 no lugar deC1. O resultado é chamado de grafoH42 e tem 24 vértices, ele é

mostrado na figura3.13.

• agora coloque os 12 vértices que foram tirados do grafoG31. Os vértices tirados

são os seguintes:(a,b,c,d,e, f ,g,h, j ′,k′, l ′,m′), ligando-os aos vérticesA,B,C eD

como no grafoG31. O novo grafo é oG4

2;

• o grafoG42 tem|V(G4

1)|+8 = 36 vértices;

3.5 Grafos livre deK1,3 64

• para obter o grafoG4i , temos que pegar uma cópia do subgrafoH4

(i−1) e repetir os

mesmos passos descritos acima. O grafoG4i tem 28+8(i−1) = 8i +20 vértices.

O seguinte resultado nos fornece um limite inferior para a extensibilidade de

grafos 4-conexos planares.

Proposição 3.22(Plummer[24]) Seja G um grafo de ordem par,4-conexo e planar, então

G é um1-extensível.

3.5 Grafos livre deK1,3

Um grafo que não contém subgrafo induzido isomorfo ao grafo bipartido e

completoK1,3 é chamado delivre de K1,3. Na classe de grafos livres deK1,3 podemos

encontrar o número de independência por um algoritmo polinomial. Nesta seção, vamos

estudar os grafosp-extensíveis livres deK1,3.

O próximo teorema mostra uma relação dos grafosp−extensíveis com os grafos

livres deK1,3.

Teorema 3.23 (Plummer[25]) Seja G um grafo de ordem par,(2p+ 1)−conexo e livre

de K1,3, então G é p-extensível.

Vamos apresentar a seguinte família de grafos, definida em[25], que satisfazem

as hipóteses do teorema acima, denotada por famíliaF(p, r), onder ≥ 2p+1. A família

F(p, r) é composta de grafosp-extensível,(2p+ 1)−conexo e livre deK1,3. Os grafos

dessa família são construídos da seguinte maneira:

• removar − (2p+ 1) emparelhamentos perfeitos disjuntos de um grafo bipartidoe

completo,Kr,r ;

• cada vértice do grafo bipartido gerado tem grau 2p+1;

• substitua cada vértice do grafo bipartido, que tem grau 2p+ 1, por uma cópia do

grafo completoK2p+1. Cada aresta incidente, no vértice do grafo bipartido, será

ligada a um vértice distinto do grafo completoK2p+1, correspondente ao vértice.

O exemplo da figura3.14foi criado usando como base o grafo bipartidoK3,3. O

valor dep foi considerado como 1, ou seja,r − (2p+ 1) = 0 e não removemos nenhum

emparelhamento perfeito do grafo bipartido. Depois para cada vértice do grafo bipartido

é criado um grafo completoK3, assim cada vértice doK3 tem uma aresta que incide no

vértice do grafo bipartido e temos o grafoF(1,3).

Plummer apresenta um limite inferior para o grau mínimo de grafos p-

extensíveis livre deK1,3.

3.5 Grafos livre deK1,3 65

• •

•a

• •

• c′ • • b′ •

• • • •

•c

•b

•a′• •

Figura 3.14: F(1,3).

Teorema 3.24 (Plummer[25]) Seja G um grafo de ordem par, p-extensível e livre de K1,3,

entãoδ(G)≥ 2p.

Vamos apresentar uma família de grafos que satisfaz o teorema3.24. Essa família

é aR(p) definida em[25]. Os grafos dessa família são construídos da seguinte maneira:

• comece comp+1 arestas independentes denotada por,ei = uivi, ondei = 1, ..., p+

1;

• para cada vérticeui , crie 2p− 1 novos vértices, denotados poryi, j , onde j =

1, ...,2p−1;

• agora ligue cada vérticeyi, j com o vérticeui, criando as arestasuiyi, j ;

• ligue o vérticeyi, j com todos outros vérticesyk,l , formando assim um grafo

completo do tipoK(p+1)(2p−1);

• do mesmo modo, para cada vérticevi crie 2p− 1 novos vértices. Esses vértices

serão notados porwi, j ;

• agora ligue cada vérticewi, j com o vérticevi, criando as arestasviwi, j ;

• ligue o vérticewi, j com todos outros vérticeswk,l , formando, assim, um grafo

completo do tipoK(p+1)(2p−1);

• o grafoR(p) resulta em 2(p+1)(2p−1)+2(p+1) vértices.

O grafo da figura3.15 satisfaz a hipótese do teorema3.24, é livre deK1,3, p-

extensível,(p+1)-conexo e comδ(G) = 2p, porém ele não satisfaz a hipótese do teorema

3.23, pois comp+1 vértices, podemos desconectar o grafo. O grafo da figura3.16é livre

deK1,3, de ordem par, comδ(G)≥ 2, mas não é 1-extensível.

3.6 Árvores 66

•u1 •v1

•y1,1

K9

•y1,2

•y1,3

•w1,1

•w1,2

•w1,3

K9

•y2,1 •w2,1

•y2,2 •u2 •v2 •w2,2

•y2,3 •w2,3

•y3,1 •y3,2

•y3,3

•w3,1

•w3,2

•w3,3

•u3

•v3

Figura 3.15: Grafo R(2), As arestas dos K9 não são mostradas.

• •• •• •

Figura 3.16: Livre K1,3.

3.6 Árvores

Uma árvore é um grafo conexo e acíclico. Toda árvore é um grafo bipartidoe

planar com exatamenten−1 arestas, pois comn arestas temos um ciclo. Vamos ver que

as árvores são grafos no máximo 0-extensíveis. O lema abaixomostra que toda árvore

comn≥ 2 tem pelo menos um vértice de grau 1.

Lema 3.25 (Lovász e Vesztergombi[16]) Seja T uma árvore conexa, com pelo menos dois

vértices. Então T contém no mínimo dois vértices de grau1.

Prova. SejaT uma árvore conexa com pelo menos dois vértices. Suponhamos que T

não tem nenhum vértice de grau 1. ComoT é conexo, necessariamente para cada vértice

vi , temosd(vi) ≥ 2. Pela proposição1.1, temos que a soma dos graus é maior ou igual

a 2n. Portanto, o número de arestas é maior ou igual ao den e temos um ciclo, uma

contradição. �

Lema 3.26 Seja G um grafo1-extensível, entãoδ(G)≥ 2.

3.7 Grau mínimo 67

Prova. SejaG um grafo 1-extensível. Pela definição de grafop-extensível temos que

0 ≤ p ≤ (n/2)− 1, logo n ≥ 2p+ 2 e como o grafo é 1-extensível temos quen ≥ 4.

Queremos mostrar queδ(G) ≥ 2. Suponhamos que exista um vérticev0 de grau 1 e

sejav0v1 a aresta que liga esse vértice ao grafo. ComoG é conexo, existe uma aresta

v1v2, ondev0 6= v2. Pela hipótese, o grafo é 1-extensível, ou seja, a arestav1v2 se estende

para um emparelhamento perfeito, uma contradição, pois o vérticev0 não será saturado.�

Teorema 3.27Seja T uma árvore, então T não é1-extensível.

Prova. SejaT uma árvore. Suponha queT é 1-extensível. Pelo lema3.26, δ(T)≥ 2. Pela

hipoteseT é um grafo 1-extensível, então temos pelo menos 4 vértices e pelo proposição

1.1temos 4 arestas, com isso temos um ciclo e o lema3.25leva a uma contradição. �

Corolário 3.28 Seja T uma árvore p-extensível, então p= 0.

•4

•1

•2

•3

(a) Sem emparelhamento

•4

•1

•2

•3

•5

•6

(b) Com emparelhamento

Figura 3.17: Árvores.

3.7 Grau mínimo

Nesta seção queremos mostrar um limite superior para a extensibilidade usando

como parâmetro o grau mínimo do grafo, denotado porδ(G). Antes vamos mostrar um

limite superior de conectividade usando o grau mínimo.

Lema 3.29 Seja G= (V,E) um grafo comδ(G) = k, então G não é(k+1)-conexo.

Prova. Suponha queG seja(k+ 1)-conexo, isso quer dizer que|V| > k+ 1 e para todo

B ⊆ V(G), onde |B| < k + 1, temos queG−B é conexo. Considerex um vértice de

grau mínimo deG e B = NG(x). Logo |B| = |NG(x)| = δ(G) = k < k+ 1 e o vérticex

é isolado emG−B, sendo que todos os vizinhos deles foram removidos. Além do mais

|G−B| = |G|− |B| > k+1− k = 1 e, portanto,G−B contém pelo menos dois vértices,

3.7 Grau mínimo 68

ou seja, ele é desconexo, uma contradição. �

O limite superior da extensibilidade de grafos comδ(G) = k é k− 1, ou seja,

ext(G) ≤ k− 1. Infelizmente esse limite não altera nada quandok ≥ n/2, pois por

definiçãoext(G) é menor ou igual do que(n/2)−1.

Teorema 3.30Seja G um grafo comδ(G) = k, então G não é k−extensível.

Prova. Seja G um grafo comδ(G) = k. O resultado anterior implica queG não é

(k+1)−conexo. Pelo teorema3.3de Plummer, o grafoG não ék-extensível parak≥ 1.

�

O grafo da figura abaixo é 4-regular comδ(G) = 4≥ n/2 e mostra um exemplo

onde a extensibilidade fica longe do valor deδ(G). O grafo não é 2-extensível, pois as

arestas 14 e 23 não se estendem para um emparelhamento perfeito, ele é apenas um grafo

1-extensível.

•1 •2

•5 • 6

•4

•3

Figura 3.18: 4-regular.

CAPÍTULO 4Algoritmos para grafos extensíveis

Neste capítulo serão estudados algoritmos sobre grafos extensíveis. O primeiro

algoritmo determina se um grafo geral é ou não 1-extensível.Será demonstrado a correção

e a complexidade desse algoritmo. Ele utiliza como base o algoritmo de emparelhamento

máximo, estudado no capítulo 2. Também mostraremos que determinar se um grafo é

p-extensível é um problema co-NP.

4.1 Algoritmo 1-extensível

Em 2003, no artigo [14], Lou, Saito e Teng apresentaram um algoritmo que

determina se um grafo geral é ou não 1-extensível. Estruturamos o algoritmo original

para facilitar sua implementação. Em sua estruturação foram usadas as mesmas funções

do algoritmo de emparelhamento máximo de Kameda e Munro do capítulo 2. Depois

modificamos o algoritmo original, criando uma lista de arestasE(L). Essa lista é criada

para receber todas as arestas que ainda não foram extendidaspara um emparelhamento

perfeito.

Primeiramente, o algoritmo4.1 encontra um emparelhamento perfeitoM para

o grafo G, para esse fim usaremos o algoritmo de emparelhamento máximo2.2. Uma

lista E(L) é criada para receber as arestas do grafo, depois são retiradas as arestas deM,

pois todas as arestas que estão emM já se estendem para um emparelhamento perfeito.

Portanto, o algoritmo não precisa verificar as arestas deM.

Para cada aresta da listaE(L), temos que encontrar um cicloM-alternante, esse

processo é repetido até a lista ficar vazia. Caso isso aconteçao algoritmo retorna que o

grafo é 1-extensível. Se para alguma aresta não for encontrado o cicloM-alternante, então

temos que o grafo não é 1-extensível.

Para encontrar os ciclosM-alternantes, iremos utilizar a funçãocaminho-

aumentantedo algoritmo de emparelhamento máximo. Primeiramente, o algoritmo retira

uma aresta da listaE(L), sejae= x0y0 essa aresta. Na seqüência encontramos os vértices

x e y, ondexx0 e y0y pertençam aM, e temos o caminhoP = (x,x0,y0,y) de compri-

mento três. Agora temos que criar um novo subgrafo e um novo emparelhamento. Seja

4.1 Algoritmo 1-extensível 70

G′ = G− x0− y0 esse subgrafo e sejaM′ = M− xx0− y0y esse emparelhamento. Feito

isso, temos no subgrafoG′ somente dois vértices que não estão saturados,x ey. Portanto,

podemos utilizar a funçãocaminho-aumentantepara identificar um caminho aumentante

entre eles. Caso a função não encontre esse caminho, então nãotemos o cicloM-alternante

e o grafo não é 1-extensível.

Algoritmo 4.1: 1-extensível


Saída: Verdade,Falso

início1

M← EmparelhamentoMáximo(G)/* Algoritmo 2.2 */2

seM não é perfeitoentão3

retorna Falso4

fim5

E(L)← E(G)−E(M) /* Cria a lista de aresta que /∈M */6

enquantoexistir e= x0y0 ∈ E(L) faça7

/* Zera a lista e as pilhas */

S1← /0; S2← /0; Lista_Vértices← /08

E(L)← E(L)−e /* Retira uma aresta */9

x←m(x0); y←m(y0) /* Encontra x e y */10

G′←G−x0−y0 /* Cria um subgrafo G′ */11

M′←M−xx0−yy0 /* Cria M′ um emparelhamento para G′ */12

secaminho-aumentante(G′,M′) então13

/* Retira as arestas do ciclo da lista E(L) */

E(L)← diminuir-lista(G′,M′)14

senão15

retorna Falso /* O grafo não é 1-extensível */16

fim17

fim18

retorna Verdade/* O grafo é 1-extensível */19

fim20

Caso a função encontre o caminho aumentante, podemos utilizar a função

diminuir-lista para retirar deE(L) as arestas que não pertençam aM e que estão no

caminhoM′-aumentante. A funçãodiminuir-lista é quase igual à funçãoaumentar-

emparelhamentodo algoritmo do emparelhamento máximo. A única diferença entre elas

é que a funçãodiminuir-lista apenas retira deE(L) as arestas que não estão emM.


Funçãodiminuir-lista

Entrada: Lista_Vértices,v, M, E(L)

Saída: Uma listaE′(L) = E(L)−P

/* P é o caminho M-aumentante definido pela Lista_Vértices */

início1

i← Total(NUM)-1; E′(L)← E(L)2

enquanto(v.NUM 6= r.NUM) e (i > 0) faça3

se(v.po contém∗) e (i não for par)então4

d← número depois do∗5

a← número antes do∗6

b← v7

/* Retira da lista a aresta que entra no broto */

E′(L)← E′(L)− (d,a); v← d; i← i−18

enquantob 6= v faça9

/* Retira as arestas que /∈M em um broto */


v← v.pe /* (v.NUM,v.pe) ∈M */11

senão12

/* A aresta (v.NUM,v.po) /∈M */

E′(L)← E′(L)− (v.NUM,v.po); v← po(v)13

fim14

i← i−115

fim16

v← a17

senão18


v← v.pe /* (v.NUM,v.pe) ∈M */20

senão21

/* A aresta (v.NUM,v.po) /∈M */

E′(L)← E′(L)− (v.NUM,v.po); v← v.po22

fim23

i← i−124

fim25

fim26

retorna E′(L)27

fim28

A figura4.1(a)mostra um grafoG e queremos saber se esse grafo é 1-extensível.


As arestas que estão em negrito representam arestas que pertencem ao emparelhamentoM

e as arestas pontilhadas representam arestas que não foram examinadas pelo algoritmo.

Então vamos aplicar o algoritmo 1-extensível4.1 no grafoG. O primeiro passo é criar

uma lista das arestas que não pertencem aM. Essa lista é denominada deE(L), ou seja,

E(L) = E(G)−M. No exemplo do grafoG temos que a listaE(L) = {12,35,46,78}.Depois o algoritmo escolhe uma aresta deE(L) para encontrar um cicloM-alternante que

contém essa aresta. Vamos escolher a aresta 12 que será retirado da listaE(L), essa aresta

é denominada porx0y0. Agora temos a listaE(L) = {35,46,78} .

A figura 4.1(b)mostra a arestax0y0 e também os vértices x e y, ondex = m(x0)

e y = m(y0). A figura 4.1(c)mostra um subgrafo induzidoH. O subgrafo induzidoH é

obtido a partir da remoção dos vérticesx0 e y0 e mostra os vérticesx e y que não estão

saturados.

Agora o algoritmo chama a funçãocaminho-aumentante()para encontrar um

caminhoM-aumentante do vérticex até o vérticey. No subgrafo induzidoH podemos

observar que temos o caminhoP = {x,5,7,8,6,y} que éM-aumentante e que começa e

termina com arestas que não pertençam aM. Esse caminhoP junto com as arestasxx0,

x0y0 e y0y formam o cicloC, que éM-alternante. Como foi encontrado o caminhoM-

aumentante dex paray, então é chamada a funçãodiminuir-lista() que vai tirar as arestas

do cicloC, que não pertençam aM da listaE(L), fazendo isso a listaE(L) fica vazia e

esse grafo é 1-extensível.

•1 •2

•3 • 4

•5 • 6

•7

•8

(a) GrafoG

•x0

•y0

•x • y

•5 • 6

•7

•8

(b) x0y0 /∈M

◦x ◦ y

•5 • 6

•7

•8

(c) SubgrafoH

Figura 4.1: Grafo1-extensível.

A figura 4.2(a)mostra o grafoG e queremos saber se esse grafo é 1-extensível.

O primeiro passo é criar uma lista das arestas que não pertencem a M. Essa lista

é denominada deE(L), ou seja,E(L) = E(G)−M. No exemplo do grafoG temos

que E(L) = {12,35,46,76,78}. Depois o algoritmo escolhe uma aresta deE(L) para

encontrar um cicloM-alternante que contém essa aresta. Vamos escolher a aresta76

que será retirado da listaE(L), essa aresta é denominada porx0y0. Agora temos a lista

E(L) = {12,35,46,78} .


A figura 4.2(b)mostra a arestax0y0 e também os vértices x e y, ondex = m(x0)

e y = m(y0). A figura 4.2(c)mostra um subgrafo induzidoH. O subgrafo induzidoH é

obtido a partir da remoção dos vérticesx0 e y0 e mostra os vérticesx e y que não estão

saturados.

Agora o algoritmo chama a funçãocaminho-aumentante()para encontrar um

caminhoM-aumentante do vérticex até o vérticey. Mas, o subgrafo induzidoH é

desconexo e não podemos encontrar um caminhoM-aumentante do vérticex para o

vérticey. Então o algoritmo termina e esse grafo não é 1-extensível.

•1 •2

•3 • 4

•5 • 6

•7

•8

(a) GrafoG

•1 •2

•3 • 4

•x • y0

•x0

•y

(b) x0y0 /∈M

•1 •2

•3 • 4

◦x

◦y

(c) SubgrafoH

Figura 4.2: Grafo que não é1-extensível.

O resultado abaixo mostra a correção do algoritmo 1-extensível.

Teorema 4.1 (Lou [14]) Seja G um grafo com emparelhamento perfeito M, nesse caso as

seguintes afirmações são equivalentes:

a) G é1-extensível;

b) para cada aresta e que não pertença a M, existe um ciclo M-alternante que

contém e;

c) para cada aresta x0y0 que não pertença a M, sejam x e y as extremidades de

um caminho M-alternante P de comprimento três, tal que xx0,y0y∈M. Então existe um

caminho M-alternante P0 que conecta x e y, que começa e termina com arestas que não

pertencem a M.

Prova. (a) implica (c): Sejae= abuma aresta que não pertence aM. Conforme a hipótese,

o grafoG é 1-extensível e a arestaese estende para um novo emparelhamento perfeitoM′.

SejaH = M⊕M′. Pelo lema2.1, H é composto de vértices isolados, caminhos alternantes

e ciclos alternantes. Como os dois emparelhamentos são perfeitos, cada vértice é saturado

por M e M′. Logo, o subgrafoH não tem caminhoM-alternante, pois as extremidades

do caminho teriam que ser saturadas por apenas um emparelhamento perfeito, uma

contradição. Os vértices isolados deH são vértices saturados emG, por uma aresta

em M ∩M′. Os ciclos alternantes deH são formados por arestas deM e M′ que não


coincidem. Seja o caminhoP = (x,a,b,y) e a arestae= ab, ondexa e by pertence aM.

Comoe /∈M, temos queP⊆ H. SejaC um ciclo alternante emH que tem as arestas de

P, então denotamosP0 = C−{a,b}, um caminhoM-alternante dex a y, que começa e

termina com arestas que não pertençam aM.

(c) implica (b): Para qualquer arestae que não pertence aM, queremos mostrar

que existe um cicloM-alternanteC que contém a arestae. Consideramose= x0y0 sendo

essa aresta. Sejamx e y as extremidades de um caminhoM-alternanteP de comprimento

três, tal quexx0 e y0y pertençam aM. ConsideramosP = (x,x0,y0,y) o caminhoM-

alternante que contéme. Pela hipótese temos um caminhoM-alternanteP0 que conectax

e y, onde as arestas dos extremos do caminho não pertencem aM. Portanto,C = P∪P0 é

um cicloM-alternante, que contém a arestae.

(b) implica (a): Sejame uma aresta qualquer deG e M um emparelhamento

perfeito deG. See pertence aM, entãoe pode ser estendida paraM. See não pertence a

M, temos que construir um novo emparelhamento perfeito que contenhae. Pela hipótese,

existe um cicloM-alternanteC, que contéme. Pelo lema2.3, M⊕C é um emparelha-

mento perfeito que conteme. �

Vamos analisar a complexidade de tempo do algoritmo 1-extensível. Ele utiliza

o algoritmo de emparelhamento máximo, que tem uma complexidade de tempo de

O(nm). Depois, para cada aresta que não pertença aM, temos que encontrar um ciclo

M-alternante. Para o algoritmo encontrar um cicloM-alternante será utilizado a função

caminho-aumentantee a funçãodiminuir-lista.

Podemos identificar um caminho aumentante, no pior caso, examinando no

máximo duas vezes cada aresta, ou seja, para a funçãocaminho-aumentantetemos uma

complexidade de tempo deO(m). A funçãodiminuir-lista retira da lista as arestas do

caminhoM′-aumentante, no pior caso, examinando todas as arestas desse caminho, ou

seja, temos uma complexidade de tempo deO(m). Portanto, temosO(m) para identificar

as arestas do caminhoM′-aumentante eO(m) para retirar as arestas da lista. Para cada

aresta da lista é executada a funçãocaminho-aumentantee depois a funçãodiminuir-

lista, então temosO(m(m+m)). Portanto, para identificar os ciclosM-alternantes temos

uma complexidade de tempo deO(m2).

O algoritmo 1-extensível utiliza uma complexidade de tempoO(nm), para en-

contrar o emparelhamento perfeito eO(m2) para identificar os ciclosM-alternantes. Por-

tanto, temosO(nm+ m2). Comon≤ m− 1, porqueG é conexo, temos quen ∈ O(m),

então a complexidade de tempo total do algoritmo4.1é deO(m2).

Podemos utilizar o algoritmo de emparelhamento máximo e o resultado do teo-

rema3.9, para encontrar um algoritmo ingênuo que determina se um grafo é 1-extensível.

Para obtermos esse algoritmo basta verificar se o subgrafoG− xy tem emparelhamento

4.2 O problemap-extensível é co-NP 75

perfeito, para cada arestaxy que pertençam aE(G). Nesse caso, temosO(nm) para en-

contrar um emparelhamento perfeito eO(m) para verificar com todas as arestas, então a

complexidade de tempo total desse algoritmo é deO(nm2).

Algoritmo 4.3: 1-extensível-ingênuo



início1

para cadaaresta e= xy∈ E(G) faça2

G′←G−x−y /* Cria um subgrafo */3

M← EmparelhamentoMáximo(G′)4

seM não é perfeitoentão5

/* O grafo não é 1-extensível */

retorna Falso6

fim7

fim8

/* O grafo é 1-extensível */

retorna Verdade9

fim10

Observamos que o algoritmo ingênuo4.3, é menos eficiente do que o algoritmo

1-extensível encontrado por Lou, Saito e Teng. Porém, uma vantagem do algoritmo

ingênuo é que podemos utilizar com maior facilidade e rapidez os outros algoritmos de

emparelhamento máximo, ou seja, se for encontrado um algoritmo mais eficiente temos

um algoritmo ingênuo melhor.

4.2 O problemap-extensível é co-NP

Nesta seção, mostraremos que o problema de decisão de saber se um grafoG

é p-extensível está na classe co-NP. Também vamos apresentar um algoritmo ingênuo e

recursivo, que resolve esse problema em tempo exponencial.

Um problema de decisãoé um problema que possui apenas duas respostas

possíveis: sim ou não. AclasseP de problemas de decisão é a que pode ser resolvida

por um algoritmo que tem uma ordem de crescimento polinomialno tamanho da entrada.

Um algoritmo de verificaçãopara um problema de decisão recebe como entrada

dois argumentos: uma instância do problema e uma cadeia de caracteres conhecida

comocertificado. Um certificado polinomial é aquele que pode ser verificado por um

algoritmo de verificação com complexidade de tempo polinomial no tamanho da entrada


do problema inicial. AclasseNP de problemas de decisão é a que possui certificado

polinomial para a resposta sim. Aclasse co-NP de problemas de decisão é a que possui

certificado polinomial para a resposta não.

Algoritmo 4.4: Decisão co-NP

Entrada: G, A


início1

M← EmparelhamentoMáximo(G) /* Algoritmo 2.2 */2

se|M|= n/2 então3

/* Encontra o emparelhamento sem os vértices do A */

M′← EmparelhamentoMáximo(G−V(A))4

se|M′|= n/2−|A| então5

/* O conjunto A estende */

retorna Verdade6

senão7

/* O grafo não é p-extensível */

retorna Falso8

fim9

senão10


retorna Falso11

fim12

fim13

Mostraremos que existe um certificado polinomial para a resposta não, do

seguinte problema de decisão: sejaG um grafo simples de ordem par, entãoG é p-

extensível? O certificado é um conjuntoA de arestas independentes, onde|A| = p, que

não se estende para um emparelhamento perfeito. Agora, precisamos de um algoritmo de

verificação para testar se o certificado é válido.

O algoritmo 4.4 verifica esse certificado na complexidade de tempoO(nm).

Portanto, esse problema está na classe co-NP. Caso o algoritmo retorne verdade, então

temos o certificadoA, que se estende para um emparelhamento perfeito, e não podemos

afirmar que o grafo ép-extensível. Se o algoritmo retornar falso, então o certificadoA

não estende para um emparelhamento perfeito, logo, podemosafirmar que o grafo não é

p-extensível.

Apresentaremos um algoritmo ingênuo e recursivo4.5, para resolver o problema

de decisãoG é p-extensível? O algoritmo recebe um grafoG e um número inteirop, entre


0 e (n/2− 1), ele retorna verdade seG é p-extensível ou falso, caso o grafo não seja

p-extensível.

Algoritmo 4.5: Extensível

Entrada: G, p


início1

/* Testa se o grafo é 0-extensível */

sep = 0 então2

M← EmparelhamentoMáximo(G) /* Algoritmo 2.2 */3

se|M|= n/2 então4

retorna Verdade5

senão6

retorna Falso7

fim8

fim9

/* Testa se o grafo é 1-extensível */

sep = 1 então10

/* Algoritmo 4.1 */

se1-extensível(G)então11

retorna Verdade12

senão13

retorna Falso14

fim15

fim16

/* Recursão para retirar as arestas ∈ E(G) */

para cadaaresta e= xy∈ E(G) faça17

G′←G−e18

seNão(Extensível(G′, p−1)) então19


retorna Falso20

fim21

fim22

/* O grafo é p-extensível */

retorna Verdade23

fim24


Se o valorp for igual a 0, simplesmente, verificamos se o grafoG tem empa-

relhamento perfeito. Agora quandop = 1 vamos utilizar o algoritmo4.1 para verificar

se o grafoG é 1-extensível. Utilizamos esse algoritmo, pois ele é mais eficiente do que

o algoritmo 1-extensível-ingênuo4.3. Por esses motivos não utilizamos o algoritmo de

emparelhamento máximo.

Quando o valor dep > 1 temos que fazer o seguinte: sejae uma aresta qualquer

do grafo. O algoritmo cria um subgrafo retirando a arestae e seus vértices, depois é

verificado seG− e é (p− 1)-extensível, esse processo é repetido com todas as arestas

do grafo, até que o valor dep seja 1. Se todos os subgrafos forem(p− 1)-extensível,

temos pelo resultado3.10, que o grafo ép-extensível. Se algum subgrafo não for(p−1)-

extensível, então o algoritmo retorna que o grafo não ép-extensível.

Através do algoritmo recursivo acima obtemos a seguinte função de recorrência:

T(m, p) = mT(m−1, p−1), ondem é a quantidade de arestas do grafo de entrada. Para

p= 0, temosT(m,0) = nm. Parap= 1, temosT(m,1) = m2. Por indução, temos que para

p > 1, T(m, p) = mT(m−1, p−1)≤m(m−1)p≤m(p+1). Portanto, a complexidade do

algoritmo éO(m(p+1)). Como o valor dep está entre 1 e(n/2)−1, temos no pior caso

queO(m(n/2)), ou seja,O(√

mn).

Podemos observar na árvore de recursão, que o algoritmo acima encontra vários

subgrafos repetidos. Acreditamos que esse problema possa ser resolvido por programação

dinâmica.

Conclusão

Neste trabalho apresentamos os grafosp-extensíveis, os quais compõem uma

classe de grande importância tanto na Teoria de Grafos, comona Ciência da Computação.

Essa classe ainda apresenta vários problemas em aberto, como por exemplo, o problema

levantado por Plummer em seu artigo[27]: sejamG um grafo ep um número inteiro,

existe um algoritmo de complexidade polinomial para decidir seext(G) = p?

Neste texto apresentamos algumas classes em que a extensibilidade é encontrada

com complexidade de tempo polinomial, como por exemplo: a classe dos grafos biparti-

dos, a classe dos grafos planares e a classe das árvores.

Em algumas classes de grafos temos limites superiores ou inferiores para a

extensibilidade. Para a classe de grafos livres deK1,3 temos um limite inferior deext(G)≥δ(G)/2. Para os grafos gerais encontramos um limite superior deext(G) < δ(G). Para as

árvores, temos queext(G) =−1 ouext(G) = 0. Caracterizamos através do teorema3.16

os grafos bipartidos,k-fator-crítico ek-extensíveis. Esses grafos são os ondek = n ou

quandok = 0 é o grafo tem emparelhamento perfeito.

Sabemos que encontrar um conjunto independente de vérticesde tamanhok,

em um grafo, é um problema que está na classeNP-completo. Portanto, a classe de

grafosp-extensíveis não bipartidos é de grande importância para osestudos dos limites

superiores do número de independência, pois para esses grafos temos um limite superior

deα(G)≤ n/2− p.

Vários exemplos de famílias de grafos 2-extensíveis são apresentados neste texto.

Na classe de grafos bipartidos criamos a família 2Ct , ondet é um valor par. Para os grafos

planares apresentamos as famíliasG3i e aG4

i . Também temos vários exemplos de famílias

de grafosp-extensíveis. Na classe de grafos bipartidos apresentamosa famíliaGn,p e para

os grafos livres deK1,3 mostramos as famíliasF(p, r) e R(p). Os resultados de produtos

de grafosp-extensíveis podem ser utilizados com as famílias citadas acima para obtermos

novos grafos com extensibilidade maior.

Uma contribuição deste trabalho foi a estruturação do algoritmo original de

Kameda e Munro[10], com esse algoritmo encontramos o emparelhamento máximo em

um grafo com uma complexidade de tempo deO(nm). A dificuldade de entendimento

do algoritmo original foi uma das motivações para essa estruturação. Queríamos um

Conclusão 80

algoritmo estruturado para facilitar a sua análise e a sua implementação, pois esse

algoritmo é a base de todos os algoritmos de grafosp-extensíveis conhecidos até agora.

Também estruturamos o algoritmo4.1 de Lou, Saito e Teng [14]. Com esse

algoritmo determinamos se um grafo é 1-extensível, numa complexidade de tempo de

O(m2) utilizando a idéia de cicloM-alternante. Encontramos o resultado2.3, que mostra

que a diferença simétrica entre um ciclo e um emparelhamento, que ajuda na prova do

resultado [14] de Lou, Saito e Teng. Usando a idéia do teorema3.9, obtemos o algoritmo

ingênuo4.3, esse algoritmo tem uma complexidade de tempo deO(nm2). Portanto, o

algoritmo4.1é mais eficiente que o algoritmo ingênuo4.3. Contudo, o algoritmo ingênuo

tem uma grande vantagem: ele não depende do algoritmo de Kameda e Munro, ou seja, se

tivermos um algoritmo mais eficiente para encontrar o emparelhamento máximo podemos

facilmente aplicá-lo no algoritmo ingênuo, melhorando assim a sua complexidade.

Apresentamos os algoritmos deste trabalho, de uma maneira que quaisquer

alunos de graduação, em Ciência da Computação, possam implementá-los, para estudar

os grafosp-extensíveis e produzir várias aplicações práticas dessa classe de grafos.

Como proposta de trabalho futuro sugerimos classificar o problema de decisão,

a saber seG é p-extensível, na classe co-NP-completo ouP. Também podemos utilizar

o resultado3.9 e programação dinâmica, para encontrar um algoritmo mais eficiente do

que o apresentado no capítulo 4, para decidir se um grafoG é p-extensível, para um valor

fixo de p.

Outra proposta é utilizar os algoritmos de grafosp-extensíveis e o poder com-

putacional para sabermos quais são os grafos 1-extensíveiscom atén vértices, ou seja,

teremos para analisar 2

(

n

2

)

grafos, incluído os isomórficos e os desconexos. Em[18]

temos algoritmos que podem gerar grafos que não são isomórficos e nem desconexos, di-

minuindo, assim, a quantidade de grafos que serão analisados. Lembramos que um grafo

comn vértices é no máximo((n/2)−1)-extensível. Por exemplo, paran = 10, os grafos

seriam no máximo 4-extensíveis.

Depois, podemos utilizar os grafos 1-extensíveis, encontrados nesse processo,

para sabermos quais deles são 2-extensíveis. Por fim, podemos utilizar esses resultados

para encontrar os padrões dos grafos 2-extensíveis.

E por fim, podemos criar uma nova família, os grafosp-max extensíveis, onde

p para um grafoG é um número inteiro entre 0 eα′(G)− 1, e se quaisquer conjuntos

de p arestas independentes estende-se para um emparelhamento máximo deG. Então,

propomos generalizar os resultados de grafosp-extensíveis em grafosp-max extensíveis

para estudar as propriedades dessa nova família.

Referências Bibliográficas

[1] ANUNCHUEN, N; CACCETTA, L. On (n− 2)-extendable graphs. Journal of

Combinatorial Mathematics and Combinatorial Computing, 9:153–168, 1994.

[2] BERGE, C. Two theorems in graph theory. Proceedings of the National Academy

of Sciences of the United States of America, 43(9):842–4, 1957.

[3] DIESTEL, R. Graph Theory. Springer-Verlag, Heidelberg, 3 edition, 2005.

[4] DIRAC, G. A. In abstrakten Graphen vorhandene vollständig 4-Graphen und

ihre Unterteilungen. Mathematische Nachrichten, 22(1-2):61–85, 1960.

[5] FAVARON, O. On k-factor-critical graphs . Discussiones Mathematicae. Graph

Theory, 16(1):41–51, 1996.

[6] FAVARON, O. Extendability and factor-criticality . Discrete Mathematics, 213(1-

3):115–122, 2000.

[7] GYÖRI, E; PLUMMER, M. D. The Cartesian product of a k-extendable and an

l-extendable graph is (k+l+1)-extendable. Discrete Math., 101(1-3):87–96, 1992.

[8] HALL, P. On representatives of subsets. Journal of the London Mathematical

Society, 10:26–30, 1935.

[9] INSTITUTE, C. M. http://www.claymath.org/millennium/P_vs_NP/. P vs NP

Problem. 2008.

[10] KAMEDA, T; MUNRO, I. A O(|V|.|E|) Algorithm for Maximm Matching of

Graphs. Springer Wien, 12(1):91–98, 1974.

[11] KARP, R. M. Reducibility Among Combinatorial Problems. Complexity of

Computer Computations, p. 85–104, 1972.

[12] LAKHAL, J; LITZLER, L. A polynomial algorithm for the extendability problem

in bipartite graphs . Information Processing Letters, 65(1):11–16, 1998.

http://www.claymath.org/millennium/P_vs_NP/


[13] LIU, G; YU, Q. Matching extensions and products of graphs, Quo Vadis, Graph

Theory? Annals of Discrete Mathematics, 55:191–200, 1993.

[14] LOU, D; SAITO, A; TENG, L. To determine 1-extendable graphs and its algorithm.

Ars Combinatoria, 69:223–228, 2003.

[15] LOVÁSZ, L; PLUMMER, M. D. Matching Theory. Elsevier Science Ltda, Amster-

dam, 1986.

[16] LOVÁSZ, L; PELIKÁN, J; VESTERGOMBI, K. Matemática Discreta. Sociedade

Brasileira de Matemática, Rio de Janeiro, 2003.

[17] MASCHLANKA, P; VOLKMANN, L. Independence number in n-extendable

graphs. Discrete Math, 154(1-3):167–178, 1996.

[18] MCKAY, B. D. http://cs.anu.edu.au/people/bdm/nauty/.Nauty. 2008.

[19] MENGER, K. Zur Allgemeinen Kurventheorie. Fundamenta Mathematicae,

10:95–115, 1927.

[20] MICALI, S; VAZIRANI, V. V. An O(√

|v||E|) Algorithm for Finding Maximum

Matching in General Graphs. 21st Annual Symposium on Foundations of Compu-

ter Science, p. 13–15, 1980.

[21] PLUMMER, M. D. On n-Extendable Graphs. Discrete Mathematics, 31(2):201–210,

1980.

[22] PLUMMER, M. D. Matching extension and connectivity in graphs. Congressus

Numerantium, 63:147–160, 1988.

[23] PLUMMER, M. D. A theorem on matching in the plane, Graph Theory in

Memory of Gabriel Andrew Dirac . Annals of Discrete Mathematics, 41:347–354,

1989.

[24] PLUMMER, M. D. Extending matchings in planar graphs IV. Discrete Mathema-

tics, 109(1-3):207–219, 1992.

[25] PLUMMER, M. D. Extending matchings in claw-free graphs. Discrete Mathema-

tics, 125(1–3):301–307, 1994.

[26] PLUMMER, M. D. Extending matchings in graphs: a survey. Discrete Mathema-

tics, 127(1-3):277–292, 1994.

[27] PLUMMER, M. D. Extending matching in graphs: an update. Congressus

Numerantium, 116:3–32, 1996.

http://cs.anu.edu.au/people/bdm/nauty/


[28] PLUMMER, M. D. Extending matchings in planar graphs V. Discrete Mathema-

tics, 150(1-3):315–324, 1996.

[29] SCHEINERMAN, E. R. Matemática discreta: uma Introdução. Thomson Learning

Ltda, São Paulo, 2003.

[30] WEST, D. B. Introduction to Graph Theory . Prentice Hall, Inc, Upper Saddle River,

2 edition, 2001.

[31] WITZGALL, D; ZAHN, C. T. J. Modification of edmonds algorithm for maximum

matching of graph. Journal of Research of the National Bureau of Standards,

69B:91–98, 1965.

[32] ZHANG, F; ZHANG, H. Construction for bicritical graphs and k-extendable

bipartite graphs. Discrete Mathematics, 306(13):1415–1423, 2006.

Índice Remissivo

m(v), 34

árvore,66

adjacentes,17

algoritmo de verificação,75

aresta-conectividade,58

aresta-conexo,57

arestas,17

laço,17

múltiplas,17

permitidas,22

proibidas,22

bipartido,19

completo,19

broto,26, 31

base,26

cúbico,18

caminho,20

M-alternante,26

M-aumentante,26

simples,20

certificado,75

polinomial,75

ciclo, 18, 20

M-alternante,26

simples,20

classe

NP, 76

P, 75

co-NP, 76

completo,18

componente,21

conectividade,21, 57

conexo,21

(x,S)-fan,50

k−conexo,21

desconexo,21

conjunto independente,22

máximo,22

maximal,22

diferença simétrica,26

disjuntos internamente,57

elementar,22

emparelhamento,21

máximo,21

maximal,21

perfeito,22

extensível,23, 49

extensibilidade,49

extremidades,17

fator,20

fator-crítico,23

fatores,20

grafo,17

direcionado,58

simples,17

grau,18

máximo,18

mínimo,18

hamiltoniano,21

Índice Remissivo 85

incidente,17

isomórfico,57

Lista_Vértices,31

livre deK1,3, 64

localmente conexo,60

MOVE(), 36

número de independência,22

ordem do grafo,17

planar,18

problema de decisão,75

raiz,32

regular,18

k-regular,18

REMOVE(),36

representação geométrica,17

saturados,21

SegundoTOPO(),36

separador,21

sub-broto,37

subgrafo,19

conexo maximal,21

gerador,20

induzido,19

TOPO(),36

vértices,17

vizinhança,18

vizinhos,18

Documents

Sobre Algoritmo de Emparelhamento Máximo e Grafos p ... · PDF fileANDRÉ DA CUNHA RIBEIRO Sobre Algoritmo de Emparelhamento Máximo e Grafos p-extensíveis Dissertação defendida