Graphs Introduction Introduction

Picture this: the Shmoopville City Zoo has just welcomed its newest member: Isabella the baby pygmy panda. The news of the latest ZooBorn is enough to send any town into a frenzy, but a baby pygmy panda? That's enough to make a statewide holiday—if it doesn't break the internet beforehand.

The zoo opens at 10am, and you plan on being the first person to see it (you never gave up on the idea that it could imprint, even though at least a thousand zoo employees have seen it before you).

But…remember that whole statewide holiday thing? Yeah, so did the rest of the state, and they're all coming to see that itty bitty baby at the same time as you, so you need a way to get to it before anyone else and say all your "oohs," "ahhs," and "so adorbs" uninterrupted. You need to find the shortest path to the pandas.

Being the clever algorithmist that you are, you make a map of the zoo, simplifying exhibits to points and figuring out about how many minutes it takes to get to each point. Your graph looks something like this:

A graph of the different exhibits in the zoo, with the time it takes to get from each exhibit to the next.

Most people agree that getting anywhere in the zoo is made faster by first visiting the penguin exhibit, since it's in the middle. But you know better and decide to add the times together for every possible path from the entrance to that adorable new cub. Lo and behold, you figure out that the best path isn't through the penguins, but the jaguars (probably because they have such fast cars). In just 14 minutes, you can be right there, staring through the glass, watching pandas idly chew bamboo.

A graph, with the shortest path (Entrance → Jaguars → Pandas) marked in purple.

Finding the shortest path couldn't happen without a little graph theory. Now you can guarantee that you'll be the first to see the cutest ZooBorn the world has ever seen—at least as long as no one else figures out the shortest path.

 

Why Should I Care?

Graphs: they aren't just for math class. They show up everywhere.

Transit systems? Modeled by graphs. Things like

  • planes
  • trains
  • semi-trucks

all use graphs to figure out how to get places the fastest. That's what helps you get fruit anywhere in the country while it's still fresh. Nobody wants over-ripe fruit (except for maybe this guy).

But that isn't all. Graphs

  • power the internet. Literally.
  • model relationships between you and your 1000 closest friends on Facebook. 
  • give computers the winning strategy at Tic-Tac-Toe (and other games) in seconds.

Graphs allow you to search in a systematic, organized way through very large, complex sets of data. Even better: they let you sort through that information to find things like the shortest path. At the end of the day, they're just a way of organizing information, but the way they do it is perfect for computers to understand relationships between things.

The key to a computer's heart is through its graphs. So let's start graphing things.