ISBN: 9788521206804
Páginas: 314
Formato: 21x28 cm
Ano de Publicação: 2012
Peso: 0.781 kg
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
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.
Seja o primeiro a publicar um depoimento sobre o livro!
