0:42
But often, when we're organizing our objects,
we like to have them in some sort of sequential order.
And so arrays and linked lists let us organize
the object that we're talking about in a line, one after the other.
And so we can do things like, traverse that list,
iterate over it, search by index, for example.
And pick out element in that ordered list of objects.
But in the previous course, we had applications where there was a hierarchy
amongst the objects that we were organizing.
So, you can think back to organizing dictionaries of words.
And when those dictionaries of words, there was common structure in those words.
For example, we could have one word that's a prefix of another word.
And so we want our data structure to mirror that common structure.
And trees are really great for
that, because you can indicate when nodes are connected to one another.
And in this tree structure, we have that one node is a parent of another
node if that parent is a prefix of its child.
And so we could organize our data structure in this way and
have the nodes be linked by this prefix relationship.
And so in all of these different view points and
all of these different applications, what we're thinking about are these objects and
then whether they have some explicit connections between them.
So, we have these basic objects and their relationships.
And that's really at the heart of what we need when we are talking about graphs.
So, graphs really generalize this principle of organizing a whole lot of
objects together so that we have objects and relationships between them.
And now we wanna think more generally about what
kinds of relationships we might have.
So, really, when we define a graph,
what we need to do is define those basic objects, and those relationships.
And those basic objects are depicted in our representation of a graph as vertices,
or nodes.
And so each object is one vertex in our graph, also known as a node, and
we draw that pictorially as a circle.
And then when we want to denote a relationship between two vertices, or
two nodes, then we can draw an edge between those vertices, or
an edge between those nodes.
And those edges sometimes are called arcs or links.
So, let's think about where we might use these graphs.
So, if we wanna think about objects that are related to one another,
a really good example is the Internet.
And we have in this internet, all sorts of websites.
Each of us can create our own website, write up some HTML code, upload
it to some server, and maybe connect it to other websites using hyperlinks.
And so we can imagine and visualize this entire internet as a graph
where each of the basic objects the vertices in our graph are the websites.
And then there's an edge between two websites if there's a link that
connects them.
Now, there's other contacts in which we have objects that are related
to one another.
And we can think about in the physical world,
4:09
But we could also think about a different situation in which we
have basic objects and relationships.
And this situation could map something much more sociological.
So, we could imagine that the basic objects are people,
real live people in the world.
And the relationship between people could be a friendship relationship.
And so we could imagine a huge graph, where each node on the graph is a person,
me, you, each one of us is a node on this graph.
And then there would be an edge between two of us if we were friends with one
another.
And so you could imagine the questions that we could ask about this graph that
would tell us how communities are formed and evolve in the world that we live in.
And these social networks as just a quick peek are what we'll be focusing on in
the cap stone project for the specialization.
So, stay tuned for those.
But for now, we're actually going to think about a different graph for
this courses project.
And this graph is more geographic.
So, we can think about a graph
5:08
that represents how we move around in the world.
So, our basic objects in this graph could be cities or locations in the world.
And then, we might want to go between one city and another.
And so, the relationships between cities could be, for example, a non-stop flight.
And so if you've been in a plane and
you've flipped through the seat back magazine,
there's often a picture of all the flight paths of that particular airline.
And you see that there's edges between two cities if there's a nonstop flight
offered by that airline between those two cities.
And so then we can think about this graph is telling us information
about how to plan a route throughout the world.
So, we'll talk a lot more about that in the project.
But I wanna mention that if we think away from the flight context,
there's more than one way to get between two cities.
So, for example we could think about driving,
having a road trip between one city and another.
And so we could have a graph that is richer than just the flight plan and have
different kind of edges for different ways of transportation between the two cities.
So in our graph we might have multiple edges between two nodes,
between two vertices.
All right.
One more example.
We could have a graph where the basic objects aren't physical things.
They're not cities, they're not people, but rather they're tasks.
So, think about a big complicated project that you might want
to produce perhaps with a big team.
And in this project there's lots of individual tasks.
So, maybe it's a software engineering project.
Maybe it's a big cooking project.
It doesn't matter. It's a really big project.
That is split up into small tasks.
But some of those tasks require another task to be completed before we start it.
And so there's relationships between certain ones of those tasks which
are dependency relationships.
And so we can picture
those relationships in a graph where we have the vertices are the tasks.
And then we have an edge from one task to another
if we need to complete that first task before we go on to do the second one.
And then what's useful about having this dependency graph
is that then that let's us do is solve the scheduling problem.
How do I take all of these tasks and put them in order so that I can complete my
project successfully while respecting the dependencies?
So, these graphs are super powerful.
It's a really general notion that can be used and
manipulated to represent a lot of different problems.
And so if we think more generally about the problem that we have,
in each of these cases, we're asking some questions about a graph.
And then afterwards Christina and Leo are gonna come back and
think of how do these general questions actually map down to
the concrete root planning that we want to do in the project.
So, for graphs in general, we want to create a graph.
We wanna ask about two vertices in the graph.
Are they close, are they far?
Is it possible to get from one to the other?
We can ask also global properties of the graph.
Are there lots of edges?
Are there lots of relationships?
Are things tightly woven together?
Or is it a pretty sparse graph?
And then we can also ask about can
we break up the graph into connected components, different pieces.
Are there pieces that really don't attract much with one another or
is everything really intertwined?
Are there paths between every two vertex?
Every two vertices.
So, we'll be thinking about each of these questions, but before we do that,
first of all, we have to define the graph, so that's what we'll do next.
Leo PorterAssistant Teaching Professor
Mia MinnesAssistant Teaching Professor
Christine AlvaradoAssociate Teaching Professor
