Teoria dos Grafos

A videoaula conceitua a teoria dos grafos, que oferece a base de estruturas de representação para diversos problemas como listas, árvores, pilhas, filas, e outras. Destaca também a adjacência, laços e arestas múltiplas, o grau de um vértice, a notação, os subgrafos, os grafos isomorfos, o passeio e caminho, e, por fim, os grafos cíclicos e acíclicos.

Teoria dos grafos e suas aplicações

Pós-graduação em Matemática Universitária - IGCE

Um estudo introdutório da Teoria de Grafos através de matrizes

Pós-graduação em Matemática em Rede Nacional - IBILCE

Resultados espectrais relacionados com a estrutura dos grafos

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.

Grafos para todos

Dissertação de Mestrado, Matemática, Especialização em Matemática para o Ensino, Faculdade de Ciências e Tecnologia, Universidade do Algarve, 2007

Grafos internos e multirrelações como "spans" : propriedades e composicionalidade

Um span em uma categoria é um par ordenado de morfismos dessa categoria, ambos com origem num mesmo objeto. O destino do primeiro morfismo é a origem do span e o destino do segundo morfismo é o destino do span. Spans, embora sejam uma estrutura bastante simples numa categoria e tenham uma definição também bastante simples, são versáteis, pois, com especializações sutis apresentadas aqui, são capazes de representar outras estruturas, tais como as tratadas nesses trabalho: relações binárias, multirrelações binárias, grafos e, em conjunto com um morfismo adicional, sistemas de transições etiquetadas (LTS). Permitem ainda, como proposto nesse trabalho, definir de forma também simples, redes de Petri como sendo um endospan em uma categoria. Mostra-se que a composição de spans aplicada a essas estruturas é capaz de expresar a composição de multirrelações — mas não de relações —, uma composição de grafos cujo grafo resultante indica caminhos em que cada parte é uma aresta de um dos grafos operados, uma composição de LTS cujo LTS resultante apresenta transações que podem ser compostas por transições de diferentes LTS e uma composição de redes de Petri cujo resultado também apresenta transações compostas por transições que podem ser realizadas em redes de Petri distintas. Mostra-se algumas propriedades dessas composições, bem como suas provas. Como verificar propriedades de relações e de grafos através de spans também é proposto.

Mundos pequenos, produção acadêmica e grafos de colaboração: um estudo de caso dos Enanpads

Utilizando a base de dados dos trabalhos publicados nos Enanpads realizados em 2002-04, este artigo focaliza a área de administração da informação para realizar um estudo exploratório sobre a formação de padrões nas estruturas de disseminação do conhecimento acadêmico no Brasil, apoiado nos conceitos oriundos da análise das redes sociais e conjugados com a base proveniente da teoria dos grafos e em recursos computacionais. Procurou-se mapear os fluxos de informações que possibilitam as trocas de conhecimento através das ligações existentes no meio acadêmico. Os resultados indicam a necessidade de ampliar e estreitar os laços entre os autores, notadamente os que possuem algum grau de centralidade local, no intuito de obter o fortalecimento das instituições de ensino, de forma a quebrar as resistências à produção conjunta entre elas, em detrimento do padrão de reprodução endógena detectado.

Avaliando a percepção dos agentes da teoria do seletorado através de processamento de linguagem natural

Nos últimos anos, a relevância da Teoria dos Grafos na descrição da rela ção entre indiví duos cresceu signifi cativamente, contribuindo para a ascensão do fenômeno das redes sociais. Sua importância tem permitido a explora ção polí tico-econômica de informa ções escondidas em sua estrutura. Assumindo que um parlamentar maximiza sua utilidade ao fortalecer o seu partido e o estado que representa, construímos uma rede política baseada no Congresso Brasileiro, o que permite a identificação de elementos da Teoria do Seletorado. Através de técnicas de Processamento de Linguagem Natural aplicadas à diferentes fontes de notícia, é possível atualizar a rede de forma a identificar alterações na estrutura de poder do sistema político brasileiro.

Grafos Eulerianos

A videoaula traz o conceito de grafo euleriano, aquele em que é possível encontrar um passeio que percorre todos os vértices sem passar duas vezes pela mesma aresta e retorna ao ponto de início. Destaca a trilha euleriana, sendo esta um passeio em um grafo G que atravessa cada aresta exatamente uma vez. Por fim, menciona o tour euleriano, este sendo uma trilha euleriana que começa e termina no mesmo vértice, e o grafo euleriano, um grafo com um tour euleriano.

GRAFOS coloração, planaridade e "Matching"

A matemÆtica discreta Ø um dos ramos mais antigos da matemÆtica. Nos tempos mais recentes sofreu grandes avanos em especial na teoria dos grafos, a qual tornou-se numa poderosa ferramenta de anÆlise para entender e dar soluªo a vÆrios tipos de problemas complexos. O objectivo deste trabalho Ø contribuir para a obtenªo de possveis relaıes entre assuntos que partida poderamos pensar que sªo dspares (quando na realidade nªo o sªo), como coloraªo, planaridade e a existŒncia de matching em grafos. Esta dissertaªo Ø um trabalho de natureza reexiva, sobre a teoria dos grafos onde a ideia principal passa por questionarmos e discutirmos alguns temas pertinentes, deniıes e teoremas relacionando sempre com a planaridade dos grafos. DesenvolveremosumraciocnioecriaremosargumentosquefundamentemaexistŒncia de uma relaªo entre este tema e a coloraªo de grafos e a existŒncia de matching em grafos, utilizando exemplos e estabelecendo relaıes de causa e consequŒncia, deduzindo assim as respetivas conclusıes. Por vezes, os grafos nªo planares podem conter um aspeto visual um pouco complexo, devido aos vÆrios cruzamentos entre as suas arestas, originando assim um certo desencorajamento em utilizÆ-los como ferramenta para a soluªo de vÆrios problemas, quer sejam bÆsicos do quotidiano, ou mais complexos das mais vastas Æreas ligadas investigaªo. Um dos propsitos deste trabalho passa por desmisticar esta ideia e provar que existem muitas deniıes, propriedades, teoremas e algoritmos que podem ser aplicados em qualquer tipo de grafos, independentement da sua planaridade.

Modelagem matemática e aplicações do problema de coloração em grafos

Pós-graduação em Matemática - IBILCE

Grafos em superfícies

Pós-graduação em Matemática Universitária - IGCE

GRAFOS coloração, planaridade e "Matching"

A matemÆtica discreta Ø um dos ramos mais antigos da matemÆtica. Nos tempos mais recentes sofreu grandes avanos em especial na teoria dos grafos, a qual tornou-se numa poderosa ferramenta de anÆlise para entender e dar soluªo a vÆrios tipos de problemas complexos. O objectivo deste trabalho Ø contribuir para a obtenªo de possveis relaıes entre assuntos que partida poderamos pensar que sªo dspares (quando na realidade nªo o sªo), como coloraªo, planaridade e a existŒncia de matching em grafos. Esta dissertaªo Ø um trabalho de natureza reexiva, sobre a teoria dos grafos onde a ideia principal passa por questionarmos e discutirmos alguns temas pertinentes, deniıes e teoremas relacionando sempre com a planaridade dos grafos. DesenvolveremosumraciocnioecriaremosargumentosquefundamentemaexistŒncia de uma relaªo entre este tema e a coloraªo de grafos e a existŒncia de matching em grafos, utilizando exemplos e estabelecendo relaıes de causa e consequŒncia, deduzindo assim as respetivas conclusıes. Por vezes, os grafos nªo planares podem conter um aspeto visual um pouco complexo, devido aos vÆrios cruzamentos entre as suas arestas, originando assim um certo desencorajamento em utilizÆ-los como ferramenta para a soluªo de vÆrios problemas, quer sejam bÆsicos do quotidiano, ou mais complexos das mais vastas Æreas ligadas investigaªo. Um dos propsitos deste trabalho passa por desmisticar esta ideia e provar que existem muitas deniıes, propriedades, teoremas e algoritmos que podem ser aplicados em qualquer tipo de grafos, independentement da sua planaridade.

Mapeamento de difusão no reconhecimento e reconstrução de sinais

Em muitas representações de objetos ou sistemas físicos se faz necessário a utilização de técnicas de redução de dimensionalidade que possibilitam a análise dos dados em baixas dimensões, capturando os parâmetros essenciais associados ao problema. No contexto de aprendizagem de máquina esta redução se destina primordialmente à clusterização, reconhecimento e reconstrução de sinais. Esta tese faz uma análise meticulosa destes tópicos e suas conexões que se encontram em verdadeira ebulição na literatura, sendo o mapeamento de difusão o foco principal deste trabalho. Tal método é construído a partir de um grafo onde os vértices são os sinais (dados do problema) e o peso das arestas é estabelecido a partir do núcleo gaussiano da equação do calor. Além disso, um processo de Markov é estabelecido o que permite a visualização do problema em diferentes escalas conforme variação de um determinado parâmetro t: Um outro parâmetro de escala, Є, para o núcleo gaussiano é avaliado com cuidado relacionando-o com a dinâmica de Markov de forma a poder aprender a variedade que eventualmente seja o suporte do dados. Nesta tese é proposto o reconhecimento de imagens digitais envolvendo transformações de rotação e variação de iluminação. Também o problema da reconstrução de sinais é atacado com a proposta de pré-imagem utilizando-se da otimização de uma função custo com um parâmetro regularizador, γ, que leva em conta também o conjunto de dados iniciais.

Formulação teórica dos fundamentos da otimização global topográfica com análise de desempenho e aplicações à estabilidade de fases de misturas termodinâmicas

Métodos de otimização que utilizam condições de otimalidade de primeira e/ou segunda ordem são conhecidos por serem eficientes. Comumente, esses métodos iterativos são desenvolvidos e analisados à luz da análise matemática do espaço euclidiano n-dimensional, cuja natureza é de caráter local. Consequentemente, esses métodos levam a algoritmos iterativos que executam apenas as buscas locais. Assim, a aplicação de tais algoritmos para o cálculo de minimizadores globais de uma função não linear,especialmente não-convexas e multimodais, depende fortemente da localização dos pontos de partida. O método de Otimização Global Topográfico é um algoritmo de agrupamento, que utiliza uma abordagem baseada em conceitos elementares da teoria dos grafos, a fim de gerar bons pontos de partida para os métodos de busca local, a partir de pontos distribuídos de modo uniforme no interior da região viável. Este trabalho tem dois objetivos. O primeiro é realizar uma nova abordagem sobre método de Otimização Global Topográfica, onde, pela primeira vez, seus fundamentos são formalmente descritos e suas propriedades básicas são matematicamente comprovadas. Neste contexto, propõe-se uma fórmula semi-empírica para calcular o parâmetro chave deste algoritmo de agrupamento, e, usando um método robusto e eficiente de direções viáveis por pontos-interiores, estendemos o uso do método de Otimização Global Topográfica a problemas com restrições de desigualdade. O segundo objetivo é a aplicação deste método para a análise de estabilidade de fase em misturas termodinâmicas,o qual consiste em determinar se uma dada mistura se apresenta em uma ou mais fases. A solução deste problema de otimização global é necessária para o cálculo do equilíbrio de fases, que é um problema de grande importância em processos da engenharia, como, por exemplo, na separação por destilação, em processos de extração e simulação da recuperação terciária de petróleo, entre outros. Além disso, afim de ter uma avaliação inicial do potencial dessa técnica, primeiro vamos resolver 70 problemas testes, e então comparar o desempenho do método proposto aqui com o solver MIDACO, um poderoso software recentemente introduzido no campo da otimização global.