0:03

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.

Â 5:52

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.

Â