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

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.

Da teoria das organizações às instituições

Neste artigo são passadas em revista algumas das principais teorias da organização empresarial à luz da moderna teoria dos grafos. Analisa-se, em primeiro lugar, a teoria clássica da gestão teorizada por H. Fayol, mostrando-se como ela pode ser revista de acordo com a teoria dos grafos hierárquicos. De seguida, analisa-se o conceito de rede dinâmica, o qual leva a abandonar a teoria neoclássica quer da empresa quer do mercado e a caracterizar as empresas evoluindo nos ambientes das tecnologias da informação. São passados em revista os casos da Cisco Systems e da Microsoft Inc., salientando-se o tipo de grafos que lhes correspondem. É finalmente destacado o papel dos standards em tecnologias da informação, concluindo-se serem necessários mecanismos de regulação institucional em dinâmicas empresariais que tendem a favorecer a emergência de monopólios.

Teoria básica das estruturas conceptuais

As Estruturas Conceptuais são um formalismo de representação de conhecimentos baseado em grafos, os chamados grafos conceptuais. A teoria foi inicialmente desenvolvida por John Sowa há dez anos. desde então, uma comunidade científica cada vez mais ampla tem-na utilizado em muitas áreas de aplicação e propôs várias alterações à teoria original. Também está em desenvolvimento uma implementação estado-da-arte gratuita e, além disso, os grafos conceptuais foram adoptados num padrão ANSI em preparação. Apesar desta actividade não existe de facto uma definição formal, completa, consistente e revista da Teoria das Estruturas Conceptuais. Esta dissertação vem contribuir para essa definição ao estender, refinar e clarificar as noções básicas da teoria. A clarificação dos grafos conceptuais em * grafos sintacticamente correctos, * grafos bem tipados, * grafos ontologicamente correctos, chamados grafos canónicos, * e grafos verdadeiros é a base da clarificação do significado das várias noções e serve de guia às extensões e aos refinamentos introduzidos. As principais extensões foram feitas no sistema de tipos e no esquema de dependências entre vértices de grafos, e o refinamento de quase todos os aspectos da teoria - em particular das regras de formação de grafos canónicos e de regras de inferência para os grafos verdadeiros - inclui o tratamento formal de algumas propostas informais de outros autores.

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.