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

Introduction to Graphs

Algorithms, Part II

Meet the Instructors