ࡱ > , . + bjbjUU > ? ?
0 F `! - 0 v v v v : Propriedades do Produto de Grafos
O desenvolvimento de propriedades tericas de uma estrutura matemtica enriquece nossa biblioteca de solues do respectivo campo de conhecimento. Vrias situaes da vida real podem ser modeladas como problemas em grafos. A partir da, os conhecimentos disponveis na Teoria dos Grafos podem ser utilizados para tratar o problema especfico. Neste trabalho, estudamos a operao de produto de grafos, com nfase no produto cartesiano e no produto complementar (uma generalizao do produto cartesiano).
O produto cartesiano de grafos considerado um adequado sintetizador de topologias de redes, pois herda as propriedades dos grafos fatores de forma interessante do ponto de vista dos critrios comumente analisados em redes de interconexo. Alm de enriquecerem a teoria, estas pesquisas auxiliam a anlise e a criao de topologias de redes de produto. Neste trabalho apresentamos cerca de quarenta propriedades conhecidas do produto cartesiano agrupadas por temas da Teoria dos Grafos, visando identificar principais resultados j publicados e despertar assim a identificao de problemas em aberto.
Dando continuidade a estas pesquisas, desenvolvemos propriedades sobre a existncia de emparelhamentos perfeito e quase-perfeito no grafo gerado pelo produto, assim como propriedades sobre o nmero desemparelhante, em funo de seus fatores.
Para redes em que essencial cada processador possuir a qualquer instante um parceiro especial, o nmero desemparelhante do grafo que modela a topologia subjacente mede a robustez do sistema no caso de falha de aresta. Isto , o nmero desemparelhante critrio topolgico relacionado tolerncia a falhas. Os resultados desenvolvidos sobre emparelhamento possibilitaram o clculo do nmero desemparelhante de algumas topologias de rede de interconexo que so produto cartesiano de grafos, a saber: hiper-Petersen; Petersen n-dobrado; cubo- Petersen dobrado; hiper-estrela; estrela-cubo; hipercubo. Tambm permitiram observar que a otimalidade do nmero desemparelhante herdada dos grafos fatores, quando eles possuem nmero par de vrtices. Ou seja, se duas topologias de tamanho par forem timas em relao ao nmero desemparelhante, a topologia criada pelo produto delas tambm ser. Essa observao refora o produto como boa estratgia para criao de topologias. Em relao complexidade, observamos que o problema do nmero desemparelhante polinomial para grafos de grau mnimo limitado, como o caso de rvores e de grafos planares. Para grafos bipartidos, provamos que o problema NP-Completo.
Estudamos tambm o produto complementar de grafos, introduzido em 2007 como generalizao do conceito de produto cartesiano. Mais especificamente, investigamos a ciclicidade / hamiltonicidade no prisma complementar -- um caso particular do produto complementar. Respondendo a questes em aberto, elaboramos uma caracterizao da circunferncia do prisma complementar de rvores e demonstramos que o prisma complementar possui ciclos de todos os tamanhos entre 3 e sua circunferncia.
O produto cartesiano de grafos uma operao com muitas propriedades ainda a serem estudadas. um tema frtil para trabalhos futuros e igualmente amplo pois percorre muitos outros temas clssicos da Teoria de Grafos. Estas propriedades precisam ser investigadas, e ento incorporadas ao conhecimento cientfico da humanidade.
Palavras-chave: Produto de Grafos, Produto Cartesiano, Prisma Complementar, Redes de Interconexo, Emparelhamento, Ciclicidade.
" e m o w x y T U c hET hQ 5\
hQ ^J h^ hQ 6] hQ h2DV hQ 5CJ \aJ "
v h
( T U $a$gdET $a$gd^ $a$gd2DV < P 1h:pET . A!"#$% Dp j 6 6 6 6 6 6 6 6 6 v v v v v v v v v 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 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 2 0 @ P ` p 2 ( 0 @ P ` p 0 @ P ` p 0 @ P ` p 0 @ P ` p 0 @ P ` p 0 @ P ` p 8 X V ~ OJ PJ QJ _HmHnHsHtH R ` R N o r m a l d CJ PJ ^J _HaJ mHsHtH D A D 0 D e f a u l t P a r a g r a p h F o n t R i R 0 T a b l e N o r m a l 4
l 4 a ( k (
0 N o L i s t PK ! [Content_Types].xmlj0Eжr(Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi} ;~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭? PK ! ֧ 6 _rels/.relsj0 }Q%v/C/} (h"O
= C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_ 6LR7`0̞O,En7Lib/Se е PK ! ky theme/theme/themeManager.xml M
@}w7c(Ebˮ CAǠҟ7՛K
Y,
e.|,H ,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+&
8 PK ! P theme/theme/theme1.xmlYOo6w toc'vuر-Mn iP@I}úama[إ4:l ЯGRX^6؊>$ !)O^rC$y@ /yH*)UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSe bORD۫qu gZo~ٺlAplxpT0+[}`j zA V2Fi@qv֬5\|ʜ̭NleXd sjcs7f
W+Ն7` g ȘJj|h(KD-
dXiJ؇(x$( :;˹! I_TS 1?E ??ZBΪmU/ ?~xY'y5g&/ɋ>GMGeD3Vq%'#q$8K )fw 9:ĵ
x}rxwr:\TZaG*y8IjbRc|XŻǿI
u3KGnD 1NIBs
RuK>V.E L+M2#'fi ~V vl{u8z H
* :( W ☕
~JTe\O*tHGHY }KNP*ݾ˦ TѼ9/#A7qZ $*c?qUnwN%Oi4 =3ڗP
1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g-
eW
)6-rC Sj
id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q% p%m&]caS l=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f
Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ .uχYC6OMf3or$5N HT[XF64T,ќM0E)`#5XY`פ ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R 3U~7+#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vp IYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07% < ҍ PK !
ѐ ' theme/theme/_rels/themeManager.xml.relsM
0wooӺ&݈Э5
6?$Q
,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{ P8g/ ]QAsم(#L[ PK- ! [Content_Types].xmlPK- ! ֧ 6 + _rels/.relsPK- ! ky theme/theme/themeManager.xmlPK- ! P theme/theme/theme1.xmlPK- !
ѐ ' theme/theme/_rels/themeManager.xml.relsPK ]
! + ET p Q S u m m a r y I n f o r m a t i o n ( 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 # C o m p O b j y
F' Microsoft Office Word 97-2003 Document
MSWordDoc Word.Document.8 9q
F# Documento do Microsoft Office Word
MSWordDoc Word.Document.8 9q