Welcome back.
Our topic today is algorithms for
processing undirected graphs which are a
model that are widely used for many, many
applications.
We'll see plenty of examples and then
we'll look at three fundamental algorithms
for processing undirected graphs and
consider some of the challenges of
developing algorithms for, for this kind
of structure.
So as introduction we'll take a look at
the basic ideas behind undirected graphs
and applications.
What is an undirected draft?
It's the, the definition is very simple.
It's a set a verticies connected pairwise
by edges.
So this is an example of an undirected
graph that describes the Paris Metro.
You've got stations and if there's a rail
line between the stations there's an edge.
So why do we study graphs and graph
algorithms?
Well there are literally thousands of
practical applications where graphs are an
appropriate models and we'll take a look
at a few others in just a minute.
Because there are so many applications,
there's literally hundreds of graph
algorithms known and these are sometimes
quite sophisticated, as we'll see and also
very important in understanding what's
going on in an application.
Even without the applications a graph is
really an interesting and broadly useful
abstraction to try and understand that's
so simple to describe, but leads to quite
complex and difficult to understand
structures.
In a general graph theory and graph
algorithms is a very challenging branch of
computer science and discreet math that
we're just introducing now.
So here's an example of a graph,
In, in genetics or in genomics,
Where if the network where the nodes are
proteins and the edges are interactions
among the proteins.
And genomicists are trying to understand
how these biological processes work.
Need to understand the nature of
connections like this.
Here's another example, the internet
itself, where, every node is a computer
and every edge is or, or a node, every, a
computer or a communications device, and
every edge is connections.
And of course, the Internet is driven by
loops and bounds, so this is a huge craft,
in this lot of needs, lot of interest
understanding, properties of this craft.
This is a, social graph having to do the
way science is carried out.
So it's the, the nodes are and scientist
websites and the edges or, clicks
connecting one to another.
This one shows how scientists in different
fields are interacting.
And again interesting and important to
understand properties of this graph.
You're certainly familiar with Facebook.
That's one of the hugest one of the
biggest graphs.
It's absolutely huge,
And it's always changing.
It's very dynamic and people want to
understand its property.
This is an example of a graph, that was
used, in litigation,
Where people were trying to understand,
exactly, precisely, the communications
patterns, in a particular corporate
culture, that was of great interest to
many people.
Another similar example, this is people
lobbying the FCC and how are they
connected.
So from the breadth and variety of these
examples, you can see that number one.
Graphs are very general model, and number
two, graphs can be huge.
This is another one showing the Framingham
heart study and connections among people
in the study and how it relates to
obesity.
So those examples in this list shows that
it's graphs are very flexible and very
dynamic model and that the graphs involved
can be huge they could have complex
properties. And so our challenge is to try
to figure out efficient algorithms that
can give us some insight into the
structure of graphs like this.
That's what we're going to be talking
about for the rest of this lecture.
So now back to a starting point which is
we need some simple and clear and specific
definitions about basic terms that we're
talking about.
And then we'll look at algorithms that
work for a small example but also the same
algorithms do what we need for big graphs
of the type we just considered.
So this is the terminology for that we'll
use for graph processing.
So we have a vertex which is a black dot
in this graph and an edge which is black
line connecting two vertices.
And then a few more concepts that are
important in many applications.
So one is the idea of the path.
That's just a sequence of vertices
connected by edges.
And the idea of a cycle,
Which is a path who's first and last
vertices are the same.
So over on the left, you can see a cycle
of length five, that connects these five
vertices.
And wherever you start, you go back to the
same place.
So we say the two vertices are connected
if there's a path between them.
And then that definition leads us to the
idea of a graph dividing up into
connective components,
Which is subsets of the graph where each
pair of vertices is connected.
And, so one of the algorithms that we're
going to look at today is one for
identifying connected components in, in a
graph.
So that's just one example.
Here's some examples of problems that
might arise in graph processing that are
easily understood just given these basic
definitions.
So the very first one is given two
vertices, is there a path connecting those
two vertices?
Like in the Internet graph, you want to
know, can I get from where I am to where I
want to get?
Or maybe you want the shortest path,
The most efficient way to get between two
vertices.
You might want to know is there a cycle on
the graph?
If the graph maybe represents electrical
kind activity a cycle might represent a
short circuit,
You would want to check for that.
Or maybe you want to systematically go
everywhere in the graph,
So there's two related problems called the
Euler tour and the Hamilton tour.
Euler tour is, is there a cycle that uses
each edge exactly once?
Can I go look around the graph and touch
every edge in it?
And the one called the Hamilton tour,
which says well I'm really just interested
in getting to the vertices.
Is there a cycle that uses each vertex
exactly once?
Or basic connectivity problems.
So you want to know, is there some way to
connect all the vertices?
Is there a path between each pair of
vertices in the graph or not?
Or you might want to know what's called
the minimal spanning tree, which is the
shortest set of edges, or the best way to
connect all of the vertices.
And then various processing issues related
to connectivity.
For example, is there a vertex whose
removal disconnects the graph?
Drawing the graph.
Can you draw the graph in the plane with
no edges crossing?
Some of the graph with nodes are
correspond to places in the plan or cities
on the Earth or whatever,
But some of the other graphs are very
abstract, may have nothing to do with
geometry.
You might want to know can you draw with
no crossing edges or you might have two
graphs, and a vertex named different to
represent the same graph.
So one of the biggest challenges in graph
processing that we'll address today in
this lecture somewhat is just to decide
how difficult are these problems.
Some of them are very easy, some of them
are very difficult and some of them,
actually, is unknown how difficult they
are.
There's such a broad variety of problems
that are simply stated.
One of the first things that we have to be
aware of when doing graph processing is
that we, we are entering into a forest of,
of all different possibilities and, and we
have to be careful that we're working on a
problem that we can solve.
And we'll try to give some insights into
that during the lectures that we gave on
graph-processing.
So that's our introduction to