Página 1 dos resultados de 1164 itens digitais encontrados em 0.003 segundos

Impacto da geração de grafos na classificação semissupervisionada; Impact of graph construction on semi-supervised classification

Sousa, Celso André Rodrigues de
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 18/07/2013 PT
Relevância na Pesquisa
37.6%
Uma variedade de algoritmos de aprendizado semissupervisionado baseado em grafos e métodos de geração de grafos foram propostos pela comunidade científica nos últimos anos. Apesar de seu aparente sucesso empírico, a área de aprendizado semissupervisionado carece de um estudo empírico detalhado que avalie o impacto da geração de grafos na classificação semissupervisionada. Neste trabalho, é provido tal estudo empírico. Para tanto, combinam-se uma variedade de métodos de geração de grafos com uma variedade de algoritmos de aprendizado semissupervisionado baseado em grafos para compará-los empiricamente em seis bases de dados amplamente usadas na literatura de aprendizado semissupervisionado. Os algoritmos são avaliados em tarefas de classificação de dígitos, caracteres, texto, imagens e de distribuições gaussianas. A avaliação experimental proposta neste trabalho é subdividida em quatro partes: (1) análise de melhor caso; (2) avaliação da estabilidade dos classificadores semissupervisionados; (3) avaliação do impacto da geração de grafos na classificação semissupervisionada; (4) avaliação da influência dos parâmetros de regularização no desempenho de classificação dos classificadores semissupervisionados. Na análise de melhor caso...

Relational approach of graph grammars; Abordagem relacional de gramática de grafos

Cavalheiro, Simone André da Costa
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Tese de Doutorado Formato: application/pdf
ENG
Relevância na Pesquisa
37.54%
Gramática de grafos é uma linguagem formal bastante adequada para sistemas cujos estados possuem uma topologia complexa (que envolvem vários tipos de elementos e diferentes tipos de relações entre eles) e cujo comportamento é essencialmente orientado pelos dados, isto é, eventos são disparados por configurações particulares do estado. Vários sistemas reativos são exemplos desta classe de aplicações, como protocolos para sistemas distribuídos e móveis, simulação de sistemas biológicos, entre outros. A verificação de gramática de grafos através da técnica de verificação de modelos já é utilizada por diversas abordagens. Embora esta técnica constitua um método de análise bastante importante, ela tem como desvantagem a necessidade de construir o espaço de estados completo do sistema, o que pode levar ao problema da explosão de estados. Bastante progresso tem sido feito para lidar com esta dificuldade, e diversas técnicas têm aumentado o tamanho dos sistemas que podem ser verificados. Outras abordagens propõem aproximar o espaço de estados, mas neste caso não é possível a verificação de propriedades arbitrárias. Além da verificação de modelos, a prova de teoremas constitui outra técnica consolidada para verificação formal. Nesta técnica tanto o sistema quanto suas propriedades são expressas em alguma lógica matemática. O processo de prova consiste em encontrar uma prova a partir dos axiomas e lemas intermediários do sistema. Cada técnica tem argumentos pró e contra o seu uso...

Higher-order graph rewriting systems; Sistemas de reescrita de grafos de alta ordem

Machado, Rodrigo
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Tese de Doutorado Formato: application/pdf
ENG
Relevância na Pesquisa
37.56%
Programas sofrem diversas modificações ao longo das etapas de desenvolvimento, implantação e manutenção. A evolução de um software pode ter várias causas: correção de erros, inclusão de novas funcionalidades ou até mesmo, como é o caso de programas orientados a aspecto, transformações estruturais podem fazer parte da semântica do sistema. Apesar de modificações serem comuns, não é tarefa trivial prever como estas afetam o comportamento dos programas, já que os componentes de software normalmente interagem de forma complexa, o que faz com que mesmo pequenas alterações possam introduzir comportamentos indesejados. Transformação de grafos, também conhecida como reescrita de grafos, é um importante paradigma para modelagem e análise de sistemas. Modelos baseados em transformação de grafos, como gramáticas de grafos, permitem uma modelagem ao mesmo tempo intuitiva e com semântica precisa, permitindo a aplicação de técnicas de análise como verificação de modelos e análise de par crítico no estudo do comportamento de sistemas. A teoria por trás de transformação de grafos vem sendo desenvolvida a várias décadas, e atualmente está descrita de uma forma bastante abstrata. Contudo, ainda não possui uma definição natural de reescritas de alta ordem...

Resultados espectrais relacionados com a estrutura dos grafos

Andelic, Milica
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Tese de Doutorado
POR
Relevância na Pesquisa
37.54%
Nesta tese são estabelecidas novas propriedades espectrais de grafos com estruturas específicas, como sejam os grafos separados em cliques e independentes e grafos duplamente separados em independentes, ou ainda grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados em cliques e independentes são estudados, tendo como objectivo limitar o maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor próprio é aplicada para obter alguns majorantes e minorantes do índice do espectro Laplaciano sem sinal dos grafos separados em cliques e independentes bem como sobre o índice dos grafos duplamente separados em independentes. São fornecidos alguns resultados computacionais de modo a obter uma melhor percepção da qualidade desses mesmos extremos. Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma estrela complementar para um valor próprio não-principal $. Além disso, é mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela complementares construímos, em alguns casos, os respectivos grafos maximais. Uma caracterização dos grafos separados em cliques e independentes que envolve o índice e as entradas do vector principal é apresentada tal como um majorante do número da estabilidade dum grafo conexo.; In this thesis new spectral properties of graphs with a specific structure (as split graphs...

Estudio de la constante de hiperbolicidad en grafos

Vilaire, Jean-Marie
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado Formato: application/pdf
SPA
Relevância na Pesquisa
37.52%
Esta tesis se dedica al estudio de los grafos hiperbólicos y está dividida en cuatro capítulos. El primer capítulo es una intoducción a la teoría de grafos y a los espacios hiperbólicos en sentido de Gromov. En los demás capítulos se incluyen los resultados de investigación que hemos conseguido. Aunque se dispone de ejemplos interesantes de espacios hiperbólicos, no existen criterios generales que permitan determinar la hiperbolicidad de un espacio. Por tanto, uno de los problemas más importantes en el estudio de los grafos hiperbólicos es obtener criterios que garanticen si un determinado grafo es hiperbólico o no. Por otra parte, existen numerosos parámetros en teoría de grafos que tienen gran importancia, tales como: el número de vértices, el núumero de aristas, el grado máximo, el grado mínimo, el diámetro, el cuello,... Por tanto, otro problema tan natural como importante es encontrar desigualdades que relacionen alguno de estos parámetros (o varios de ellos simultáneamente) con la constante de hiperbolicidad del grafo, encontrando y clasificando (como es importante en teoría de grafos) aquellos grafos para los que se tenga la igualdad. En esta tesis se demuestra que el estudio de la hiperbolicidad de los grafos se puede reducir al estudio de la hiperbolicidad de grafos más sencillos. En particular...

Hiperbolicidad de grafos en sentido de Gromov

Michel, Junior
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado Formato: application/pdf
SPA
Relevância na Pesquisa
37.5%
Si X es un espacio métrico geodésico y x₁; x₂; x₃ ∈ X, un triángulo geodésico T = {x₁; x₂; x₃} es la unión de tres geodésicas [x₁x₂], [x₂x₃] y [x₃x₁] en X. El espacio X es ∂-hiperbólico (en sentido de Gromov) si cualquier lado del triángulo T está contenido en un ∂-entorno de la unión de otros dos lados, para cada triángulo geodésico T en X, es decir, si para toda permutación {i, j, k} de {1, 2, 3} y para todo u ∈ [xixj] se verifica d(u, [xjxk] ∪ [xixk]). Denotamos por ∂(X) la constante de hiperbolicidad optimal de X, es decir, ∂(X) := inf{∂ 0 : X es ∂-hiperbólico}. Esta tesis se enmarca dentro del estudio de las propiedades de los grafos hiperbólicos de Gromov, y forma parte de un amplio proyecto que involucra a numerosos investigadores de diversas universidades que trabajan en este mismo tema. Los resultados de esta tesis se presentan en dos secciones, en el tercer capítulo. En la primera de ellas relacionamos la constante de hiperbolicidad de un grafo con algunos parámetros del mismo grafo, como el cuello, el número de vértices y el diámetro: en particular, si g denota el cuello (el ínfimo de las longitudes de los ciclos del grafo), probamos que ∂ (G) ≥ g(G)/4 para todo grafo (finito o infinito...

Teoria dos grafos: uma reflexão sobre a sua abordagem no ensino não universitário

Cardoso, Ana Maria Dias Soares
Fonte: Universidade Portucalense Publicador: Universidade Portucalense
Tipo: Dissertação de Mestrado
Publicado em //2009 POR
Relevância na Pesquisa
37.62%
A teoria dos grafos remonta ao século XVIII, quando Euler introduziu as suas ideias básicas para resolver o famoso problema das pontes de KÄonigsberg. No entanto, nas últimas decadas, a teoria dos grafos estabeleceu-se, por direito proprio, como uma importante ferramenta matematica numa grande variedade de áreas do conhecimento e algumas áreas específicas, tais como, investigaçao operacional, engenharia, genetica, sociologia, geografia, ecologia, analise numerica, computaçao paralela, telecomunicacoes e quimica. Aliás, é corrente dizer-se que um grande leque de problemas em diversas ciencias pode ser modelizado por um grafo e resolvido com a teoria dos grafos. Por exemplo, é possivel calcular as diferentes combinaçoes de voos entre duas cidades, determinar se é ou nao possível percorrer todas as ruas de uma cidade sem percorrer a mesma rua duas vezes e determinar o numero de cores necessarias para colorir um mapa. Até à decada de 90 do seculo transacto, a teoria dos grafos era abordada somente no ensino universitario. Com o surgimento de novas disciplinas no ensino secundario, nomeadamente, da disciplina de Matematica Aplicada às Ciencias Sociais, a teoria dos grafos ganha um lugar nos programas sociais; aos alunos do ensino nao universitario é-lhes proporcionado uma abordagem...

Búsqueda rápida de caminos en grafos de alta cardinalidad estáticos y dinámicos

Rivero Espinosa, Jesica
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: info:eu-repo/semantics/bachelorThesis; info:eu-repo/semantics/masterThesis Formato: application/pdf
SPA
Relevância na Pesquisa
37.6%
Los grafos han sido empleados en la resolución de problemas complejos de distinta índole desde su aparición. Para ello, toda la información asociada al dominio debe ser representada mediante nodos y relaciones entre nodos (enlaces), y posteriormente aplicar diversas operaciones sobre el grafo creado. Entre todas ellas, la búsqueda de caminos es una de las más frecuentes y permite resolver problemas de distinta naturaleza. Debido a la frecuencia con la que se resuelven gran cantidad de problemas aplicando búsquedas de caminos, existen multitud de trabajos que han aportado al estado del arte algoritmos para realizar dicha tarea. Sin embargo, debido a la constante aparición de nuevos requisitos a tener en cuenta en los grafos sobre los que se realizan las búsquedas de caminos, siguen surgiendo nuevas propuestas impulsadas por la evolución de las necesidades, que añaden nuevos matices al problema. Entre estas nuevas características, merecen especial atención aquellas relacionadas con el continuo crecimiento de los grafos; el hecho de que tanto la estructura de los mismos como los costes asociados a los nodos y enlaces varían con el tiempo; y la aparición de nuevas topologías derivadas del tamaño de los grafos como es el caso de las Small-World Networks. Además...

O problema da orientação pfaffiana de grafos

Santos, Fábio Andreatta
Fonte: Universidade Federal de Mato Grosso do Sul Publicador: Universidade Federal de Mato Grosso do Sul
Tipo: Dissertação de Mestrado
POR
Relevância na Pesquisa
37.52%
Um circuito C em um grafo G é alternado se existe um emparelhamento perfeito M de G tal que C é M-alternado. Uma orientação das arestas de um grafo G é uma orientação pfaffiana se, ao percorrermos qualquer circuito alternado em algum sentido, encontramos um número ímpar de arestas orientadas neste mesmo sentido, ou seja, todos os circuitos alternados do grafo possuem paridade ímpar. Se um grafo possui uma orientação pfaffiana, então dizemos que ele é pfaffiano. Nem todo grafo é pfaffiano, como por exemplo o grafo de Petersen e o K3;3. Por isso, decidir se um dado grafo possui, ou não, uma orientação pfaffiana é um problema de grande importância, pois, além de estar relacionado com alguns problemas fundamentais na teoria dos grafos, como determinar o número de emparelhamentos perfeitos em um grafo1, são foi resolvido para algumas classes de grafos: grafos planares, grafos bipartidos, grafos quase-bipartidos e grafos sólidos. Neste trabalho, estudaremos a caracterização do problema da orientação pfaffiana de grafos paras as classes de grafos bipartidos e planares. Além disso, estudaremos parte da teoria de grafos cobertos por emparelhamentos para apresentar uma nova demostração de uma caracterização de grafos pfaffianos dada por Lovász e Plummer em [9].; A circuit C in a graph G is alternating if there is a perfect matching M of G such that C is M-alternating. An orientation of the edges of a graph G is Pfaffian if...

Coloração de arestas em grafos indiferença

Flavio de Freitas Stecca
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 12/12/2003 PT
Relevância na Pesquisa
37.57%
Esta dissertação aborda o problema da coloração de arestas restrito aos grafos indiferença. O teorema de Vizing diz que qualquer grafo pode ter suas arestas coloridas com .6 (G) ou .6( G) + 1 cores. Grafos pertencentes à Classe 1 são os grafos cujo índice cromático (n úmero mínimo de cores suficientes para pintar suas arestas) X' é igual a .6 ( G) . Se X' = .6(G) + 1, o grafo pertence à Classe 2. Um grafo é dito overfull se .6(G) l_J < m, onde nem são o número de vértices e o número de arestas, respectivamente. Grafos neighborhood overfull são grafos que têm um vértice de grau máximo cuja vizinhança induz um subgrafo overfull. Grafos indiferença overfull ou neighborhood overfull pertencem à Classe 2. Apresentaremos uma breve compilação de resultados de pesquisas. Dois destes resultados mostram que grafos indiferença com grau máximo ímpar e grafos indiferença reduzidos pertencem à Classe 1, porém o problema ainda está em aberto para um grafo indiferença qualquer. Abordamos o problema criando um modelo de programação linear para coloração de arestas. Implementamos um gerador que nos permitiu gerar grafos indiferença de dife-rentes estruturas. Estes grafos tiveram suas arestas coloridas através de programação linear. Definimos um tipo especial de grafo indiferença denominado grafo indiferença semi-universal. Criamos um método que permite cobrir um grafo indiferença com grafos indiferença semi-universais. Mostramos que resolver o problema para um grafo indife-rença qualquer equivale a estender certas colorações parciais para um grafo indiferença semi-universal qualquer. Reforçamos a conjectura de que todos os grafos indiferença não neighborhood overfull são Classe 1...

Problemas em grafos com poucos P4's em grafos indiferença; Problems on graphs with few P4's and indifference graphs

Vagner Pedrotti
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 19/08/2011 PT
Relevância na Pesquisa
37.63%
Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida...

Determinação de grafos regulares excecionais com recurso a (K, T)-extensões; Determination of regular exceptional graphs by (K, T)-extensions

Magalhães, Inês Monteiro Barbedo de
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Tese de Doutorado
POR
Relevância na Pesquisa
37.57%
Um grafo excecional é um grafo conexo com menor valor próprio não inferior a -2 que não é grafo linha generalizado. Esta tese tem como objetivo apresentar uma nova t´técnica de construção de grafos regulares, com certas propriedades de natureza combinatória e espetral invariantes, e aplicá-la na construção de todos os grafos regulares excecionais. O trabalho encontra-se dividido em duas partes. Na primeira parte descreve- -se a nova t´técnica de construção de grafos regulares pela introdução de conjuntos (κ, τ )-regulares, designada de (κ, τ )-extensão, e define-se uma relação de ordem parcial entre grafos regulares. Mostra-se que a (κ, τ )- extensão de um grafo se reduz à construção de matrizes de incidência de um 1-design combinatório, para a qual se definem propriedades que previnem a construção de grafos isomorfos. Além disso, esta t´técnica permite a construção de grafos regulares com partição equilibrada e apresentam-se algumas propriedades espetrais destes grafos. Na segunda parte ´e feita uma breve descrição das três técnicas conhecidas para a construção dos grafos regulares excecionais. Posteriormente, aplicam-se as (κ, τ )-extensões na construção recursiva do conjunto dos grafos regulares excecionais...

Sobre subclases y variantes de los grafos perfectos

Bonomo, Flavia
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: info:eu-repo/semantics/doctoralThesis; tesis doctoral; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Publicado em //2005 SPA
Relevância na Pesquisa
37.6%
Los grafos perfectos fueron definidos por Claude Berge en 1960. Un grafo G es perfecto cuando para todo subgrafo inducido H de G, el número cromático de H es igual al tamaño de un subgrafo completo máximo de H. Los grafos perfectos son de gran interés desde el punto de vista algoritmo: si bien los problemas de determinar la clique máxima y el número cromático de un grafo son NP-completos, éstos se resuelven en tiempo polinomial para grafos perfectos. Desde entonces, fueron definidas y estudiadas gran cantidad de variantes de los grafos perfectos. Entre ellas, los grafos clique-perfectos. Una clique en un grafo es un subgrafo completo maximal con respecto a la inclusión. Un transversal de las cliques de un grafo G es un subconjunto de vértice que interseca a todas las cliques de G. Un conjunto de cliques independientes es un conjunto de cliques disjuntas dos a dos. Un grafo G es clique-perfecto si el tamaño de un transversal de las cliques mínimo coincide con el de un conjunto de cliques independientes máximo, para cada subgrafo inducido de G. El término "clique-perfecto" fue introducido por Guruswami y Pandu Rangan en 2000, pero la igualdad de esos parámetro fue estudiada previamente por Berge en el contexto de hipergrafos balanceados. En 2002...

Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König; On structural characterizations of graph classes related to perfect graphs and the König property

Safe, Martín Darío
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: info:eu-repo/semantics/doctoralThesis; tesis doctoral; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Publicado em //2011 SPA
Relevância na Pesquisa
37.63%
Un grafo es balanceado si su matriz clique no contiene como submatriz ninguna matriz de incidencia arista-vértice de un ciclo impar. Se conoce una caracterización para estos grafos por subgrafos inducidos prohibidos, pero ninguna que sea por subgrafos inducidos prohibidos minimales. En esta tesis probamos caracterizaciones por subgrafos inducidos prohibidos minimales para los grafos balanceados restringidas a ciertas clases de grafos y mostramos que dentro de algunas de ellas conducen a algoritmos lineales para reconocer el balanceo. Un grafo es clique-perfecto si en cada subgrafo inducido el mínimo número de vértices que intersecan todas las cliques coincide con el máximo número de cliques disjuntas dos a dos. Contrariamente a los grafos perfectos, para estos grafos no se conoce una caracterización por subgrafos inducidos prohibidos ni la complejidad del problema de reconocimiento. En esta tesis caracterizamos los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases. Un grafo tiene la propiedad de Kőnig si el mínimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices. En esta tesis caracterizamos estos grafos por subgrafos prohibidos...

Caracterizaciones estructurales de grafos de intersección; Structural characterizations of intersection graphs

Grippo, Luciano Norberto
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: info:eu-repo/semantics/doctoralThesis; tesis doctoral; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Publicado em //2011 SPA
Relevância na Pesquisa
37.65%
En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos.; In this Thesis we study structural characterizations for six classes of graphs...

Caracterizaciones estructurales de grafos de intersección; Structural characterizations of intersection graphs

Grippo, Luciano Norberto
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: Tesis Doctoral Formato: text; pdf
Publicado em //2011 INGLéS
Relevância na Pesquisa
37.65%
En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos.

Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König; On structural characterizations of graph classes related to perfect graphs and the König property

Safe, Martín Darío
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: Tesis Doctoral Formato: text; pdf
Publicado em //2011 INGLéS
Relevância na Pesquisa
37.63%
Un grafo es balanceado si su matriz clique no contiene como submatriz ninguna matriz de incidencia arista-vértice de un ciclo impar. Se conoce una caracterización para estos grafos por subgrafos inducidos prohibidos, pero ninguna que sea por subgrafos inducidos prohibidos minimales. En esta tesis probamos caracterizaciones por subgrafos inducidos prohibidos minimales para los grafos balanceados restringidas a ciertas clases de grafos y mostramos que dentro de algunas de ellas conducen a algoritmos lineales para reconocer el balanceo. Un grafo es clique-perfecto si en cada subgrafo inducido el mínimo número de vértices que intersecan todas las cliques coincide con el máximo número de cliques disjuntas dos a dos. Contrariamente a los grafos perfectos, para estos grafos no se conoce una caracterización por subgrafos inducidos prohibidos ni la complejidad del problema de reconocimiento. En esta tesis caracterizamos los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases. Un grafo tiene la propiedad de Kőnig si el mínimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices. En esta tesis caracterizamos estos grafos por subgrafos prohibidos...

Sobre subclases y variantes de los grafos perfectos

Bonomo, Flavia
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: Tesis Doctoral Formato: text; pdf
Publicado em //2005 INGLéS
Relevância na Pesquisa
37.61%
Los grafos perfectos fueron definidos por Claude Berge en 1960. Un grafo G es perfecto cuando para todo subgrafo inducido H de G, el número cromático de H es igual al tamaño de un subgrafo completo máximo de H. Los grafos perfectos son de gran interés desde el punto de vista algoritmo: si bien los problemas de determinar la clique máxima y el número cromático de un grafo son NP-completos, éstos se resuelven en tiempo polinomial para grafos perfectos. Desde entonces, fueron definidas y estudiadas gran cantidad de variantes de los grafos perfectos. Entre ellas, los grafos clique-perfectos. Una clique en un grafo es un subgrafo completo maximal con respecto a la inclusión. Un transversal de las cliques de un grafo G es un subconjunto de vértice que interseca a todas las cliques de G. Un conjunto de cliques independientes es un conjunto de cliques disjuntas dos a dos. Un grafo G es clique-perfecto si el tamaño de un transversal de las cliques mínimo coincide con el de un conjunto de cliques independientes máximo, para cada subgrafo inducido de G. El término "clique-perfecto" fue introducido por Guruswami y Pandu Rangan en 2000, pero la igualdad de esos parámetro fue estudiada previamente por Berge en el contexto de hipergrafos balanceados. En 2002...

Sobre grafos intersección de arcos y cuerdas en un círculo

Durán, Guillermo A.
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: Tesis Doctoral Formato: text; pdf
Publicado em //2000 ESPAñOL
Relevância na Pesquisa
37.58%
Los grafos arco-circulares son los grafos intersección de arcos alrededor de un círculo. Presentamos en esta tesis los principales resultados conocidos sobre esta clase y definimos las principales subclases. Mostramos como a partir de la caracterización formulada por Tucker para grafos arco-circular propios surgen nuevas caracterizaciones para esta subclase y deducimos características de las estructuras prohibidas minimales para arco-circulares. Se estudian todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan, excepto en una de ellas que se demuestra que es vacía. Este resultado asegura que dado un grafo arco-circular propio no unitario, si es clique-Helly debe ser arco-circular Helly. Los grafos circulares son los grafos intersección de cuerdas dentro de un círculo. También aquí presentamos una reseña de los resultados más importantes y definimos las principales subclases, demostrando algunas relaciones de inclusión entre ellas. Damos una condición necesaria para que un grafo sea circular Helly y conjeturamos que también es suficiente. De ser correcta esta conjetura tendríamos una caracterización y también un reconocimiento polinomial para esta subclase. Se muestra como a partir de la mencionada caracterización de Tucker para grafos arco-circular propios y de un teorema de caracterización de Bouchet para los circulares surgen estructuras prohibidas minimales para esta clase. Analizamos también todas las posibles intersecciones de las subclases definidas...

Un enfoque algorítmico sobre algunas variantes del problema de coloreo de grafos y el problema de conjunto independiente máximo; An algorithmic approach for some variants of the graph coloring problem and the maximum stable set problem

Koch, Ivo Valerio
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: Tesis Doctoral Formato: text; pdf
Publicado em //2014 08 21 INGLéS
Relevância na Pesquisa
37.56%
En esta Tesis estudiamos variantes del problema de coloreo de grafos para varias familias de grafos, y analizamos el problema del conjunto independiente máximo bajo un enfoque de generación de planos de corte. En el problema del k; i-coloreo, asignamos conjuntos de colores de cardinalidad k a los vértices de un grafo G, de manera que los conjuntos que correspondan a vértices adyacentes en G intersequen en no más de i elementos y la cantidad total de colores usados sea mínima. Esta cantidad mínima recibe el nombre de número k; i-cromático y es denotada por Xik(G). Este parámetro, que generaliza el número cromático X01(G), es tan difícil de trabajar que su valor es desconocido aún para grafos completos. Desarrollamos un algoritmo de orden lineal para el cómputo de Xik para ciclos y generalizamos este resultado a grafos cactus. Adicionalmente, estudiamos la relación entre este problema en grafos completos y un problema abierto clásico de teoría de códigos. Un b-coloreo de un grafo es un coloreo tal que cada clase color admite un vértice adyacente a por lo menos un vértice perteneciente a cada una de las demás clases color. El número b-cromático de un grafo G, denotado como Xb(G), es el máximo número t tal que G admite un b-coloreo con t colores. Describimos un algoritmo polinomial para computar el número b-cromático de la clase de los grafos P4-tidy y estudiamos para esta clase dos propiedades conocidas: la b-continuidad y la b-monotonía. Estudiamos además la versión sobre aristas del b-coloreo y su índice b-cromático asociado. Presentamos cotas para el índice b-cromático del producto directo de grafos y damos resultados generales para varios productos directos de grafos regulares. Introducimos también un modelo sencillo de programación lineal para el b-coloreo de aristas...