After watching this video lesson, you will better understand the workings of a graph in graph theory. Learn the key terms that you will see and what they look like on the graph. Also, learn how to navigate a graph.
The graphs that you see in graph theory, the study of graphs, look a lot like a connect the dots game. However, you won't always get a nice picture at the end. You will instead get a lot of dots with various lines connecting the dots. And, unlike the connect the dots game, some of the points may have more than one line connecting it to others. The graphs will look something like this:
This is an example of a simple graph. It looks like a connect the dots game, doesn't it? But the finished product doesn't look like a cute animal or an interesting object. It just looks like a bunch of dots with lines connecting them together. The study of how these lines connect the dots is what graph theory is all about.
It may sound boring and pointless, but if you think about a city, its many intersections and roads, and then you think about planning the best route to get from point A to point B, then you might see how graph theory comes into play. Graph theory allows you to find the best route given the roads that connect the various intersections. Look at the graph again, and you might be able to see a little village now. The circles are houses, and the lines are roads connecting the houses. This is just one application of graph theory, and there are others. But it shows how important graph theory is. That is why there is a whole field of math devoted to this study.
As you delve deeper into graph theory, you will come across a few very important key terms, which we will cover in this video lesson. We begin with the terms related to our vertices, our points.
We can have several different styles of vertices. We can have an isolated vertex, which is a vertex with no lines connecting it to others. An isolated vertex in a graph will be all by itself. It won't have any connections.
The vertex to the far right in this graph is an isolated vertex. See how it has no lines connecting it to others? It looks rather lonely. If our graph represents a little village, then this isolated vertex might be a house with no roads to it. You'd have to walk through wilderness to get to it.
Another term that you are likely to see is adjacent vertices. This refers to connected vertices that are next to each other. For example, looking at our last graph, the two vertices at the very top of our graph are adjacent vertices because they are connected, and they are next to each other.
Next, we have the degree of a vertex. This tells us how many lines are connected to the vertex. For example, the isolated vertex has a degree of 0. The vertex to the very far left has a degree of 2 because it has two lines. The vertex at the very top has a degree of 3 because it has three lines connecting it to others. If our degree is even, we call the vertex an even vertex. If the degree is odd, then we call it an odd vertex. That's pretty easy to remember. Odd for an odd number of connections and even for an even number of connections.
Now, let's go over the terms for edges, our lines. We can have multiples edges if we have roads that are parallel to each other or lines that connect the same vertices together. We also have adjacent edges, which, like an adjacent vertex, are edges that are next to each other. Looking at our graph, the edges at the far left of the graph are adjacent because they are next to each other.
Paths and Others
Now that we've covered the terms for vertices and edges, let's talk about the terms for other aspects of our graph. Here, we have what is called a path, a route taking you from one vertex to another. For example, we may want to get from the house at the far left, point A, to the house at the way bottom, point B.
The edges that we take and the vertices that we pass through are all part of our path. The number of edges that we take is referred to as the length of the path. So, for example, if we started going down from point A and continued taking the lowest edges, we would have a path length of 3 since we used three edges to get from point A to point B. If our path takes us from one point, say point A, and it takes us back to the same point A, then we call this path a circuit.
In this example, because all of our vertices are connected, we can call this a connected graph. If we have a graph that is not all connected together, like the one below, then we have a disconnected graph. You can think of a disconnected graph as neighbors or houses that are not connected to the other neighbors or houses. If you lived in one neighborhood, you wouldn't be able to get to the other neighborhood since there are no roads connecting the two.
Now, take a look at this graph:
This graph has two components, or two subgraphs. These subgraphs are graphs in themselves but are not connected to the rest of the graph. If we were to add a connection like this, then we would have just one graph with one component:
This connection between the components is called a bridge. Just like a bridge in real life, if you broke it or got rid of it, then you wouldn't be able to get to the other side. In graph theory, a bridge is the only path you can take from one component to another. So, it's like having just one bridge from the mainland to an island. If the bridge broke down, there would be no way to get to the island. And there we have our important key terms.
Let's review what we've learned. We learned that graph theory is the study of graphs. Vertices are the points in our graph. An isolated vertex is a vertex with no lines or connections to it. Adjacent vertices are connected vertices that are next to each other. The degree of a vertex tells you how many lines are connecting this vertex to other vertices. If the degree is odd, then we can call the vertex an odd vertex. If the degree is even, then we can call it an even vertex.
Our edges are our lines. Multiple edges are lines that connect the same vertices together. Adjacent edges are edges that are next to each other. A path is a route from one vertex to another. The length of the path is the number of edges needed to get from one vertex to another.
If all the vertices in the graph are connected, then we have a connected graph. This means that we have paths that we can take from any point in this graph to any other point in the graph. If not all the vertices are connected to each other, then we have a disconnected graph. In a disconnected graph, the subgraphs are referred to as components. These subgraphs are graphs in themselves but are not connected with the rest of the graph. A bridge connects two components together. Take away the bridge, and we will have two separate components again.
After this lesson, you'll have the ability to:
- Define graph theory
- Identify the types of vertices and edges used in graph theory
- Describe a path and the length of the path in graph theory
- Differentiate between connected and disconnected graphs
- Explain what components and a bridge are in graph theory