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