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.