Texto padrão ou superior na teoria de gráficos aplicados

8

Estou procurando um texto de referência sobre teoria de grafos aplicada e algoritmos de grafos. Existe um texto padrão usado na maioria dos programas de ciência da computação? Caso contrário, quais são os textos mais respeitados no campo? Eu tenho Cormen et al.

JEHR
fonte
Em quais aplicativos você está interessado? Aplicações algorítmicas?
A.Schulz
Estou interessado em gráficos direcionados, mas quero um texto definitivo, se houver algo assim. Pensei (esperava) que houvesse um texto dedicado que abordasse teoria, história e aplicações. Obrigado por responder.
JEHR
3
Pesquisando na Amazon por "teoria dos grafos aplicados" produz vários resultados. Sugiro que você comece por aí (ou faça uma pesquisa semelhante em outro lugar), vá à sua biblioteca e procure os candidatos mais promissores. Compre o que você achar mais acessível ou resp. ajustando suas necessidades. Nem todo livro ajuda a todos, isso é um assunto muito específico para cada pessoa.
Raphael
1
Eu procurei na Amazon antes de perguntar aqui. Eu pensei que isso seria óbvio. Portanto, vim aqui para ver se havia um texto definitivo para o tópico que é amplamente usado em programas de CS (veja minha pergunta original).
JEHR
1
Na minha experiência, um "texto definitivo" quase nunca existe, e mais ainda na ciência da computação (um campo jovem). Livros diferentes atendem a diferentes públicos e preferências diferentes, tanto em termos de seleção e apresentação de conteúdo.
Raphael

Respostas:

3

Para dígrafos em particular, há os de Band-Jensen e Gutin "Digrafos: Teoria, Algoritmos e Aplicações" . Abrange bastante material.

A primeira edição é gratuita para download agora que a segunda edição está lançada (há um link para o pdf em sua página). Obviamente, se você tiver acesso a uma conta Springerlink, poderá obter a segunda edição!

Além de ser livre, embora não tenha certeza de sua popularidade (especialmente considerando que é "relativamente" jovem), é um tomo pesado, com ampla cobertura do básico a tópicos bastante avançados e de perspectivas práticas e teóricas.

A outra vantagem é que é um dos poucos (talvez apenas?) Textos de cobertura completa especificamente em dígrafos, em vez de ser um livro geral de teoria de grafos com material sobre dígitos.

Luke Mathieson
fonte
Obrigado! Grátis é sempre muito bom. Parece que cobre muito bem meu interesse principal (gráficos direcionados)!
JEHR 26/07/12
3
À luz de uma discussão em andamento sobre o Meta , encorajo você a tentar melhorar essa resposta, fornecendo evidências de que este texto, em particular, é sua recomendação. Que evidência você tem para sugerir que é popular ou amplamente utilizado? Que evidência você tem de que é respeitada? Observe que ainda não existe uma política sobre "perguntas da lista", mas estou pessoalmente (não oficialmente) curioso para ver quanta justificativa as pessoas podem fornecer.
Patrick87
Luke, fiz uma revisão limitada do livro que você sugeriu e é o melhor livro sobre gráficos direcionados que já vi. Em mais de 700 páginas, é bastante robusto. Apenas lendo a introdução e olhando para os tópicos que posso dizer é o que eu estava procurando-- e, é grátis !! No meu estágio de aprendizado, isso é suficientemente definitivo para minhas necessidades. Vou levar um ano para superar isso. Obrigado por uma ótima sugestão.
26412 JEHR
5

Eu daria uma olhada no livro gratuito de Bondy e Murty: Graph Theory with Applications . Este livro é menos algorítmico e mais teórico de gráficos do que outros recursos recomendados aqui. Há também uma versão mais recente do livro , que não está disponível gratuitamente na rede, mas é extremamente bem escrita e com notação atualizada. Em comparação com outros livros gratuitos sobre teoria dos grafos (como por exemplo Diestel ), Bondy / Murty usa uma abordagem menos formal para provar e explicar a teoria.

A razão pela qual eu a usei é porque é o livro-texto principal do curso de Teoria dos Gráficos da Universidade Técnica da Dinamarca, ministrado por Carsten Thomassen , no qual sou professor assistente há 2 anos.

utdiscant
fonte
Uau, outro texto livre que parece muito bom! Obrigado por esta ótima sugestão!
26412 JEHR
2
À luz de uma discussão em andamento sobre o Meta , encorajo você a tentar melhorar essa resposta, fornecendo evidências de que este texto, em particular, é sua recomendação. Que evidência você tem para sugerir que é popular ou amplamente utilizado? Que evidência você tem de que é respeitada? Observe que ainda não existe uma política sobre "perguntas da lista", mas estou pessoalmente (não oficialmente) curioso para ver quanta justificativa as pessoas podem fornecer.
Patrick87
Atualizei minha resposta com algumas justificativas.
27412 utdiscant
3

Sempre existe a Teoria Algorítmica de Gráficos, que abrange algoritmos de grafos, estruturas de dados, percursos e vários outros tópicos. Se não tem o que você está procurando, pelo menos você não está perdendo nada.

alto
fonte
Obrigado, nunca ouvi falar disso antes. Vou adicioná-lo à minha biblioteca. Parece que não há um texto definitivo amplamente utilizado, portanto, esse pode ser um bom achado.
JEHR
Muito obrigado, por este ponteiro. Eu não estava ciente deste livro. Parece muito bom e tem muitos exercícios! E é grátis!
A.Schulz
1
À luz de uma discussão em andamento sobre o Meta , encorajo você a tentar melhorar essa resposta, fornecendo evidências de que este texto, em particular, é sua recomendação. Que evidência você tem para sugerir que é popular ou amplamente utilizado? Que evidência você tem de que é respeitada? Observe que ainda não existe uma política sobre "perguntas da lista", mas estou pessoalmente (não oficialmente) curioso para ver quanta justificativa as pessoas podem fornecer.
Patrick87
3

Dê uma olhada na Teoria dos grafos algorítmicos (não gratuitos) de Alan Gibbons. É antigo, mas amplamente utilizado em CS, possui uma abordagem computacional, mas também cobre a teoria. Em cerca de 250 páginas, não é muito intimidador e é bem respeitado.

ncke
fonte
2
À luz de uma discussão em andamento sobre o Meta , encorajo você a tentar melhorar essa resposta, fornecendo evidências de que este texto, em particular, é sua recomendação. Que evidência você tem para sugerir que é popular ou amplamente utilizado? Que evidência você tem de que é respeitada? Observe que ainda não existe uma política sobre "perguntas da lista", mas estou pessoalmente (não oficialmente) curioso para ver quanta justificativa as pessoas podem fornecer.
Patrick87
2

Existe o livro "Gerenciamento e mineração de dados gráficos" de Charu C. Aggarwal.

Ele contém (entre outros):

  • Mineração de Gráfico: Leis e Geradores
  • Gerenciamento e mineração de dados de gráficos
  • Indexação de gráficos
  • Consultas de acessibilidade do gráfico
  • Correspondência de gráfico
  • Classificação do Gráfico

Como o título sugere, ele se concentra em dados gráficos e algoritmos para esse tipo de dado. Não sei se é isso que você está procurando, mas posso realmente recomendar este livro:

Gerenciamento e mineração de dados gráficos

EDIT: Como um comentário pediu "evidências" para a relevância da minha resposta, gostaria de salientar o seguinte:

  • Charu Aggarwal é uma das luzes orientadoras no campo da mineração de dados ( 20 principais autores ).
  • O livro é muito bem escrito e fácil de entender, mesmo com pouco conhecimento prévio.
  • Há uma revisão deste livro da ACM indicando uma recomodação da leitura.
  • E finalmente: eu gosto: D

fonte
2
À luz de uma discussão em andamento sobre o Meta , encorajo você a tentar melhorar essa resposta, fornecendo evidências de que este texto, em particular, é sua recomendação. Que evidência você tem para sugerir que é popular ou amplamente utilizado? Que evidência você tem de que é respeitada? Observe que ainda não existe uma política sobre "perguntas da lista", mas estou pessoalmente (não oficialmente) curioso para ver quanta justificativa as pessoas podem fornecer.
Patrick87
Espero poder esclarecer por que acho que este livro é relevante.