Grafos

Teoria, Modelos, Algoritmos

Paulo Oswaldo Boaventura Netto

R$ 128,00

Disponível em estoque

Sobre o Livro

ISBN: 9788521206804
Páginas: 314
Formato: 21x28 cm
Ano de Publicação: 2012
Peso: 0.781 kg

Conteúdo

Capítulo 1: Introdução

Capítulo 2: Principais noções
2.1 Definições iniciais 
2.2 Definição geral de grafo e definições acessórias 
2.3 Algumas considerações necessárias
2.4 Esquema e rotulação de um grafo 
2.5 Valoração 
2.6 Igualdade e isomorfismo 
2.7 Partição de grafos 
2.8 Representação de grafos 
2.9 Operações com grafos 
2.10 Relações de adjacência 
2.11 Grafos simétrico, antissimétrico e completo
2.12 Grafo complementar de um grafo 
2.13 Percursos em um grafo 
2.14 Grafo de interseção, grafo adjunto, menor de um grafo
2.15 Grafos de Kneser, grafos-círculo, grafos-grade

Capítulo 3: Conexidade e conectividade
3.1 Discussão preliminar sobre conexidade
3.2 Tipos de conexidade 
3.3 Componentes f-conexas
3.4 Dois resultados sobre f-conexidade
3.5 Grafo reduzido 
3.6 Teoremas sobre conexidade 
3.7 Algoritmos para decomposição por conexidade 
3.8 Vértices peculiares em grafos não fortemente conexos 
3.9 Discussão sucinta sobre aplicações 
3.10 Conectividade e conjuntos de articulação 
3.11 Pontos de articulação e antiarticulação

Capítulo 4: Distância, localização, caminhos
4.1 Conteúdo e importância
4.2 Teorema de Festinger e aplicações 
4.3 Distância em um grafo 
4.4 Centros, medianas, anticentros 
4.5 Algumas generalizações e outras questões
4.6 Resultados relativos a raios e diâmetros 
4.7 Grafos extremais de problemas de diâmetro
4.8 Problemas de caminho mínimo 
4.9 Algoritmos de caminho mínimo 
4.10 O problema do labirinto 
4.11 O problema da exploração total 
4.12 Partição de grafos em percursos

Capítulo 5: Grafos sem circuitos e sem ciclos 
5.1 Grafos sem circuitos 
5.2 O método PERT 
5.3 O grafo potenciais-atividades 
5.4 Outras questões referentes a grafos sem circuitos 
5.5 Grafos sem ciclos: florestas e árvores 
5.6 Outros problemas de árvores parciais 
5.7 Bases de ciclos e de cociclos: coárvores 
5.8 Fatoração em árvores e arboricidade 
5.9 Grafos sem ciclos: arborescências 
5.10 Problemas de enumeração e contagem 
5.11Problemas e resultados correlacionados

Capítulo 6: Alguns problemas de subconjuntos de vértices
6.1 Introdução
6.2 Conjuntos independentes 
6.3 Partição cromática e número cromático 
6.4 Dominância
6.5 Outros critérios para dominância; irredundância
6.6 Aplicações da dominância simples
6.7 Núcleo de um grafo

Capítulo 7: Fluxos em grafos
7.1 Introdução 
7.2 O modelo linear de fluxo 
7.3 O problema do fluxo máximo 
7.4 Temas relacionados à maximização do fluxo
7.5 Fluxos em grafos com limites inferiores quaisquer 
7.6 O problema do fluxo de custo mínimo 
7.7 Fluxo dinâmico ou θ-fluxo 
7.8 Algumas aplicações

Capítulo 8: Acoplamentos
8.1 Introdução 
8.2 O problema do acoplamento máximo 
8.3 Acoplamentos em grafos bipartidos 
8.4 Acoplamentos em grafos quaisquer 
8.5 Uso de técnicas de fluxo 
8.6 O problema do b-acoplamento 
8.7 Existência de um acoplamento perfeito
8.8 Aplicações 
8.9 Alguns resultados

Capítulo 9: Percursos abrangentes
9.1 Introdução 
9.2 Existência de percursos abrangentes para ligações
9.3 O Problema do Carteiro Chinês 
9.4 Problemas hamiltonianos 
9.5 O Problema do Caixeiro-Viajante

Capítulo 10: Grafos planares e temas correlacionados
10.1 Introdução 
10.2 Algumas definições e resultados 
10.3 Caracterização da planaridade 
10.4 Outras questões envolvendo planaridade 
10.5 Grafos planares hamiltonianos 
10.6 Algoritmos para caracterização da planaridade 
10.7 O teorema das quatro cores 
10.8 O problema grau máximo-diâmetro em grafos planares 
10.9 Grafos quaseplanares 
10.10 Menores percursos disjuntos em grafos planares 
10.11 O número de grafos não imersíveis em outras superfícies

Capítulo 11: Extensões do problema de coloração
11.1 Introdução 
11.2 Invariantes de vértices 
11.3 Coloração de arestas 
11.4 Números cromáticos total e geral, outros critérios de coloração 
11.5 Polinômios cromáticos 
11.6 Grafos perfeitos
11.7 O problema da T-coloração

Capítulo 12: Alguns temas selecionados 
12.1 Introdução
12.2 Operações binárias com grafos 
12.3 Introdução à teoria espectral de grafos 
12.4 Indices topológicos 
12.5 Centralidades em grafos 
12.6 Vulnerabilidade em grafos 
12.7 O uso de software investigativo em grafos 
12.8 Problemas de roteamento 
12.9 Traçado de grafos 
12.10 Jogos em grafos 
12.11 A expansão das aplicações 
12.12 As grandes redes

Sinopse

O primeiro resultado do que veio a ser a teoria dos grafos passou um século perdido em meio aos setenta grossos volumes da produção científica de Leonhard Euler. À época, o problema das pontes de Königsberg não passava de uma pequena brincadeira sem nenhum interesse prático.

Hoje em dia, a teoria desenvolvida por Euler está na base das técnicas utilizadas para especificar rotas de atendimento para serviços a domicílio em cidades; além disso, algo da sua produção no campo da geometria está envolvido, através da teoria dos grafos, com os projetos de circuitos integrados, como os dos computadores.

O século XIX viu as primeiras aplicações de grafos, quase ao mesmo tempo na eletricidade e na química. Hoje em dia, eles continuam sendo aplicados a circuitos elétricos e eletrônicos e sua utilidade cresceu extraordinariamente no campo da química, auxiliando na definição de índices cujos valores possam ser associados, através das estruturas das moléculas - que são estruturas de grafo - às propriedades das substâncias correspondentes. Indo mais longe ainda, a bioquímica molecular vem utilizando algoritmos de grafos para estudos como os da estrutura do DNA e da composição das proteínas. Problemas de administração, de transportes, de comunicações e de relacionamento são estudados com o auxílio de grafos.

Os desafios do futuro estão nas grandes redes sem escala, como a Internet, as redes de migração e, provavelmente, o maior de todos os desafios estará no estudo da mais complexa das redes: a rede neural dinâmica do cérebro humano.

O primeiro livro dedicado aos grafos foi publicado há pouco mais de 70 anos: hoje, eles já são centenas. As revistas e os congressos especializados existem por todo o mundo e os trabalhos publicados se contam aos milhares, tanto com motivação teórica como dentro das especialidades que utilizam em suas aplicações os poderosos recursos da teoria dos grafos.

Todo esse potencial, no entanto, não se realiza sem um intenso trabalho, em vista da complexidade dos problemas, tanto do ponto de vista teórico como do computacional. A prova dos teoremas pode apresentar grandes dificuldades, como se observa ao se examinar a trajetória do problema das quatro cores, resolvido computacionalmente - mas ainda não analiticamente - após cerca de um século de tentativas, e a prova analítica do teorema dos grafos perfeitos.

Em nossa visão, tudo isso é algo de apaixonante, capaz de motivar toda uma carreira profissional, tal como o fez com este autor. Não esperamos tanto dos que recorrerem a este livro - mas desejamos que nele encontrem utilidade, bem como algum caminho que lhes traga as respostas para seus problemas que envolvam grafos; e, também, que o considerem agradável de abrir. Ele se destina a um universo diversificado: até o momento, trata-se do único livro-texto publicado no Brasil sobre o assunto e, em vista disso, seu conteúdo envolve interesses de cursos de graduação e de pós-graduação, bem como de pesquisa teórica e aplicada. Esta diversidade traz como consequência que o seu leitor poderá encontrar nele, ao lado dos temas de seu interesse, outros que não atraiam sua atenção. Por este pequeno inconveniente, o autor apresenta suas desculpas.

Ver maisVer menos

Material de Apoio

Depoimentos sobre o livro

Envie seu depoimento

Seja o primeiro a publicar um depoimento sobre o livro!