In this lecture, we are going to talk about graphs. That's a basic introduction to graphs, realizing that most of this should be a revision of concepts. We are revisiting a lot of concepts you should have learned in CSCI 2824, your discrete math class and a little bit in your discrete data structures class as well. Hopefully, this is a good revision to get us started on graphs. What's a graph? Well, a graph is a very interesting object. It's a mathematical object which models a binary relation over a finite set. Typically, we draw the elements of this set as vertices of this graph, also called nodes or vertices. The arrows are the edges. This is an example where the set of vertices or the set of nodes is the set v_1, v_2, v_3, v_4 and the set of edges, v_1,v_2, v_2,v_1, v_1,v_3, v_1,v_4, v_2,v_3, v_2,v_4. Typically, there are two things that we don't consider. We do not consider self-loops in graphs, like that. Our graphs generally do not have self-loops in this class, even though we can handle self-loops, it's just a question of do we handle it? No, generally, our algorithms don't work on self-loops. The other thing, some graphs may have are multi-edges and we don't have that. So we cannot have multiple edges between two nodes, you can just either have an edge or not have an edge. The other concept you might have learned is the difference between a directed graph and an undirected graph, which is a very important concept. In a directed graph, the edges between the nodes have direction. In an undirected graph, the edges are considered directionless or better still, bidirectional, which means that you can think of this as a graph where every edge is a two-way edge. If you have an edge v_1 to v_2, you also have the edge going back. Typically, then we do not draw the arrow, we simply draw a straight line without an arrow to denote that it's an undirected graph. In terms of relations, an undirected graph would become a symmetric relation. Hopefully, these concepts were clear to you. Where do graphs come from and why are they important? Where do graphs come from? That's a very important question because graphs are a very important data structure, and you might have already learned where they come from. Computer networks are graphs. In a computer network, these are servers and these are communication links between servers and that forms a computer network, social networks, where the nodes are people and the edges are relations, so that could be a customer-client relationship. It could be a friendship so on and so forth and then you get different types of social networks. This could be ecological networks. In an ecological network, these could be species of animals and these could be predator-prey relationships. What other kinds of networks do we get? They could be electrical circuits. The nodes are junctions and the edges are wires. They could be programs, there are multiple graphs that come out of programs. The nodes could be variables, they just could be data dependencies. The nodes could be control locations in the program. The edges could be controlled flow. You get different kinds of graphs like control flow graphs, data flow graphs, and so on. Graphs come about in a lot of places and we often wish to perform operations and run algorithms on graphs. By the way, the Google Maps, roads, street addresses, there's plenty of graphs and we would like to solve problems on graphs. What are the kinds of problems we would like to solve? There are many kinds of problems starting with traversal problems. Identifying cycles in graphs, ranking the nodes in graph. What else? Finding shorter spots, finding spanning trees, you will find this very important applications to finding what are called spanning trees, and we will talk about this. Flows on graphs, very important problems. With all of these, you really need to understand how to represent graphs, how to run algorithms on graphs. First question is, how do we represent graphs on a computer? You should already either know this or you will study this very soon in your data structures class. If you haven't already taken it, you will study this very soon and that's where you will explore these ideas a little bit better, but for the purposes of this class, there are many representations of graphs and the complexity of the algorithms will depend on what representation you start with. The simplest representation is called an adjacency matrix. In an adjacency matrix, a graph is just defined by a matrix where the vertices form the rows and the vertices also form the columns. If there is an edge between n_i and n_j, you place a one entry for i, j. This means that edge from n_2 in this case, let's call this n_j to n_j. In general, the i, j entry says, is there an edge n_i, n_j in the edge set of the graph? If there is, you place a one there. If there isn't, you place a zero there. It's a matrix of zeros and ones, and this is called adjacency matrix. If there are key vertices in the graph, the size of this representation is k squared. Often, graphs have lots of vertices and very few edges. This is the case in many of the graphs that I have listed here. For example, computer networks. If you think about the Internet, there are billions of vertices on the Internet, but there aren't billions of communication links. Each vertex is connected to relatively few other computers with a physical link. This is an example. Social networks, there are billions of people on Facebook, but each person has a few hundred friends. Each person could be friends with a billion people. But no, we are not friends with a billion people, except maybe for Mark Zuckerberg. The rest of us are friends with maybe a few hundred to a few thousand people or a few tens of thousands of people if you're really social; maybe really social, then you're friends with about ten thousands of people or if you're a celebrity. Otherwise, you are friends with about a thousand people beyond which I wonder what the term friend means. Ecological networks. There are tons of species, thousands or tens of thousands of species on the planet, but not every species has a predator prey relationship. We have a set of foods that we eat. If we are the predator, then our prey consists of let's say, chicken and lamb and so on and so forth, but it's not every species on the planet well, unless you are someone who does eat every species on the planet, which hopefully you aren't. What you see is that these graphs in the world generally have what's called sparsity structure. Even though a graph with k nodes can have up to k times k minus 1 edges, that's the maximum number of edges that a directed graph with k nodes can have, real graphs have much fewer edges than this big maximum number. What does that mean for an adjacency matrix? Which means that most of this matrix is zeros. Very few entries of this matrix is one. A lot of space in this matrix is wasted in just storing zeros and very few of them are ones. There's a different representation that's more commonly used because of the sparsity and it's called the adjacency list representation. Here, we don't represent it by a matrix, we represent it by a list. Every node, n_1 points to a list of its neighbors, n_2 points to a list of its neighbors, n_k points to a list of its neighbors or adjacent nodes. What's the size of the adjacency list representation? If your graph has let's say, k nodes and m edges, then the adjacency list is going to have one cell for every node. There's going to be k cells. Each cell is going to point to a neighbor, but remember, a neighbor is characterized by an edge, so for every neighbor, there is an edge that defines that neighbor. Each of these entries is corresponding to an edge in the graph. The total number of cells is k plus m. K cells for each of the nodes. If you add up all the sizes of the list hanging off of each of the nodes, that gives you the number of edges. You have k plus m, or the number of vertices plus the number of edges, which in many cases can be much smaller than the adjacency matrix representation. This is a vain if your graph is sparse, so then you represent your graph using an adjacency list representation. Now there are other representations. There's a very popular representation called the incidence matrix representation and of course, the incidence matrix representation has some linear algebraic properties. It gives rise to something called the graph Laplacian and so on. We'll not talk about that. Let's just stop with adjacency matrix and adjacency list, noting that there are some other representations which are also important for certain kinds of algorithms. Hopefully, we are revising and hopefully you remember all of this or you have encountered all of this. We know what a graph is, we know why we care about graphs in computer science in general, and what are the two ways to represent a graph; an adjacency matrix and adjacency list representation. If we understood all of this, then we are now ready to look at some algorithms on graphs. Thank you.
