Connectivity

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: The point of switching from relational language to graph theoretical language is really so that we can talk about paths and connections. So let's look at the topic of graph connectivity in general. Two vertices in a simple graph, or for that matter, a directed graph, are said to be connected if and only if there's a path between them. In a directed graph, the path would have a direction.

In a simple graph, paths don't have direction. So a is connected to b if and only if b is connected to a. It's a symmetric relation. So two vertices are connected if and only if there's a path between them. That's equivalent, of course, to saying if and only if there's a walk between them.

We include length 0 paths and length 0 walks, so every vertex is considered to be connected to itself. A whole graph is said to be connected if all of its vertex are connected to each other. So every graph you can think of as broken up into the mutually connected pieces, or subgraphs, which are called its connected components.

So let's look at a simple example. Let's look at the connections between MIT buildings, where we draw an edge between building 10 and building 13 if there's a door between them or a corridor or between them. So there's a corridor between building 10 and building 4, but not between building 10 and building 12. To get to 12, you have to go through 4.

That's the main building numbers off the MIT Infinite Corridor. East campus, of course, isn't connected to anything, so it's a single, isolated vertex. And then there's the medical center in E17 and E25, which are a sequence of four buildings that are connected as indicated, but not connected at all to east campus or the Infinite Corridor, that is, you have to go outside to get from east campus to the Infinite Corridor or from the Infinite Corridor to the medical center. Unless you sneak through the basement and another restricted areas.

So this is one graph. It's not three graphs. This is one graph which has three parts, and so it has three connected components. In general, the more connected components a graph has, the more broken up it is, and that's a way to remember it.

The formal definition of the connected component of a vertex, v, is simply all of the vertices, w, that are connected to v. And if you look at these connected components, they've defined an equivalence relation on the vertices, of course, because a connected component is a block of the equivalence relation. It's a block of the partition associated with the equivalence relation.

Another way to define this, the set of w that are connected to v, is simply it's taking the image of v under the greater than or equal to 0 walk relation. E star is our notation for the walk relation in the graph whose edges are E, including walks of length 0. So a graph is connected then means it really has only one connected component.

Free Downloads

Video


Caption

  • English-US (SRT)