0xDE (11011110) wrote,

Why graphs?

Someone today asked me: why graphs? “Why are graphs so widely used in computer science, and in related fields such as software engineering?” Here's my glib response:

The short answer is that graphs can be used to reason symbolically about any kind of pairwise relationship between any kind of entity, and that we like to think about pairwise relationships because unary relationships aren't powerful enough and k-way relationships for k>2 add extra complication without adding any real power.

So already in 1736 Euler was using graphs to model transportation connections between pairs of places (the bridges of Königsberg; more modernly this idea shows up in airline ticket planning, where the vertices represent airports and the edges represent flights, or in mapquest-like route planning, where the vertices represent road intersections and the edges represent intersection-free segments of roads). We have graphs representing people and social networks connecting them (online friendships, sexual contacts, parenthood, coauthorship, etc). We have graphs representing subroutines in a computer program and caller-callee relations between them. We have graphs representing web pages and html links between them. We have graphs representing proteins in your body and the chemical interactions they participate in. Etc etc.

Graphs are powerful because the same kinds of problems and algorithms turn out to be important in many of these different applications. So by taking away the application-specific features of all of those different problems and turning them into something as abstract as a graph, we only have to solve these problems once instead of repeatedly solving the same problems in different disguises.
Tags: graph theory
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded