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.