A free graph theory book by David Joyner, Minh Van Nguyen, and Nathann Cohen

http://code.google.com/p/graph-theory-algorithms-book/

by mononcqc • 16 years ago

42 11 16 years ago

code.google.com

ableal• 16 years ago

Looks nice. I went into the tarball, looking for the Sage code snippets (they seem to be only inline in the Tex files). Then, besides the possibly redundant .hg dir, I noticed there were no image files for the figures. Those are also inline, with "{tikzpicture}"

Seems to be a fairly recent thing. Found this 2006 paper: http://www.tug.org/TUGboat/Articles/tb28-1/tb88mertz.pdf

P.S. This seems good enough to fetch all the Sage listings:

    sed -e '/begin.lstlisting/,/end.lstlisting/p' -e d *.tex

(Just in case it's handy for someone else. I always forget how 'sed' ranges work.)

P.P.S. The PGF/TikZ graphics for TeX seem to have been first released in 2005: http://sourceforge.net/projects/pgf/ . These things sneak up on you when you are not looking ... Google even tells me there's an "Inkscape extension for exporting SVG paths as TikZ code"

ximeng• 16 years ago

This is the same book as the one mentioned in

http://news.ycombinator.com/item?id=1203937

mononcqc2• 16 years ago

Ah, my bad - hadn't seen that one and it (obviously) didn't get picked up as the same link.

gcb• 16 years ago

finally. A book where i can change the style and tex it in a way i can just scroll down on my cell phone screen. Instead of left-right for every damn line.

Damn {pdf,ps}!

anatoly• 16 years ago

I applaud the effort, yet deplore the writing. I looked at the first few pages and was dismayed. This isn't a book I would recommend to anyone with no knowledge of graph theory who needs to pick it up.

The authors make no effort to connect to someone who either doesn't have the math background, or forgot it since they did their math courses in college X years ago. Look at the very first sentences: they intimidate almost willfully. Before we're ever told what a graph is, we're told that it's very hard to define and there are "directed graphs, weighted graphs, multigraphs, simple graphs and so on". Why? What possible benefit is there of saying this except to intimidate? I don't yet know what a graph is - or probably I do intuitively but not exactly. I'm not going to remember all these words!

Then "we start by calling a "graph" what some would call an "unweighted, undirected graph w/o multiple edges" ". Again, why? What's wrong with saying this five pages on, after you explain something about direction, multiple edges, maybe weights? The tone seems almost hostile in its dryness.

Then the definition itself is a perfect specimen of a definition aimed solely at a professional mathematician, who is almost never the intended audience of this book (I assume). An ordered pair of sets? Why? Suppose that I remember well what an ordered pair of sets is; if I'm not a mathematician, I almost certainly don't have the intuition that it's just a shortcut way of specifying "V and E". There's no important reason to define a graph as an ordered pair; it's just a formalistic convention. You're not going to be writing out proofs in ZFC about graphs. Even the Sage examples in the book don't follow the (V,E) notation. Why not just say something like "a graph is defined by a set of vertices V and a set of nodes E, where each node in E connects two vertices in V together"? And immediately follow up with a simple example/picture? And then, after the image is clear to the reader and they understand what it is that you want to model mathematically, then talk about formal ways of representing it, and maybe, if you really want to use it, remind the reader what a cartesian product is, and so on.

When you say "Elements of V are called _vertices_, or _nodes_, and elements of E are called _edges_, or _arcs_", why not add "equivalently" after the "or"-s? Again, someone who last read a formal definition of this kind X years ago - or never - is not going to immediately understand that you're just introducing synonyms. They're gonna go "huh? so when is it vertices and when is it nodes?" at least for a few seconds. Why do that?

In fact, I would say that any reader who's at home with the language and the meaning of this definition will be a reader who definitely already knows what an undirected graph is, formally. In other words, someone who needs this definition will almost certainly have to struggle to understand it. This is the opposite of what you want from a definition.

And all that - just on the first page!

mononcqc2• 16 years ago

I found myself having no problem reading it, knowing bits of set theory I had taught myself beforehand, but I have to admit I would have been confused otherwise.

Given the authors have the book open-sourced and that this looks like it's still a draft, it might be a good idea to forward your criticism to the authors. I'm sure they'd appreciate it.

zitterbewegung• 16 years ago

It looks like the book is still in beta and currently being written.

roundsquare2• 16 years ago

I don't entirely agree. This book seems to be targeted for an undergraduate graph theory class. If thats the case, these definitions are just fine.

dusklight• 16 years ago

Shouldn't this have been implemented as a wiki?

abbetts• 16 years ago

Its fine. Downloaded the pdf. Its straightforward. Good examples. The topic of graphs is so interesting. Its more fun, as you read, to think about how this can describe real world networks like facebook friends, traffic patterns on a gmap, internet routers, world trade patterns.

roundsquare2• 16 years ago

As a note, its still being written. The later chapters are not even written at all, they just have notes of topics to be covered.

A free graph theory book by David Joyner, Minh Van Nguyen, and Nathann Cohen

Related Stories