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.