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.

Â