аЯрЁБс>ўџ -/ўџџџ,џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№П‘bjbjqPqP8$::‘џџџџџџЄxxxxxxxŒ ŒЏ n@@@@@@V b. 0 0 0 0 0 0 $ h…ЈT xj@@jjT xx@@i ~ ~ ~ jŠx@x@. ~ j. ~ ~ xx~ @4 pvTD\Ÿгє R~   0Џ ~ -F "-~ ~ H-xЦ Tjj~ jjjjjT T h jjjЏ jjjjŒŒŒDаDŒŒŒаŒŒŒxxxxxxџџџџ Resumo Esta tese aborda diversos conceitos e aspectos de Teoria dos Grafos, tendo como foco principal problemas de partiчуo e de convexidades de caminhos. Para os problemas de partiчуo, consideramos originalmente o problema da M-Partiчуo proposto por Feder, Hell, Klein e Motwani que consiste em verificar se o conjunto de vщrtices de um dado grafo G pode ser particionado segundo as condiчѕes impostas por uma matriz M quadrada e simщtrica de ordem m sob os valores 0,~1,~*, onde os elementos na diagonal principal representam as relaчѕes internas entre os vщrtices de cada uma das m partes, podendo os vщrtices de uma parte i serem completamente adjacentes (M_{ii}=1, e neste caso a parte i щ uma clique); completamente nуo adjacentes (M_{ii}=0, e a parte i щ um conjunto independente); ou nуo terem nenhuma restriчуo (M_{ii}=*). Os mesmos valores (0,1,*) sуo aplicсveis ao restante da matriz, representando as relaчѕes externas, onde M_{ij}=1 indica que todos os elementos da parte i sуo adjacentes a todos os elementos da parte j; M_{ij}=0 indica que nenhum elemento da parte i щ adjacente a algum elemento da parte j; e M_{ij}=* indica que nуo existe restriчуo de adjacъncia entre as partes i e j. A partir do problema da M-Partiчуo, propusemo-nos a estudar duas configuraчѕes especэficas: P_k-Partiчуo e (k,0)^{j}-Partiчуo. O problema da P_k-Partiчуo de um grafo G consiste em encontrar uma partiчуo dos vщrtices de G de forma que, ao escolhermos um vщrtice de cada partiчуo, o grafo induzido por estes vщrtices щ um P_k, para quaisquer que sejam os vщrtices escolhidos; assim, estudamos condiчѕes para que um grafo seja P_k-particionсvel. O problema da (k,0)^{j}-Partiчуo consiste em estudar o problema da M-Partiчуo em que as matrizes M sуo restritas рquelas em que a diagonal principal contenha apenas 0's e a њltima linha/coluna contenha apenas 1's e/ou *'s. Para as convexidades de caminhos, que sуo definidas atravщs de coleчѕes especiais de caminhos em grafos - por exemplo, a coleчуo dos caminhos mэnimos, associada р convexidade geodщsica; ou a coleчуo dos caminhos induzidos, associada р convexidade monofєnica -, propusemos uma estrutura geral (framework) capaz de representar diversas convexidades conhecidas, e mostramos que um conjunto de problemas щ NP-completo quando mantemos esta estrutura na sua forma mais genщrica. No entanto, quando restritos a configuraчѕes especэficas, mostramos que alguns problemas podem se manter difэceis ou apresentar algoritmos polinomiais de acordo com a convexidade escolhida e do problema em questуo. Palavras-chave: Teoria dos Grafos, Convexidades de Caminhos, M-Partiчѕes. Abstract This thesis deals with several aspects and concepts of graph theory, focusing on partition problems and path convexities. Regarding the partition problems, we first consider the M-Partition problem proposed by Feder, Klein, Hell, and Motwani, that consists of verifying if the vertex set of a given graph can be partitioned according to some conditions imposed by a symmetric, square matrix M defined over 0,1,* where the elements in the main diagonal represent internal relations between vertices in each of the m parts: vertices in part i can be completely adjacent (M_{ii}=1, and, in this case, part i is a clique); completely non-adjacent (M_{ii}=0, and, in this case, part i is an independent set); or have no adjacency restrictions (M_{ii}=*). The same values 0,1,* applies to the rest of the matrix, representing external relations between parts, where M_{ij}=1 means that parts i and j are completely adjacent; M_{ij}=0 means that parts i and j are completely non-adjacent; and M_{ij}=* means that parts i and j have no adjacency restrictions. From the M-partition problem, we propose the study of two specific matrix problems: the P_k-Partition problem and the (k,0)^{j}-Partition problem. The P_k-Partition problem consists of finding (if any) a partition of the vertex set such that, by choosing a vertex in each partition, the graph induced by such vertices is a P_k, for any choice of such vertices; therefore, we study conditions for a graph to be P_k-partitionable. The (k,0)^{j}-Partition problem consists of studying the M-Partition problem on restricted matrices M such that their main diagonal contains only 0's and the last row/column contains only 1's and/or *'s. Regarding the path convexities, which are defined over special collections of paths in graphs - for example, the collection of shortest paths, associated with the geodetic convexity; or the collection of induced paths, associated with the monophonic convexity -, we propose a general framework able to represent several well-known convexities, and show that a set of problems is NP-complete when we consider such framework in its more generic formulation. However, when restricted to specific configurations, some problems may still be hard, or admit polynomial algorithms according to the chosen convexity. Keywords: Graph Theory, Path Convexities, M-Partitions. KXa‘эмбУЖЉhU+љhМНOJQJ^JhЫ hМНOJQJ^JhЫ hМН5OJQJ^JhЫ 5OJQJ^J hЫ hМНOJQJ^JmHsH#hЫ hМН5OJQJ^JmHsHўџIJKLMNOPQRSTUVWXabWїяЭяЭяяїїїїїїїїїїїїїїяЭ"$ Ц2”(М Pфx  4 Ш#\'№*„.2Ќ5@9a$gdC@v$a$gdC@v$a$gdЫ ‘§WX‘їеї"$ Ц2”(М Pфx  4 Ш#\'№*„.2Ќ5@9a$gdC@v$a$gdC@v61hP:pхыА|. АШA!АЅ"АЅ#‰$‰%ААФАФ Ф†œ 666666666666666666666666666666666666666666 6666666666 666666666666 666666666666666666666666666666666666666666666666666666666666666666D@ёџD f’NormalCJ^J_HaJmH sH tH >AђџЁ> 0Fonte parсg. padrуoTiѓџГT 0 Tabela normalі4ж l4жaі ,kєџС, 0 Sem lista Œe@ђŒ є9Д0Prщ-formataчуo HTML7 Ц2”(М Pфx  4 Ш#\'№*„.2Ќ5@9CJOJQJ^JaJ@ўЂ@ є9Д0 Char CharCJOJQJ^JaJ‘$џџџџў џ I J K L M N O P Q R S T U V W X a b WX“˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€“Kˆ0Kˆ0L1‘W‘‘џџ_GoBackŸ“Ÿ“iu˜šцш9;­ЏikAMєї\ms|ры< G X ` 4 9 L S } ~ Н О  С У и й ќ ў ?AVWжйСФ)“фхTV~€œЃX ` іј“3X ` b “X ` “Иi–Йi–Кi–Лi–Мi–хW Ы C@v{‚yf’ЈkЋє9ДА1ЙнVНМНехыU+љ“џ@€X X N†X X ‘@@џџUnknownџџџџџџџџџџџџGџ:рAxР џTimes New Roman5€Symbol3& џ:рCxР џArialG€MS ??MS Mincho7џрџ@ŸCambria71 Courier"Aˆ№аЉ b‡G3bGƒ #ƒ #Ё№Ѕ‰ДД24ˆˆ№ќџ(№џ$Pџџџџџџџџџџџџџџџџџџџџџє9Д2џџ6Tэtulo: Partiчѕes & Convexidades de Caminhos em GrafosJoaoHelioўџр…ŸђљOhЋ‘+'Гй0œ˜ифє  ,8 X d p|„Œ”ф8Tэtulo: Partiчѕes & Convexidades de Caminhos em GrafosJoaoNormalHelio3Microsoft Office Word@FУ#@—Щe›г@‚/#\ŸгƒўџеЭеœ.“—+,љЎ0  hp|„Œ” œЄЌД М џф# ˆц 7Tэtulo: Partiчѕes & Convexidades de Caminhos em Grafos Tэtulo ўџџџўџџџ !"#ўџџџ%&'()*+ўџџџ§џџџ.ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РFpчVD\Ÿг0€1Tableџџџџџџџџ-WordDocumentџџџџџџџџ8$SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџ$CompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq