14 ms·
I don’t understand Graph Theory
- anticnstrctv 9y agoMaybe I'm alone, but I never felt the graph theory pedagogy I experienced was very confusing or boring (I did think this about plenty of CS topics!). There's lots of motivating examples to pull in, and better/clearer diagrams than this in may places. This just seems like a not very lucid description of theory that is very formalized and that many lectures and textbooks deal with.
- doomlaser 9y agobesides data structures, graph theory and its related curricula were my favorite and overall most practical areas of the CS education I received
- dpwm 9y agoWhen I was 16 I changed sixth form[0] following a house move and I was accidentally put onto a maths course that was basically algorithms without computers. I think the name was something like Decision and Discrete. This course started with Zeller's congruence as an example of an algorithm and then moved onto some graph theory and then onto Dijkstra's algorithm. I never got to see what the rest of the course contained, but it really looked like a good course. Sadly I was not able to persuade the person who was in charge to let me continue to take the course. All the people on the course absolutely hated it from the start; thought I was mad to want to do it; would go on to fail it and as a result this was the last year the sixth form would run it. [0] Sixth form is the 16-18 optional education in the UK.
- beojan 9y agoYou're talking about the D1 module, which was considered the easiest maths module at my school, because it doesn't really require much understanding, you just have to learn the material.
- Gormisdomai 9y agoD-maths modules in the UK have changed a lot over the years, seems like they started out pretty legit and got diluted over time. Depends when they took it.
- pertymcpert 9y agoI hated that module. I found it boring because it was just memorising algorithms and applying them. The key aspect of studying algorithms, complexity and analysis of the algorithm itself, was missing.
- arethuza 9y ago"education in the UK" In England and Wales, maybe in NI but definitely not here in Scotland, which has a completely different system.
- jdietrich 9y ago>Sixth form is the 16-18 optional education in the UK. It's only sort-of optional now - since 2015 you're required to remain in education or training until 18, although that includes vocational courses and apprenticeships.
- taoistextremist 9y agoNothing covered in this article is stuff I'd consider very complicated, but I took a class on graph theory and the kinds of algorithms and concepts covered in the second half of that course were much more complex, though the fact that I hadn't taken a modern algebra class probably hurt me with some of those things, not to mention the class was also about the relation to combinatorics which presents much more interesting, though more complicated, problems.
- Scea91 9y agoSome people prefer learning from examples (inductive) while other people prefer learning the theory bottom-up (deductive). This article may be for the first kind of people. Everyone uses both kinds of reasoning but I know I have deeper understanding of the areas that I studied bottom-up. Even if it might have been a bit more difficult and time consuming, because I didn't get to the applicable stuff as fast.
- kbart 9y agoWhy not use mixed approach? I find it works best for me. First, learn by examples to get a broader picture, then learn theory bottom-up to get into details. It's much easier to learn complex theories when you know where it leads and what purpose it serves than building mental model blindly.
- suj1th 9y agoIMO, deductive learning is limiting ( we are limited by the span of our examples), but it has great recall value. Inductive learning is harder to commit to long-term memory; particularly, when learning something which you find scant use for in your day-to-day life. Again, I can see this is not general, and could vary considerably across individuals.
- randomsearch 9y agoI’ve done a few degree-level teaching courses, and what I gathered from them is that the notion of individual learning styles is a bit of a myth. Most people learn best from examples, which makes intuitive sense. Purely theoretical learning does not come easy to most people - that’s why maths is so scary to so many. Given that the learning style myth has been mostly discredited, I also wonder about preferences such as night owl vs morning bird - it seems to me that people learn best in the morning, _unless_ they have poor sleep hygiene. Which would again make totally intuitive sense.
- MooMooMilkParty 9y agoI'm curious about your last statement. I guess I'd be considered a night owl by most people, and certainly have poor sleep hygiene in the eyes of early birds, but I find myself most motivated to do really "intellectual" work about 2-3 hours after dinner. For the record, when I say "intellectual" work I don't specifically mean academic, but more broadly creative. Do you specifically mean something like learning in the classroom setting? Now I'm also curious about the differences in free-form learning (which I guess I'm talking about) vs the more traditional classroom learning. Do you have any insight on this?
- travisjungroth 9y agoFor people who don’t understand graphs, Euler graphs seem like such a weird place to start. There are much more relevant problems (social networks, followers and travel distances) with approachable graphs (undirected, directed, and weighted).
- vinchuco 9y agoThe place I wish I had started at: The Nature of Computation - Moore, Mertens What I got (graduate coursework): Graph Theory - Reinhard Diestel A more encyclopedic treatment (most big results, no proofs): Handbook of Graph Theory - Gross, Yellen
- adrianN 9y agoThe Diestel book is great if you already know Graph Theory. The proofs are exquisitely concise, but it's hard to read because you have to think really hard about the definitions and why they're giving in precisely that way (hint: to make the proofs more concise!).
- gaurav_v 9y agoThe Nature of Computation is really good.
- gilleain 9y agoedit: Never mind - I hadn't read far enough in. He means 'Eulerian graph', I think. As in a graph with an Eularian trail. You know it might be nice for people to get the terminology right if you are writing about this stuff... What do you mean by 'Euler graphs'? As in, the problems described by him such as the bridge problem? I would call anything with vertices and edges an 'Euler graph' as opposed to a 'Cartesian graph' (a chart).
- rowyourboat 9y ago> You know it might be nice for people to get the terminology right if you are writing about this stuff... He specifically mentions in the article that he found both terms and used the one used in the literature he refers to.
- Twisell 9y agoI just lost track at the airbnb example. What is the inherent advantage of using a graph in the context of computing scores over 4million possibilities ? Should’t a Modern sql database be enough? PS : Or maybe we could use a blockchain to be even more modern?
- hodl 9y agoOr a hadoop cluster. Oh I'm showing my age!
- vardanator 9y agoThe point of example is to show that graphs (for Airbnb case - trees) are a good fit. Modern sql database should be enough, but just because it has strong indexing, which is mostly implemented using B-trees, which are again graphs. So Airbnb example takes the reader to balanced binary trees (though it seems long reading).
- twic 9y agoI thought it was odd to treat trees as graphs. They are, but they're different enough that you don't use the same tools on them.
- coldtea 9y agoHmm? Trees are just acyclic and connected graphs in graph theory. Why wouldn't you use the same tools that apply to graphs in general?
- yorwba 9y agoAcyclicity usually makes it possible to come up with a specialized algorithm that works better on trees than an algorithm that needs to handle all possible graphs. For example, many NP-complete problems become fixed-parameter tractable if you fix the tree-width of the graph (essentially, how many nodes you have to bag together until the graph looks like a tree). Because of this, algorithms on trees are often very different from general graph algorithms in practice. You could use the same tools, but it would be unnecessarily slow and/or complex.
- mathgenius 9y agoHere's a pro-tip: "I don't understand XYZ" this is the humble-brag of academia. And the more basic XYZ is, the more points you win. Try the following: "I don't understand 1+1=2." Sit back and enjoy your collaborators as they stare in wonderment at your sage lack of understanding.
- leoc 9y agoWhatever do you mean, Socrates? Surely all men know the meaning of XYZ?
- hopw_roewur_ne 9y agoIt took a bit of work to understand what was going on here though: "From this proposition it will follow, when arithmetical addition has been defined, that 1 + 1 = 2." https://en.wikipedia.org/wiki/Principia_Mathematica#/media/File:Principia_Mathematica_54-43.png https://en.wikipedia.org/wiki/Principia_Mathematica#/media/F...
- opportune 9y agoI don't think good mathematicians confuse rigorous understanding with intuitive understanding as you suggest; rather, they are complements of each other Further reading: https://terrytao.wordpress.com/career-advice/theres-more-to-mathematics-than-rigour-and-proofs/ https://terrytao.wordpress.com/career-advice/theres-more-to-...
- kkleindev 9y agoThat's a great, yet easily forgotten distinction
- nazgul17 9y agoSaying that you intuitively do not understand XYZ often requires intellectual honesty as well as understanding it rigorously, even more so in academia. So saying that you intuitively do not understand XYZ can be used as a signal.
- beefield 9y agoI have noticed that more often than not, when I say "I don't understand XYZ" I actually mean "Are you really, really sure that you understand XYZ, because what you say makes no sense whatsoever"
- cooervo 9y agotoo long
- twic 9y agoHow long did this take to write? It is rather reminiscent of War and Peace, in that it's undoubtedly an impressive work, but there is no way i am going to read it.
- zaphar 9y agoThat's a shame. Really good long form writing is often well worth your time. Although this particular piece had some grammar issues that reduced it's quality but the content was still enjoyable.
- Moodles 9y agoMy MSc dissertation topic was on graph theory. I studied a lot of crazy stuff: things like random trees, hypergraphs and partitions of graphs into other graphs. I remember once this internet company came to campus and was trying to encourage mathematicians to join them. This lady said: "One person has a PhD in graph theory but originally thought she wouldn't be needed here. Yet the internet is a graph!" I was thinking, yeah, sure, a lot of graph data structures and algorithms are pretty useful, but it was hard for me to see how some the niche topics I was studying would really, actually, be useful. Luckily mathematics does tend to to surprise us like that. (Saying that, I am now a cryptographer and don't use much graph theory, or any of the economics and game theory I did in my undergradate :-) Game theory in particular, I am highly skeptical of, but that's another story...)
- dsacco 9y ago> (Saying that, I am now a cryptographer and don't use much graph theory, or any of the economics and game theory I did in my undergradate :-) Game theory in particular, I am highly skeptical of, but that's another story...) You’re a cryptographer and don’t use any game theory? Most cryptographic protocols are, or can be, phrased through game semantics. Game theory is very useful, what are you skeptical about?
- Moodles 9y agoIt is true that you can analyse many cryptographic schemes by modelling them as games. In fact, my PhD was largely focused on this exact topic :-) Our discussion really depends on what we define as “game theory” and “graph theory” I suppose. The game theory I studied in economics (albeit in my undergrad) I'm very skeptical of, though. It was about exact payoffs and rational agents and loads of assumptions that really don't work in real-life. I'd spend time literally analysing optimal strategies in board games. It all seemed kind of pointless. People always said you can apply game theory to political science and wars, but it all seemed like common sense and logic, rather than the specific stuff I was actually studying. I remember solving integral equations to calculate Nash equilibrium bidding strategies in third price bid auctions with perfect information and a uniform distribution of value to buyers. The solutions had a lot of maths, but had no bearing on reality whatsoever. What I studied was never really used to make any actual predictions in the real world. It seemed almost as if they were trying to make this subject mathematical to give it some legitimacy. A lot of it is common sense. One could argue that studying it helps you think logically I guess, but so do lots of things. Ariel Rubinstein is a famous economist and actually one of the founders of game theory and gave an excellent critique of the whole space. He is a lot more eloquent than I. You should listen to him and let me know what you think. https://rwer.wordpress.com/2012/11/05/game-theory-a-critique/ https://rwer.wordpress.com/2012/11/05/game-theory-a-critique...
- estomagordo 9y agoNice work. I stopped reading about 2 volumes in, though.
- andybak 9y agoSmall quibble: > note that we are still dealing with pseudocode He's got a funny idea about pseudocode! This is very timely. I've been writing an app to draw polyhedra and it's slowly been dawning on me that there's a lot more graph theory involved than there is 3D geometry or vector maths.
- OldArrow 9y agoWas expecting this to be pitch for neo4j.
- blattimwind 9y agoIf anyone has trouble with graph theory or other basics of discrete mathematics, then the introductory works of Matoušek and Nešetřil will most likely help them very much.
- addadi 9y agoI must recommend also Sarada Herke series of videos on graph theory. they are excellent. https://www.youtube.com/playlist?list=PLGxuz-nmYlQOiIOriTXMEoGoybUC3Jmrn https://www.youtube.com/playlist?list=PLGxuz-nmYlQOiIOriTXME...
- btown 9y agoSo, if you do have data in an arbitrary graph structure and want to do a search like the Airbnb example - essentially, sort nodes by maximal total flow from a set of starting search nodes - clearly Hopcroft-Karp isn’t appropriate, but is there an algorithm that is good for this use case? The author punts to building indices, but is there a way to express that from a graph theory perspective?
- ozim 9y agoThose disclaimers look like comments on bad code. Dear author you do not have obligation to make such clarifications. I take this blogpost as example how I do not want to write. It is too long and too much information in one piece, Euler to BST with AirBnb to Twitter, and Facebook. With stop on linked lists, arrays and trade-offs between them. Don't even get me started on Sponge Bob. All this targeted at junior developers? I advise author to read: "Nobody Wants to Read Your Sh*t: Why That Is And What You Can Do About It"
- deleted 9y ago[deleted]
- vardanator 9y ago:D noted, thanks. I just hate those part 1, part 2, part N articles, so tried to put all in one. However, done just 40% of the initial plan, so some new looong article will be published sometime in the future.
- felideon 9y agoAnd yet, it is at the top (#2 right now) of HN.
- whorleater 9y agoBecause the HN voting system is a clear and democratic way of expressing value
- agentultra 9y agoGraph theory is amazing. One of my favorite subjects. If you're a liberal-arts kind of person and or have scars from prior experiences with mathematics I recommend, https://www.amazon.com/Introduction-Graph-Theory-Dover-Mathematics/dp/0486678709/ref=zg_bs_13938_1?_encoding=UTF8&psc=1&refRID=5B340WJFHW26XTZVXM54 https://www.amazon.com/Introduction-Graph-Theory-Dover-Mathe...
- andrepd 9y agoI'm just gonna go ahead and say: this is the kind of style that makes me go "yawn, this is boring". Endlessly meandering and circling the subject, stopping every sentence to make an irrelevant digression or an attempt at humour (breaking my concentration in the process), stretching on and on... Yeah, give me a concise text, that goes straight to the subject, and that doesn't attempt to take a conversationalist tone with me as if we were having a beer together, give me that any day. Yes, I understand some people have the opposite view, I'm just trying to day that there are surely a lot of people too that find this kind of style extremely distracting and frustrating. In other words, my favourite textbooks of all time are Landau and Lifschitz :^)
- vardanator 9y agoInteresting notes, thanks. I was struggling with such books that compress a complex idea in a couple of sentences, so I'm always trying to explain as detailed as possible. Though understanding that there is a broad audience who likes the opposite (succinct explanations), I wrote disclaimers to secure me just in case. So, read the disclaimers one more time, that's my only excuse for such long and boring discussions :)
- andrepd 9y agoYes, I have talked to people who much prefer a lighter, lengthier style, so I guess this is a matter of taste. If I may offer a suggestion though, the pictures are very distracting and often don't add to the discussion. Consider either limiting their use, or making them smaller and on the sides of the page.
- vardanator 9y agoSure, will try for the next one. Thanks.
- tmaly 9y agoHave you heard of the Pyramid Principle book? I am working through the book now. I find the method very helpful in structuring how you present ideas in your writing.
- inputcoffee 9y agoI have a graduate degree in computer science and know some graph theory, but I really liked this. I thought it was interesting, reminded me of a lot of theory, and taught me some more. I really appreciated the voice and tone. I am very surprised to see people who did not appreciate it and took the time to write how much they didn't like it. (Which is their right). I am writing this only to let the original author know that there is an audience for this kind of "breezy" explanation.
- vardanator 9y agoThank you very much! I don't really get upset for critics, it helps a lot to produce the next good work (noting previous complains). However, hearing some really positive feedback is always motivating to spend more time on knowledge sharing. Thanks again!
- bhrgunatha 9y agoTeaching is part skill and part craft and like so many other creative areas there are plenty of different styles that can appeal to different personalities and preferences. It's a constant tension and there will always be room for imagination, creativity and even art in teaching. Prime example - http://poignant.guide/ http://poignant.guide/
- lists 9y agoI'm likely the developer that's in your target audience: a self-taught Junior in a feature factory with no mentorship and 'agile' cycles that have you always on the next thing after the other. These types of articles are super helpful in beginning to shore up the foundations. Thanks for the article.
- gtrubetskoy 9y agoFor programmers "understanding" graph theory begins with being able to implement a traversal and knowing how depth-first is different from breadth-first, what is pre-order, in-order or post-order, what role the stack and the queue play in it, and how it can be done recursively or using a loop.
- vardanator 9y agoThanks @signa11 for sharing this.
- interdrift 9y agoThank you for sharing this. I'm doing a master's degree in computing and I think graphs are the most powerful modeling tool in the whole of computer science.
- lkrubner 9y agoI find it strange that the folks on Hacker News sometimes have such strong reactions to the tone of an article, or sometimes just a paragraph in the article. I’ve gotten that too, when articles of mine become popular on HN. I personally liked this article about graph theory, the conversational tone.
- hackermailman 9y agoI didn't understand why at first until I started reading dozens of books and papers suggested here that have precision in their writing, now I too can't stand an overly written article or book. The Art of Computer Programming vol 1 contains an excellent introduction to graph theory where Knuth converts a program flow chart into a graph to discover free subtrees.The dry humor there doesn't try to be too obvious, and every sentence is carefully written for precision.
- lkrubner 9y agoI get that any kind of writing can provoke strong reactions, as some people have strong preferences. And they have a right to those preferences. But I hope we can agree that being vocal about one's preferences is a different kind of activity? Everyday on Hacker News there are dozens of articles that don't interest me, but can you imagine what people would think about me if, in every one of those articles, I posted a note saying that I didn't like the article? Most of us simply skip over the stuff that doesn't interest us. That is clearly the default behavior. Therefore it is interesting why, on certain articles, people do feel the need to comment on the style. Personally, I've been lucky, because the most vocal people have been the people who like my writing. But not always. I wrote a book about startups, and some people loved that it had a lot of humor, whereas others really hated it. At least so far, the one's who hate it write to me privately, whereas the ones who love it have written the reviews on Amazon: https://www.amazon.com/Destroy-Tech-Startup-Easy-Steps/dp/0998997617/#customerReviews https://www.amazon.com/Destroy-Tech-Startup-Easy-Steps/dp/09... I'm lucky, but I'm also curious why this is. As a purely sociological question, why is that sometimes people feel the need to be very vocal with their disapproval, whereas most of the time they keep such disapproval private?
- nukeop 9y agoI don't know if this is common in USA to finish higher education in computer science and not learn about graphs at some point? Even the basics? In Europe most universities that teach computer science have at least one course fully dedicated to graph theory, algorithms for traversal, shortest path finding, cycle detection and so on. I didn't even know it was possible to work professionally as a software developer and not already know all of this.
- the_af 9y agoAnother thing I noticed is the number of articles claiming that "college is overrated" or that "CS is not useful for the real world" and in general downplaying the importance of a formal education, and then... "I don't understand Graph Theory". Yes, not saying the same people claim all these things, but surely there's some connection between deriding a formal CS education and not understanding a prime example of a CS topic like Graph Theory?
- curuinor 9y agoIt's common everywhere software is made that the people who make it don't necessarily have a higher ed degree in computer science. I do, and I was forced to dedicate a course to it, yes
- jasonmaydie 9y agoFor the longest time I couldn't understand electrical theory, until a youtuber explained it very simply... It won't move unless it can see a path to ground, except you make it do all the work while it's attempting to ground. That's all it took for the theory to fall into place.
- baron816 9y agoDon’t worry, it’s just a theory...
- zerr 9y agoUnderstood but forgot. Several times.
- tayo42 9y agoThere is some serious amounts of cynicism and negativity in these comments. The article is an interesting introduction. The style is a little all over the place, but hardly worth closing it over. No one seems to be criticizing the correctness of the content, probably the most important part of a technical article to discuss.
- forgottenpass 9y ago>No one seems to be criticizing the correctness of the content, probably the most important part of a technical article to discuss. shug There's plenty of existing resources designed to learn graph theory. It's not good enough for a new one to simply be correct. If someone doesn't think their presentation of the content is going to be better, why bother? I'd sooner share my discrete math textbook with someone before sending them this link.
- enriquto 9y agoThe best way to understand graph theory is in a continuos setting. When you approximate a linear pde with finite differences, you can write the discrete set of equations as a linear system with sparse matrices. Sparse matrices are just graphs. And the natural matrices associated to this graph (adjacency matrix, incidence matrix, transposed incidence matrix, etc) correspond to the natural linear operators on your space (laplacian, gradient, divergence, etc.).
- camel_Snake 9y agoIf you already understand those other things I find it surprising that you wouldn't already understand graph theory.
- taeric 9y agoWith the top few posts being somewhat negative, I was expecting a bad article. It is longer than I'd care for on a quick read, but it looks solid and I would consider a hardcopy. Especially to share with my kids to help them learn. The added "color" really helps, I think.
- diyseguy 9y agoIf someone wants to present a fresh take on a subject like this, why drag out the same examples that are always used? My eyes glazed over as I observed the bridges of Konigsberg trotted out yet again. Sprinkling curlicues on a tired overused cliche like this will never freshen it up. Can all the authors out there just stop trying to dumb things down for a general audience and just start at the intermediate level? Just skip all the drawn out cliched intros and get on with it. Don't try to cutesify it, it just comes out condescending. This is also why I can't bear to read documentation from Google.
- tyteen4a03 9y agoI really think what this article needs is an editor. From a quick glance I can see quite a bit of info but the way it is presented irks me.