[MUSIC]

So in the previous video we started talking about graphs as this general data

structure where we have nodes and we have connections between them.

And what we're going to do now is really hammer down some definitions and

see how these definitions come into play.

By the end of this video you'll be very comfortable with these basic definitions

that are associated with graphs.

So as we mentioned, in order to specify a graph all we need to talk about

are what the collection of basic objects are, and

then what the relationships between them need to be.

And the terminology that we use for the basic objects are the vertices or

the nodes.

And then the terminology that we use for

the relationships between them are the edges or the arcs or the links.

Now the vertex set is often denoted by capital V.

The edge set is often denoted by capital E.

And something you wanna keep in mind is that when we're talking with the size of

a graph, which is going to be important when we think about performance,

the size of the graph really depends on both the size of V and the size of E.

The number of vertices and the number of edges.

We'll talk more about that as we develop more algorithms.

Now think back to the example with the friendship graph.

If I'm your friend, you're my friend, we're both friends with one another.

It's not like I can be your friend but you can't be my friend back.

It doesn't work.

In that situation our edges between vertices are undirected.

They don't have arrowheads.

They don't point from one vertex to another.

A way of saying that in math speak is that the edge relationship is symmetric.

Now, we have other graphs that ordering really does matter for.

And think back to the example we talked about before with dependencies,

with task dependencies, and in that situation the arrows really do matter.

And so we can have grasped directed which means that for

every edge we want to think about it's end points.

So we've got two endpoints for each edge, each of the endpoints is a vertex.

And it makes a difference whether the edges pointing from one vertex

to the other or vice versa.

All right, so we've got a notion of undirected graphs,

we've got a notion of directive graphs.

And then we can also think about enriching these graphs a little bit, and

sometimes our edges can carry with them more information.

So sometimes we want to label our edges, perhaps with weights that

might represent something like the cost of going across this edge.

And you'll see the weights coming into play again and

again when we develop algorithms in the future modules of this class.

So, we've got these vertices, we've got edges, and

they're coming together to build up this data structure.

So let's start by thinking about the neighborhood relationship of

a particular vertex.

And so a one vertex is a neighbor of another vertex if

there's an edge between them.

And so take a look at this particular graph, and

think about what the neighbors are of the vertex 4.

So let's talk about one more notion that's going to be really important about graphs,

and that's the notion of paths.

So when we're thinking about a big graph, what often we wanna do

is find a way of getting from one part of the graph to another.

And so that might be useful in the root planning project that you're doing in this

class, but it could also be useful for

thinking about global properties of the graph.

So a path in a graph is a sequence of vertices and edges that depict,

you can imagine yourself hopping along the edges in the graph to get from one place

to another.

And so I'm only ever allowed to move along edges,

from one vertex to another along an edge.

So let's think about this particular directed graph, and think about for

which pair of these vertices is there a path in the graph

that goes from the first vertex to the second.