ࡱ> NPMq`bjbjqPqP7(::llll, $6         $hJ'   '  <        6Mgl | R 0 X X X P ' ' H$H Resumo Um grafo do tipo prisma complementar surge da unio disjunta do grafo  QUOTE  , do seu complementar  QUOTE   e da adio de um emparelhamento entre os vrtices correspondentes em  QUOTE   e  QUOTE  . Essa classe de grafos foi introduzida recentemente e existem inmeros problemas em aberto a seu respeito. Dois problemas clssicos da teoria dos grafos, determinar se em um dado grafo existe uma clique de ordem  QUOTE   e determinar se em um dado grafo existe um conjunto independente de ordem  QUOTE  , foram provados NP-completos quando o grafo de entrada um prisma complementar. Nessa dissertao, estudamos as complexidades dos problemas da clique e do conjunto independente sob a tica da complexidade parametrizada. Inicialmente provamos utilizando a teoria de Ramsey que estes problemas possuem um ncleo e, portanto, so Tratveis por Parmetro Fixo (FPT). Em seguida, mostramos atravs de PPT redues que tanto determinar se o grafo possui uma clique de tamanho  QUOTE   quanto determinar se o grafo possui um conjunto independente de tamanho  QUOTE   em grafos prismas complementares, quando parametrizados pelo tamanho da soluo  QUOTE  , no possuem ncleo polinomial. Alm disso, abordamos o problema 2-contaminao no contexto dos prismas complementares. Esse problema consiste em infectar um determinado grafo por completo partindo de um conjunto de vrtices infectados inicialmente. Para que um vrtice seja contaminado, basta que pelo menos 2 de seus vizinhos estejam contaminados. A propagao da contaminao ocorrer seguindo tal regra at que todos os vrtices do grafo estejam contaminados. Sabe-se que o conjunto mnimo de vrtices necessrio para contaminar um grafo deste tipo no mximo 5. Para esse problema, provamos que o conjunto mnimo necessrio para contaminar todo o grafo no mximo 3. Com isso, descobrimos uma estratgia algortmica para encontrar tal conjunto. Palavras-chave: Cliques, Conjuntos Independentes, 2-Contaminao, Prismas Complementares. Abstract The complementary prism graph arises from the disjoint union of the graph  QUOTE   and its complement  QUOTE   by adding the edges of a perfect matching joining pairs of corresponding vertices of  QUOTE   and  QUOTE  . This class of graph was recentely introduced and there are many open questions about it. Two classical problems of graph theory, to determine if in a given graph there is a click of order k and to determine if in a given graph there exists an independent set of order  QUOTE  , were proved NP-complete when the input graph is a complementary prism. In this dissertation, we study the complexities of the problems of the clique and the independent set from the point of view of the parameterized complexity. First we prove using Ramsey's theory that these problems have a kernel and therefore are Fixed Parameter Treatable (FPT). Then we show through PPT reductions that both determine if the graph has a clique of size  QUOTE   and determine if the graph has an independente set of size  QUOTE   in complementary graphs prisms, when parameterized by the size of solution  QUOTE   , have no polynomial kernel. In addition, we address the 2-contamination problem in the context of complementary prisms. This problem consists in infecting a certain graph completely starting from a set of initially infected vertices. For a vertex to be contaminated, it is enough that at least 2 of its neighbors are contaminated. The propagation of the contamination will occur following this rule until all the vertices of the graph are contaminated. It is known that the minimum set of vertices necessary to contaminate a graph of this type is at most 5. For this problem, we proved that the minimum set necessary to contaminate the entire graph is at most 3. Thus, we discovered an algorithmic strategy to _nd such a set. Keywords: Cliques, Independent Sets, Irreversible Set, Complementary Prisms. MNUVWXYZpqxyz{|} ɸɢɸɌɸvɸk`ɸj| h (h[ldUj h (h[ldUjh (h[ldUj$h (h[ldUjXh (h[ldUjh (h[ldUjh (h[ldUjh (h[ldU h (h[ldCJOJQJ^JaJ)jh (h[ldCJOJQJU^JaJ hG&=h[ldCJOJQJ^JaJ hG&=h[ldCJ(OJQJ^JaJ($     d7$8$H$gdG&=$d7$8$H$a$gd2=$d7$8$H$a$gdG&=         I J Q R S T U V βΜβxβmbβjEh (h[ldUjjh (h[ldUjh (h[ldUjh (h[ldUh[ldCJOJQJ^JaJjh (h[ldUjh (h[ldU hG&=h[ldCJOJQJ^JaJj#h (h[ldU)jh (h[ldCJOJQJU^JaJ h (h[ldCJOJQJ^JaJjHh (h[ldU" d e ghopqrstβjj_jTjjIjjb$h (h[ldUj"h (h[ldUj h (h[ldU(h2=h[ldCJOJQJ^JaJmH sH  h;h[ldCJ(OJQJ^JaJ(&hG&=h[ld5CJOJQJ\^JaJh[ldCJOJQJ^JaJ hG&=h[ldCJOJQJ^JaJjh (h[ldU)jh (h[ldCJOJQJU^JaJ h (h[ldCJOJQJ^JaJj h (h[ldUijd7$8$H$gdG&=$d7$8$H$a$gd2=$d7$8$H$a$gd;   !"#$%&*+2345ʿߴʩߞʓ߈}rgj6h (h[ldUj4h (h[ldUj2h (h[ldUj0h (h[ldUj/h (h[ldUjR-h (h[ldUj+h (h[ldUj)h (h[ldUj'h (h[ldU(h2=h[ldCJOJQJ^JaJmH sH )jh (h[ldCJOJQJU^JaJj.&h (h[ldU(567jrʿߴʜ.h2=h[ld5CJOJQJ\^JaJmH sH j<h (h[ldUj@:h (h[ldU(h2=h[ldCJOJQJ^JaJmH sH )jh (h[ldCJOJQJU^JaJje8h (h[ldU 50P:pm/ =!"#$% Dd D  3 A"b.,+3 H}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D  3 A"b4ߣa4 nCnߣa4 nPNG  IHDR  esRGB pHYs+IDAT(S0Ehq{Get+.H@B((2`A=}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D  3 A"b.,+3 H}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D  3 A"b4ߣa4 n Cnߣa4 nPNG  IHDR  esRGB pHYs+IDAT(S0Ehq{Get+.H@B((2`A=}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D   3 A"bCd8@{&nd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{& gCnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D   3 A" bCd8@{&Bnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{& Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D   3 A" bCd8@{&nd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{& Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{&nd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{& Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{&dnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D   3 A"bCd8@{& ?Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"b.,+3 H}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D   3 A" b4ߣa4 nr&Cnߣa4 nPNG  IHDR  esRGB pHYs+IDAT(S0Ehq{Get+.H@B((2`A=}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D  3 A"b.,+3 H(n,+3 H}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D   3 A" b4ߣa4 n-Cnߣa4 nPNG  IHDR  esRGB pHYs+IDAT(S0Ehq{Get+.H@B((2`A=}yos=q/us*ζ.J6 ޏ{Ж:A .IENDB`Dd D  3 A"bCd8@{&b/nd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A" bCd8@{& =1Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{&3nd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{& 4Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{&6nd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{& 8Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D ! 3 A" bCd8@{&:nd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB`Dd D  3 A"bCd8@{& _<Cnd8@{&PNG  IHDRsRGB pHYs+IDAT8Oc?рh W='!0/`[Մ0;0訩0UǬT TkǬ¼AFߙh Cv,Z!o쎴mĥh;@3,Į怌 @=.ʁaa6/P7&!b$IENDB` 666666666666666666666666666666666666666666 6666666666 666666666666 666666666666666666666666666666666666666666666666666666666666666666N@N U Normal dCJ^J_HaJmHsHtH >A> 0Fonte parg. padroTiT 0 Tabela normal4 l4a ,k, 0 Sem lista BB G&=0Placeholder Text B*phVV G&=0Texto de balo dCJOJQJ^JaJ@@ G&=0 Char CharCJOJQJ^JaJ(     ij00000000000000000000000000000I0T\ 5  MWYpz|ISUgqs  # % * 4 6 #################8@0(  B S  ?_GoBack,8&,ghopqt     ! " # & ) 8 =KM f   o z 333G&=2=4DB[ld (;m*{U p@@**Yu**@@UnknownG:Ax Times New Roman5Symbol3& :Cx Arial7&@Calibri5& >[`)Tahoma"AjGƚjtD tD !242($PG&=2ResumopripeHelioOh+'0l  ( 4 @LT\dResumopripeNormalHelio3Microsoft Office Word@ @,etUe@ܴgtD ՜.+,0 hp|   Resumo Ttulo  !"#$%&'()*+,-./012356789:;<>?@ABCDFGHIJKLORoot Entry FOgQData =1Table4XWordDocument7(SummaryInformation(=DocumentSummaryInformation8ECompObju  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q