ࡱ > B D A )` bjbj 4 s
\ \ \ 8
$ ( [
]
]
]
]
]
]
$ h h P
[
[
. \ G
0
p X
\ \ Resumo
Um grafo G distncia hereditria se G conexo e todo caminho induzido em G isomtrico, isto , as distncias em qualquer subgrafo induzido conexo so as mesmas que as no grafo original. Os grafos de distncia hereditria foram introduzidos e primeiramente caracterizados por Howorka e formam uma importante subclasse dos grafos perfeitos.
Neste trabalho, consideramos o problema de verificar se um dado grafo de distncia hereditria G admite uma clique que intercepte todos os ciclos do grafo, ou seja, estudamos transversais-cliques de ciclos em grafos de distncia hereditria.
Mais formalmente, um transversal-clique de ciclos, ou simplesmente cct (do ingls clique-cycle transversal), de um grafo G, uma clique QUOTE tal que QUOTE para todo ciclo C de G. Logo, um grafo admite cct se e somente se puder ser particionado em uma floresta e um subgrafo completo. Por esta razo, tais grafos so tambm chamados de grafos-(F,C).
Grafos que admitem cct podem ser reconhecidos em tempo polinomial. Entretanto, nenhuma caracterizao de tais grafos conhecida, mesmo para grafos perfeitos. Por esta razo, como contribuio principal desta dissertao, descrevemos uma caracterizao de grafos de distncia hereditria que admitem cct atravs de uma famlia de subgrafos induzidos proibidos. Este resultado amplia estudos similares para grafos cordais e cografos. Alm disso, mostramos que grafos de distncia hereditria que admitem cct podem ser reconhecidos em tempo linear por esta caracterizao.
Palavras-chave: Grafos de distncia hereditria, transversal de ciclos, transversal-clique de ciclos, grafos-(F,C).
. / T U _ `
źvi j!) h h EHUj h h EHUh h PJ j h h PJ Uj`
h h EHUj h h EHU h h j h h U hom 6hu hZ
6hu h`R 6h"? hZ
hZ
6h`R hZ
6hZ
h`R hZ
5CJ aJ ' ` R
s u v x y { | ~ d gdZ
$a$gd|/N gdZ
$a$gdu s
# ; T ^ m n N T s _
`
c m p q r s t v w y z | } ŽŹ h-# j h-# U hZ
hu hom huSY huSY 6huSY hom hu 5h`R hZ
PJ hW hW 6hW h`R hu hu hZ
6hZ
h`R PJ 22 1h:p"? . A!"#$% `
D d
,
3 A "q
k
12T⊆VG b ] ,dA#R, 9 D n 1 ,dA#R,PNG
IHDR < ^a~ sRGB pHYs + IDATHKV;r09 v l7ܦ 7p#tn]99q" 0 o' %h7ypmMV;AI$9PIPɨګa ,"uFJe"AOV A/#jLGQ ZsE%o[9[# ##+ Q]Lf轧Y0 #: Fw P Qn>y&\ Q\ytۍr<4Z-T uk"@{N
Ū{{VzvuUJ̌ ae :cT| aY>?UfVŝ(Ơdazn
veVg
f -UЧ6#WXf ef_T b{> ~0 Jyvq ̑
a \ ,di h`g _S?>Eci9@OV{
IENDB``
D d
,
3 A "q
k
12T⊆VG b ] ,dA#R, 9
n 1 ,dA#R,PNG
IHDR < ^a~ sRGB pHYs + IDATHKV;r09 v l7ܦ 7p#tn]99q" 0 o' %h7ypmMV;AI$9PIPɨګa ,"uFJe"AOV A/#jLGQ ZsE%o[9[# ##+ Q]Lf轧Y0 #: Fw P Qn>y&\ Q\ytۍr<4Z-T uk"@{N
Ū{{VzvuUJ̌ ae :cT| aY>?UfVŝ(Ơdazn
veVg
f -UЧ6#WXf ef_T b{> ~0 Jyvq ̑
a \ ,di h`g _S?>Eci9@OV{
IENDB`a D d
(, ;
3 A "
12T∩VC≠ ∅ b eZ=JEPI$ n eZ=JEPI$PNG
IHDR X mmt sRGB pHYs + :IDATXGX=v0 vz`p-tֱ[ueRrr ]\<`6ǖl J)酐PedUA*IVొ l(t uܛCXyBł>&B`,mWq wr gÿ;E' %vv|WRBKh/cuXnRx f(rIu@
|dF-ӌ \2 !%|w/ !TMDHfQe$F"xW֑jG.P:>SAƣ]Uc`+
XegiqK}{|^ܡk|$]toɢ8x}yBAFz>ɇk)o^f5V<wWEyk8Y94;6># FCr 3e㜭<~6ogV=}wߚa(
12T∩VC≠ ∅ b eZ=JEPI$ e) n eZ=JEPI$PNG
IHDR X mmt sRGB pHYs + :IDATXGX=v0 vz`p-tֱ[ueRrr ]\<`6ǖl J)酐PedUA*IVొ l(t uܛCXyBł>&B`,mWq wr gÿ;E' %vv|WRBKh/cuXnRx f(rIu@
|dF-ӌ \2 !%|w/ !TMDHfQe$F"xW֑jG.P:>SAƣ]Uc`+
XegiqK}{|^ܡk|$]toɢ8x}yBAFz>ɇk)o^f5V<wWEyk8Y94;6># FCr 3e㜭<~6ogV=}wߚa( 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 h H 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 J @ J "? N o r m a l d CJ _HaJ mHsHtH > A >
F o n t e p a r g . p a d r o T i T 0
T a b e l a n o r m a l 4
l 4 a , k ,
0 S e m l i s t a D D Z
0 C a b e a l h o d 8! . . Z
0 C h a r C h a r 2 > > Z
0 R o d a p d 8! . !. Z
0 C h a r C h a r 1 T 1T om 0 T e x t o d o E s p a o R e s e r v a d o B*ph V BV om 0 T e x t o d e b a l o d CJ OJ QJ ^J aJ @ Q@ om 0
C h a r C h a r CJ OJ QJ ^J aJ ` R s v y | %0 ( %0 %0 %0 %0 %0 %0 %0 %0 %0 %0 %0 %0 %0
#t#t T # A A @ 0 (
B
S ? r s s u u v v x y { | ~ r s s u u v v x y { | ~ I -# |/N uSY om Gu !V u @> W Z
"? x `R r @ V1 P @ U n k n o w n G z T i m e s N e w R o m a n 5 S y m b o l 3& z A r i a l 7& { @ C a l i b r i 5& z a T a h o m a " 1 r r 24 p p 2 HX $P Z
2 R e s u m o S i m o n e v i v i a n e Oh +'0 \
$
0 < D L T Resumo Simone Normal.dot viviane 2 Microsoft Office Word @ @ ꥏ@ ꥏ r ՜. +,0 h p |
p ' Resumo Ttulo
! " # $ % & ' ( * + , - . / 0 2 3 4 5 6 7 8 : ; < = > ? @ C R o o t E n t r y F g3 E D a t a
7 1 T a b l e ) W o r d D o c u m e n t 4 S u m m a r y I n f o r m a t i o n ( 1 D o c u m e n t S u m m a r y I n f o r m a t i o n 8 9 C o m p O b j u
F# Documento do Microsoft Office Word
MSWordDoc Word.Document.8 9q