15+ years ago as an undergraduate I was interested in graphs. Manos then suggested that I should read Christos‘ PhD thesis. Then came work. Then came this paper. Then came even more work. I forgot about graphs. My interest was renewed after spending family vacations with a theorist’s family. Aris presented me with a challenge, while this fall, this man taught me the foundations from a non-CS perspective.
In the words of Steve Yegge:
“Graphs are, like, really really important. More than you think. Even if you already think they’re important, it’s probably more than you think.”
Notice the “really really important” part. For it is not “really2 important”; rather it is more of “reallyn important” (for n >> 2). Go down to your library and read Bela Bollobas’ “Modern Graph Theory” (I found its predecessor “Graph Theory – An Introductory Course”) or even Reinhard Diestel’s “Graph Theory” which is also available online*. For those who read Greek, here is a quick introduction (definitions and theorems but no proofs): Εφαρμογές Θεωρίας Γραφημάτων.
In an era when (almost) everyone seems to be talking about the social graph, or applications that make use of it, you need the mathematical background. If you have an idea that builds on social networks it is almost inevitable that its development and implementation will make use of theorems or more general results of graph theory. So, since you will have to deal with it, why not be prepared? Or even if you have devised a graph data model that can kill the RDBMS+, why not use the theory to support the argument?
[*] – Originally I wanted to write a simple “post-it” on Diestel’s book. However, in the process I decided to make it a typical blog post of three to four paragraphs. You may even want to dig more by reading Bernie Hogan’s “Using Information Networks to Study Social Behavior: An Appraisal “, the stuff over at the NetWiki and the articles in the graph theory section of MarkCC’s Good Math, Bad Math.
[+] – Hank, this is not a polemic on your view on RDBMS; we have already agreed on what parts of this view we disagree.
Managing organized complexity 
Πολλά θέματα είναι ΠΟΛΥ ενδιαφέροντα σε αυτόν τον κόσμο, ένα από αυτά είναι και η θεωρία γράφων. Πολλοί και με το δίκιο τους θα πουν “εμένα δεν μου χρειάστηκε ποτέ”, γιατί όντως “γραφικά” προβλήματα σπάνια συναντάμε.
Εμένα πάντως μου είχε τύχει ένα το 1998, που όμως μέχρι και σήμερα τρέχει σε kernel mode production code: “Δεδομένου ενός γράφου βρες την μέγιστη απόσταση μεταξύ δύο οποιονδήποτε κόμβων”.
Από τα πλέον κλασικά και “απλά” αλλά αν πας να το λύσεις μπακαλίστικα, βασισμένος στην πολλών κιλών μαγκιά σου απλά έχασες.
Νομίζω πως οι γράφοι είναι μια εντελώς παρεξηγημένη -παραμελημένη αν θέλεις- περιοχή. Ο περισσότερος κόσμος νομίζει πως είτε πρόκειται για ένα θεωρητικό παιχνίδι-άσκηση, είτε για κάτι που έχει σχέση με τους compilers (που έτσι κι αλλιώς είναι δύσκολο subject και το αποφεύγει).
Έτσι η “μαγκιά” που προσφέρουν ώστε ακόμα και σε ένα σκαρίφημα να μπορείς να δεις μια -πρόχειρη έστω- μοντελοποίηση των δεδομένων σου μένει σε αχρηστία. Όπως το ίδιο συμβαίνει και με την πολυπλοκότητα του προβλήματος, η οποία διαισθητικά μπορεί και πάλι να προκύψει από την οπτικοποίησή του.
Είπαμε όμως, όταν έχεις γράψει πολύ σεντόνι (το οποίο βέβαια στην πραγματικότητα μπορεί να μην είναι ούτε ουσιαστικό, ούτε optimal) δε σου χρειάζονται οι γράφοι. Είναι μόνο για κάτι γραφικούς θεωρητικούς.
– Εγώ ασχολούμαι με δίκτυα. Τι σχέση έχουν οι γράφοι και ο Dijkstra;
Έλα ντε…
Σωστότατος ο Steve.