How does graph theory work and how is related to computer science?
In: Engineering
You can think of a graph as a bunch of dots on a piece of paper, with some of the dots connected by lines. Graph theory deals with describing how the dots are connected and how get between one dot and another. It deals a lot with finding paths between places. In graph theory the dots are called “nodes” and the lines are called “vertices”.
There are a lot of things in computer science that you can think of as a graph, which allows you to apply graph theory techniques to them. For example, the Internet is made up of a web of computers and router all connected to each other. So if you wanted to connect your computer to Reddit to see a silly cat picture, you’re likely to want to have the fastest or shortest route from Reddit to you. All the machines are the dots on paper, and the lines are all the cables and wires connecting those machines.
Another example is Facebook. When it suggests friends, it is basically making a graph where you are the starting node. Then your friends are nodes directly connected to you. Then their friends are nodes connected to them, and so on. So to find suggestions, Facebook starts at you and searches for every node connected to you, then connected to them, and so forth moving outwards, with the assumption that people close to you on the graph are more likely to want to friend each other.
How does graph theory work? Well, you start by taking objects (called nodes or vertices) and connecting them to each other with either undirected or directed “lines,” (directed lines can only have information or whatever flow one way) that represent relationships. Then you can determine properties of the resulting graph using math.
In computer science, you can use virtual graphs to map all sorts of things, because the computer can store them fairly efficiently. It is most popular to use them to study network dynamics (especially how networks function as they gain and lose nodes), data organization and interrelations, and even computational flow through a program.
I’m not a CS (just a former non-discrete math major) so that’s about all I know, but there’s even graph-specific languages like GRAPE that make processes like this easier. If you’re really interested, this is usually the domain of some undergraduate abstract algebra courses.
Latest Answers