Hi again.
In the last lecture we saw the problem of the small wall defect, and
how we test if the, if a network or a graph has a small wall defect.
And as we said or
we ended last time, is by formulating the problem, as a graph theoretic problem.
Or the input was a graph, and we had to compute something on the graph.
So now the question is, what is a graph?
The, the, the purpose of this lecture, is to introduce some basic concepts ah,ah,
on graphs, that are needed for this specific problem.
Graph theory is a very rich field of computer science.
We are not going to cover, even 5% of it.
And we are not going to introduce all the concepts that we
need throughout this course.
Now. We are going to introduce this concept as
we need them.
For now we need to talk about basics of graphs.
What is a graph?
How we represent it.
What is a distance in a graph because we need the distances to,
to look at the small walled problem.
So, what is a graph?
That first thing we are going to look at at the graphs in terms of
directions of edges.
So, we are going to talk about two types of graphs in the beginning.
There's an undirected graph and there's a directed graph.
What is an undirected graph?
A, an undirected graph formally is, is, is described by a pair two elements, V and E.
V is a set of nodes.
We say it's a set of nodes.
It has to be, of course, finite.
It's a finite set of nodes.
And E is a set of undirected edges, where an edge is basically a set of two nodes.
Okay? So an edge connects two nodes, and
we represent it as a set of these two nodes.
So, as an example,
[SOUND] this is an undirected graph.
That has four nodes and four edges.
The set of nodes in this graph are 0, 1, 2, 3.
And the set of edges in this graph are, there's an edge between 0 and 1 that is
undirected, so we represent it as an unordered pair or a set of two elements.
There's 0, 1.
There's an edge between 1 and 2.
There is an edge between 2 and 3.
And there is an edge between 3 and 0.
And this graph, if I call this graph G.
This is the, the picture of the graph, or the drawing of the graph.
Formally, the graph is the pair V, E where V is the set and E is this set.
Notice that in sets order does not matter.
I could have written two, one, zero, three, three, one, zero, two and so on.
The order of the two nodes here zero, one, one, zero are the same.
So I don't write it twice.
Same thing with one, two, two three, three zero.
The, the, the fact that I wrote this edge before this edge means nothing.
I could have written this before and so on.
So with undirected graphs, we have a set of nodes,
we have a set of undirected edges.
Okay, when we talk about directed graphs.
Directed graphs have a similar, a similar thing in terms of nodes.
We have a set of nodes.
Doesn't change.
What the difference is, with the, with the edges.
So now these are undirected edges.
But when we talk about directed graph, we have direction on the edges and
when we write them formally, we do not use set notation.
We use double notation.