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?. Well the answer for that one is that you can use DFS to get this done. I wouldn't think that any programmmer can do it. Ask a friend. But with DFS, you can see in the book, a pretty simple DFS based solution, that to this problem. That'll tell you whether a graph is bipartite, by labeling vertices in such a way. If it is bipartite, that, all the edges have the property to go from one set, one vertex to another. So definitely a good exercise after this lecture is to try to write a program that test whether a graph is bipartites or not. Okay, let's, oh, here's another application of this by the way. That dating graph for the sexual transmitted diseases so there's males and females, is that one gonna be bipartite? I think maybe this one is but, nowadays maybe not in general. Okay, what about this one, Does a graph contain a cycle or not? 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. So, that's the kind of another point on this range of difficulty of graph processing problems. So there's no question that graph processing is challenging. And this introductory lecture gave us numerous useful graph processing algorithms. But still leaves us with the feeling that there's plenty more to know and we'll cover some more in later lectures.
