10
$\begingroup$

I was asked to read about Graph Theory. First got the book "Graph Theory with Applications" by Bondy and Murty. As a Computer Science student its becoming difficult to read and understand. Then I started reading "Graph Theory-Modeling, Applications and Algorithms" by Agnarsson and Greenlaw. They presented the same topics little bit easier but from a different point of view. I found the definitions are bit different. But they essentially mean the same.

I am looking for some books on Graph Theory for a Computer Science student from a beginner point of view. I am looking for books like "Graph Theory-Modeling, Applications and Algorithms".

$\endgroup$
4
  • 1
    $\begingroup$ Try $\textit{Combinatorics and Graph Theory}$ by Harris, Hirst, and Mossinghoff. It is written for undergraduates. $\endgroup$
    – William
    Apr 19, 2014 at 9:11
  • $\begingroup$ Robin Wilson's book Introduction to Graph Theory is highly readable if I recall correctly. You might also want to have a look at the Schaum's Outline on Graph Theory by Balakrishnan. $\endgroup$
    – Casteels
    Apr 19, 2014 at 9:42
  • 1
    $\begingroup$ I liked Shimon Even's book Graph Algorithms, which may be more directly applicable to your work as a Computer Science student. $\endgroup$
    – MJD
    Apr 19, 2014 at 16:59
  • 1
    $\begingroup$ You have everything [here][1]. I post an answer since $I<50$ reputation. [1]: mathoverflow.net/questions/4836/… $\endgroup$
    – user142182
    Apr 19, 2014 at 17:18

3 Answers 3

Reset to default
11
$\begingroup$

I like Doug West's book called Introduction to Graph Theory. It's a breadth book, covering the basics including cycles, paths, trees, matchings, covers, planarity, and coloring. There are algorithms covered like Dijkstra, Kruskal, Ford-Fulkerson, Bipartite Matching, Huffman Encodings, and the Hungarian algorithm. There is also a lot of relevant theory you will want.

You also get topics like spectral graph theory, random graphs, and matroids if you want to cover them. I like that it has an appendix with a bunch of NP-Completeness proofs as well. Those are a really good reference to have as a CS person.

I come from a CS background but am majoring in math, so I have a healthy appreciation for both. Hopefully this helps.

On a side note- if you come across the Alan Tucker Applied Combinatorics text, you should pass on it. I didn't like it very much. It has good problems, but not very good explanations.

$\endgroup$
0
9
$\begingroup$

  • I liked The Handbook of Graph Theory. I didn't read it all, but I've read the section on min-cut max-flow theorems and Ford-Fulkerson algorithm and it was easy to grasp.

  • Another really good book is Even's: Graph Algorithms, it is rigorous but is written in a very accessible way. The good point in it is that the author writes what he's going to do with the developed concepts, most of the authors let you deduce that alone. For some, it might be a plus.

  • I bought Gould's: Graph Theory, I'm still waiting for it to come, but I've seen the look inside feature on amazon and it seems to be a very complete book on graph theory, it seems to also have a very simple languange.

  • Another really good option, although with more content, is Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. It's a great introduction to the most basic contents of graph theory and the languange is not so hard, there are a lot of good references too.

  • The following book is a little bit odd, it has some parts in which it's clear to understand, but most of the times, the exercises are just too demanding. There's not much problem if you use it without it's exercises. The book is Jungnickel's: Graphs, Networks and Algorithms, It seems to be a good call because you're a student of computer science, because this book has a little discussion about algorithm making and it also presents the algorithms in a readable pseudo-code.

  • I don't know how far you are in your CS course. But at least in my university, the put a lot of emphasis on linear algebra (one is supposed to take this course at the first semester). Then if you have a good background on Linear Algebra, you could use the DaMN Book. Algorithms are illustrated using Sage. The original name of the book is Graph Theory Algorithms. The joke on DaMN book is made by the authors in the mentioned page, it reffers to a particular combination of the initial letters of their names.

  • Even being beastly-sized, Bondy/Murthy's: Graph Theory is a great reading. And at least for some of the topics I studied, it uses almost no linear algebra for it's development. I recommend you to take a look at it.

Tip for studying graphs: Don't study with only one book. It's a good thing to have $3-4$ books, because sometimes, one of the books obscures some points which others help to clear it up. Reading the handbook of graph theory, I had a little trouble understanding the following:

enter image description here

I somehow felt unsafe to assume what was the maing of $E(P)$ and $f_P$ And then, the following text on Graph's, Networks and Algorithms helped me to clear it up:

enter image description here

In the last quote, it was easier to understand that the function takes the flows in the original graph, and uses the agumenting path in the residual graph to change the values of the flow in the original graph.

I had the same problem in the other direction too. Understanding the algorithm of Ford-Fulkerson in the Jungnickel's book was very hard. But in the HGT, it became easy. The only problem I had was with that part in the HGT.

$\endgroup$
1
$\begingroup$

I think "A First Course in Graph Theory by Gary Chartrand" is a great introductory textbook on Graph Theory for any person, no matter what their background is. It is also inexpensive.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .