0:03

Okay. Now that we, that we've discussed

Â breadth-first search and depth-first search in connected components three.

Â Very useful graph processing algorithm for all sorts of real applications.

Â Now we're gonna go back to the idea of the different problems that might arise when

Â doing graph processing, And what are, what are our intuition I-,

Â with this experience? And what types of problems are difficult,

Â and what types of problems are easy? It's not that I have any real answers to

Â that but we wanna keep coming back to this issue,

Â So that we can appreciate a great algorithm when we see it.

Â So, here's a challenger or an example of a challenge.

Â So, here's a problem that comes up in plenty of applications.

Â So you want to know if a given graph is bipartite.

Â So what bipartite means is you can divide the edges into two subsets, divide the

Â vertices into two subsets with the property that every edge connects a vertex

Â in one subset to a vertex in another. So in this case, we can assign zero,

Â three, and four to be red vertices. And if we do that, then every edge

Â connects a red to a white vertex. That's a bipartite graph and we saw an

Â example of bipartite graph the Kevin Bacon graph.

Â We had movies and performers, two different types of vertices, and every

Â edge went from a movie to a performer. And in general and other applications, so

Â we want to know is a graph bipartite. So by graph processing challenge, I mean

Â is how difficult is this problem? And so what do you think, based on our

Â experience? Is this a problem that any programmer

Â could do? Or maybe you need to be a typical diligent

Â student in this course, Or maybe it's difficult enough that you

Â ought to pay somebody to do it. Or, actually maybe it's even an expert

Â couldn't do it, and we'll talk about the precise meaning of that later on.

Â Or maybe we don't even know how difficult it is, or maybe we can show that it's

Â impossible to solve this problem. These are pretty broad categories, and

Â you'd like to think that we could categorize problems in these kinds of

Â categories. So what about biparting? We'll do this for

Â a bunch of problems, but what about bipartitenes?.

Â 3:54

So in this case, there's a cycle, zero to five to four to six back to zero, and this

Â other cycle's two, zero, one, three, two there are two, four, six those are all

Â cycles. So how hard is it to find a cycle in a

Â graph in these categorizations well that one, It's very simple.

Â This one, maybe any programmer could do. Maybe.

Â You have to have the graph representation, But you have to use DFS.

Â Well, you could figure out a way to do it without, probably,

Â But anyway it's really simple with DFS. You, you don't even need to hire an expert

Â for finding a cycle. Alright here's a classic graph processing

Â problem that dates back to the eighteenth century.

Â So it's this town in Konigsberg in Prussia at the time where there's an island,

Â And the river kinda comes in and branches around the island and then goes out in two

Â branches. And there's a bunch of bridges, five

Â bridges onto the island, two from the banks and one across, to the this third

Â peninsula and then there's two bridges crossing that way,

Â So a total of seven bridges one, two, three, four, five, six, seven.

Â And Euler who's a famous mathematician would go out on Sunday stroll in this

Â place and came up with the idea. You know could anyone find a way to go on

Â a Sunday stroll and cross each one of these bridges exactly once.

Â So that's, often talked of as, the, original graph processing problem.

Â So, in terms of graphs, it's is there a cycle that uses every edge exactly once.

Â Given a graph, is there a cycle that uses every edge exactly once?

Â A and actually, a Euler, proved, a let's say first theorem in graph theory, a if

Â its connected, and all the vertices have even degree, you can always do it.

Â In this case you can't because there's a vertex with odd degree.

Â So that's, that's the answer to the existence, is there a cycle.

Â But suppose you wanted to find the cycle. So you can go ahead and check the degree

Â of every vertex. We looked at easy code for that to know

Â that there exists a cycle but how about finding one that uses every edge exactly

Â once. So in this case, here's the cycle that

Â uses every edge exactly once. And this graph every vertex has even

Â degree, and if you go zero, one, two, three, four, two, zero, six, four, five,

Â zero you get to every edge exactly once. That's an Eulerian Cycle. so how about

Â that one? Is that any programer a or do you have to

Â hire an expert, or is it impossible? Well this one we have it listed as a

Â typical, diligent algorithm student can do it.

Â But it's a, it's a, a bit of a challenge. It's a, an interesting program and again

Â once you get through the bipartite graph on you can think about this one.

Â A it makes some sense what the algorithm does, but it might take you a few tries to

Â get the code debugged, Let's say then you'll find code for it, it

Â looks like. Alright.

Â So that's a Eulerian Cycle What about if you want to visit every vertex exactly

Â once? So, you don't care about going over all

Â the edges, you just want to get to all the places.

Â That's called the, in this case there is a way.

Â For this graph zero, five, three, four, six, two, one, zero.

Â So that's a way to get to every vertex exactly once.

Â This is sometimes called the traveling salesperson problem on graphs.

Â If the sales, traveling salesperson has to get to every city and wants to just go

Â there once without retracing steps. So how about that one?

Â The, every edge is more to visit, it might seem more challenging.

Â And, actually, maybe if you have any experience with this, you realize that

Â this one is intractable. That's called the Hamiltonian Cycle

Â problem, and it's a classical NP-Complete problem.

Â We'll be talking about NP-Complete problems at the end of the course, but

Â basically the idea is that nobody knows an efficient solution to this problem for

Â large graphs. And it's a frustrating situation that

Â we'll talk about. But, you definitely not gonna, solve it by

Â just being a diligent algorithm student a and not even hiring an expert will get it

Â solved, no matter how much the expert charges.

Â So the intuition on finding a cycle that visits every edge once.

Â Yeah, you could do it. Find a cycle that visits every vertex

Â once, probably not. That's the kind of challenge that we face

Â when addressing applications of graph processing.

Â Here's another example. Problem is, given two graphs you want to

Â know are they identical except for the way that we need the vertex.

Â So here's an example of, a these two graphs don't look all that identical, at

Â all. But if you, take zero here and rename it

Â four and one and rename it three and like that,

Â Then sorry zero here and name it four and one and rename it three and like that.

Â Then you'll see that they are the same graph.

Â They represent the same connections. And in so many applications where, maybe

Â the vertex names are, are a bit arbitrary or you just wanna know.

Â Really the interest is in the structure of the connections, you might wanna know if

Â just the way that I name the vertex makes the graph different?

Â Or if I have two classes that have two different kinds of interactions, is it the

Â same interactions that's independent of the people or scientific experiment

Â studying a property of the universe or whatever, you might wanna know, is that

Â connection structure the same or not? That's called the Graph Isomorphism

Â Problem. How difficult you think that one is?

Â So, you know, you could, there you can try all possible ways of renaming the

Â vertices, But there's really a lot of ways, in

Â factorial ways. Way too many to try for a huge graph.

Â Is there efficient way to do it, Or is it intractable like the Hamiltonian

Â Path Problem. Where it's in this category that nobody

Â knows an efficient algorithm for but there could be one.

Â Actually for Graph Isomorphism, that's one that's stumped mathematicians and computer

Â scientists for many years. Nobody knows even how to classify this

Â problem. We don't know if it's easy or if it's in a

Â class of problems that are, we don't know how to solve but there could be a

Â solution. We can't show that it's impossible or

Â guaranteed to be difficult. Nobody knows how to classify this problem.

Â Again, pointing out that, even for a relatively simple problem to state.

Â The state of our knowledge and understanding the properties of algorithms

Â to solve such problems, is, it's incomplete for sure.

Â So one last one, here's a graph processing challenge.

Â So this graph, when it's laid out it's got two edges that cross between, between

Â three and four and zero and five. And in general if you have a graph that

Â you've got, so say the social networking graph of a small class, you want to study

Â that graph and look at it, you want to draw it on the plane and maybe you don't

Â want, you want to do it without having edges crossed.

Â So in this case there is a way to place the vertices in the plain so that when you

Â draw the edges no two of them cross. So, how difficult is that problem, even is

Â it possible to do or not. So, that's a classic problem in

Â graph-processing that, came up, from, the first time that people were ever sending

Â graphs in computers. And the answer to this one is also,

Â interesting to contemplate. There's a linear time algorithm known for

Â this based on DFS. So that means the running times, you could

Â run it on huge graphs. You could know, whether or not you could

Â lay it out in the plane. It was discovered, by Tarjan in the

Â 1970's. And you heard that name come up again, in

Â graph processing. Based on DFS,

Â But, if you really wanna get this done, you need to hire an expert, 'cause that is

Â quite a complex algorithm, And probably, beyond, what a diligent

Â algorithm student, or a professor, might accomplish.

Â