Libros de fácil lectura sobre Teoría de Grafos

Question

Me pidieron que leyera sobre la Teoría de Grafos. Primero conseguí el libro "Graph Theory with Applications" de Bondy y Murty. Como estudiante de Ciencias de la Computación se me hizo difícil leer y entender. Entonces empecé a leer "Graph Theory-Modeling, Applications and Algorithms" de Agnarsson y Greenlaw. Presentaron los mismos temas un poco más fácil, pero desde un punto de vista diferente. Encontré que las definiciones son un poco diferentes. Pero esencialmente significan lo mismo.

Estoy buscando algunos libros sobre Teoría de Grafos para un estudiante de Informática desde un punto de vista de principiante. Estoy buscando libros como "Teoría de Grafos-Modelado, Aplicaciones y Algoritmos".

Answer 1

Me gusta el libro de Doug West llamado Introducción a la teoría de grafos . Es un libro amplio, que cubre lo básico, incluyendo ciclos, caminos, árboles, emparejamientos, cubiertas, planaridad y coloreado. Se cubren algoritmos como Dijkstra, Kruskal, Ford-Fulkerson, Bipartite Matching, Huffman Encodings, y el algoritmo húngaro. También hay una gran cantidad de teoría relevante que querrá.

También tienes temas como la teoría de grafos espectrales, grafos aleatorios y matroides si quieres cubrirlos. Me gusta que tenga un apéndice con un montón de pruebas de NP-Completitud también. Son una muy buena referencia para tener como una persona de CS.

Vengo de una formación en ciencias de la computación, pero me estoy especializando en matemáticas, por lo que tengo un sano aprecio por ambas. Espero que esto ayude.

Por otro lado, si te encuentras con el Alan Tucker Combinatoria aplicada texto, deberías pasar de él. No me ha gustado mucho. Tiene buenos problemas, pero no muy buenas explicaciones.

Answer 2

• Me gustó Manual de Teoría de Grafos . No lo he leído todo, pero he leído la sección sobre los teoremas min-cut max-flow y el algoritmo Ford-Fulkerson y ha sido fácil de entender.

• Otro libro realmente bueno es Incluso: Algoritmos gráficos Es riguroso, pero está escrito de forma muy accesible. El punto bueno en él es que el autor escribe lo que va a hacer con los conceptos desarrollados, la mayoría de los autores te dejan deducir eso solo. Para algunos puede ser una ventaja.

• He comprado Gould's: Teoría de los gráficos Todavía estoy esperando que llegue, pero he visto el mira en el interior en amazon y parece ser un libro muy completo sobre teoría de grafos, además parece tener un lenguaje muy sencillo.

• Otra opción muy buena, aunque con más contenido, es Harris/Hirst/Mossinghoff's: Combinatoria y teoría de grafos . Es una gran introducción a los contenidos más básicos de la teoría de grafos y el lenguaje no es tan difícil, hay un montón de buenas referencias también.

• El siguiente libro es un poco impar, tiene algunas partes en las que es claro de entender, pero la mayoría de las veces, los ejercicios son demasiado exigentes. No hay mucho problema si lo usas sin sus ejercicios. El libro es Jungnickel's: Grafos, redes y algoritmos Parece ser una buena opción si eres un estudiante de informática, porque este libro tiene una pequeña discusión sobre la creación de algoritmos y también presenta los algoritmos en un pseudocódigo legible.

• No sé hasta qué punto estás en tu curso de CS. Pero al menos en mi universidad, se pone mucho énfasis en el álgebra lineal (se supone que uno debe tomar este curso en el primer semestre). Entonces, si tienes una buena base de álgebra lineal, podrías usar el Libro DaMN . Los algoritmos se ilustran con Sage. El nombre original del libro es Algoritmos de la teoría de grafos . El chiste de Libro DaMN es hecha por los autores en la página mencionada, se refiere a una combinación particular de las letras iniciales de sus nombres.

• Incluso teniendo un tamaño bestial, Bondy/Murthy's: Teoría de Grafos es una gran lectura. Y al menos para algunos de los temas que estudié, casi no utiliza álgebra lineal para su desarrollo. Te recomiendo que le eches un vistazo.

Consejo para estudiar los gráficos : No estudies con un solo libro. Es bueno tener $3-4$ libros, porque a veces, uno de los libros oscurece algunos puntos que otros ayudan a aclarar. Leyendo el manual de teoría de grafos, me costó un poco entender lo siguiente:

De alguna manera me sentí inseguro al asumir lo que era la maing de $E(P)$ y $f_P$ Y a continuación, el siguiente texto sobre Gráficos, redes y algoritmos me ayudó a aclararlo:

En la última cita, era más fácil entender que la función toma los flujos en el gráfico original, y utiliza la ruta de agumentación en el gráfico residual para cambiar los valores del flujo en el gráfico original.

También tuve el mismo problema en la otra dirección. Entender el algoritmo de Ford-Fulkerson en el libro de Jungnickel fue muy difícil. Pero en el HGT se convirtió en algo fácil. El único problema que tuve fue con esa parte en la HGT .

Answer 3

Creo que "A First Course in Graph Theory", de Gary Chartrand, es un gran libro de texto de introducción a la teoría de grafos para cualquier persona, independientemente de su formación. Además, es barato.