This presentation corresponds to Chapter 5.3 in the book. We start by discussing what graphs are. These are not the graphs we plot in coordinate systems but rather structures consisting of vertices and edges that connect the vertices. Here, we have a graph with vertices O, P, Q, and R and edges OP, OQ, OR, and PR. We can use graphs to describe, for example, a map. In the graph here of the Ilocos Region, each province is represented by a vertex or a node and there is an edge between vertices if and only if the two provinces share a common border. For example, La Union shares a border with Ilocos Sur and also with Pangasinan so we have an edge between LU and IS and also between LU and P. Here are important graph theoretic concepts which will be discussed in this video. We start with undirected graphs. The graph on the left is a simple graph while the one on the right is a multigraph. A graph is a multigraph if there is more than one edge connecting certain pairs of vertices. See the multiple edges between the vertices O and T as well as between Q and R. Now, focus on edge HI. The following are equivalent statements. Number 1, H and I are adjacent. Number 2, HI is incident with H and I. Number 3, H and I are endpoints of HI. Lastly, the degree of a vertex is the number of edges incident with it. Hence, the degree of H is 3 because there are three edges incident with H, namely HG, HI, and HM. On the other hand, the degree of I is just 2. Next, we have directed graphs. These are graphs with directed edges. Think one-way streets. You can go one way but not back. The graph on the left is a directed graph while the one on the right is a directed multigraph. Notice that there are two different directed edges from N to I. 1, 2. Now, focus on edge BC. You can go from B to C but not from C to B. The following are equivalent statements. B is adjacent to C. C is adjacent from B. B is the initial vertex and C is the terminal vertex. Lastly, the in-degree of a vertex is the number of edges coming in while the out- degree is the number of edges coming out. The in-degree of B is 1 because there is only one edge coming in towards B. That will be GB. On the other hand, the out-degree of B is 3 because there are three edges coming out of B, namely, BA, BC, and BG. A loop at a vertex, like the one at C, contributes 1 to both its in-degree and out-degree. In this slide, we discuss paths and circuits. IMJ is a path of length 2. IMJ. A path is a sequence of edges which join a sequence of vertices. IMJI, on the other hand, is a circuit of length 3. IMJI. So a circuit is a path which starts and ends with the same vertex. A graph is connected if there is a path between every pair of vertices. The graph on the left is connected but the one on the right is disconnected. This is because there is no path between J and any of the other vertices. These are special paths and circuits. An euler path or circuit is a path or a circuit which traverses every edge exactly once. A hamilton path or circuit is a path or a circuit which passes through every vertex exactly once. The graph on the right has no euler circuit but it has an euler path. The euler path is CGFEDFCD. How did we know? We use these two statements. An euler circuit exists if and only if each vertex has an even degree. An euler path exists if only if there are exactly two vertices of odd degree. There is also a hamilton circuit here. The hamilton circuit is CDEFGC. It is a circuit because it starts and ends with the same vertex C and it is hamiltonian because it passes through every vertex exactly once. Lastly, we describe weighted graphs. Weighted graphs are those whose edges have assigned weights. In applications, the weights may represent distances, costs, or time. In the graph here, ABCD is a path of length 15. We have for the length 4 + 5 + 6. 4 + 5 + 6. On the other hand, AFBA is a circuit of length 7. AFBA. For the length, we have 2 + 1 + 4. An important class of problems involves finding the shortest path between two vertices in a weighted graph. It will be covered in another video.