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
ANDRÉ DA CUNHA RIBEIRO
Sobre Algoritmo de EmparelhamentoMáximo e Grafos p-extensíveis
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
ANDRÉ DA CUNHA RIBEIRO
Sobre Algoritmo de EmparelhamentoMáximo e Grafos p-extensíveis
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:
2.1 Emparelhamento máximo 27
• 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.
2.1 Emparelhamento máximo 28
◦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
2.2 Algoritmo de Emparelhamento Máximo 30
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
Entrada: GrafoG qualquer
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.
2.2 Algoritmo de Emparelhamento Máximo 31
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.
2.2 Algoritmo de Emparelhamento Máximo 32
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
2.2 Algoritmo de Emparelhamento Máximo 33
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.
2.2 Algoritmo de Emparelhamento Máximo 34
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
2.2 Algoritmo de Emparelhamento Máximo 35
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.
2.2 Algoritmo de Emparelhamento Máximo 36
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.
2.2 Algoritmo de Emparelhamento Máximo 37
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
2.2 Algoritmo de Emparelhamento Máximo 38
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.
2.2 Algoritmo de Emparelhamento Máximo 39
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-
2.2 Algoritmo de Emparelhamento Máximo 40
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.
2.2 Algoritmo de Emparelhamento Máximo 41
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
sei for par então19
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|.
2.5 Emparelhamento máximo em grafos bipartidos 46
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
2.5 Emparelhamento máximo em grafos bipartidos 47
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
2.5 Emparelhamento máximo em grafos bipartidos 48
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.
3.1 Definições Básicas 51
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
3.1 Definições Básicas 52
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.
3.1 Definições Básicas 53
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
3.1 Definições Básicas 54
◦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.
3.2 Grafos bipartidos 56
◦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
3.2 Grafos bipartidos 57
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.
3.2 Grafos bipartidos 58
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
3.4 Grafos planares 61
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;
3.4 Grafos planares 62
•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 .
3.4 Grafos planares 63
• 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
Entrada: GrafoG qualquer
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.
4.1 Algoritmo 1-extensível 71
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 */
sei for par então10
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
sei for par então19
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.
4.1 Algoritmo 1-extensível 72
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} .
4.1 Algoritmo 1-extensível 73
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
4.1 Algoritmo 1-extensível 74
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
Entrada: GrafoG qualquer
Saída: Verdade,Falso
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
4.2 O problemap-extensível é co-NP 76
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
Saída: Verdade,Falso
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
/* O grafo não é p-extensível */
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
4.2 O problemap-extensível é co-NP 77
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
Saída: Verdade,Falso
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
/* O grafo não é p-extensível */
retorna Falso20
fim21
fim22
/* O grafo é p-extensível */
retorna Verdade23
fim24
4.2 O problemap-extensível é co-NP 78
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.
Referências Bibliográficas 82
[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.
Referências Bibliográficas 83
[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