Networks

Lesson

If we start at a vertex and then move along an edge (in the direction of the arrow, if it’s a directed edge) to a new vertex, we are starting a **walk**. We can continue the walk by selecting another edge coming out of the second vertex, then a third edge coming out of the third vertex, and so on. In a simple network we can represent a walk by a sequence of vertices. Here is a simple, undirected network, with the green arrows representing a walk around the network:

A walk that **starts and ends at the same vertex** is called **closed**, and if it **starts and ends at different vertices** it is called **open**. The walk above is open - below is a different walk on the same network:

This walk has sequence $ABADFCGDEA$`A``B``A``D``F``C``G``D``E``A`. Since it starts and ends at the same vertex, it is **closed**. We can also tell from just looking at the sequence (and not the diagram) that’s the walk is closed, since the sequence **starts and ends with the same letter**.

A **walk** is the broadest, most general definition of how we can move around a network. Sometimes we want to impose a stricter condition - if we say that the walk **cannot use the same vertex more than once**, we call it a **path** (we can reuse the start/end vertex only). Here are two different paths, one open and one closed, on the same network:

applies network techniques to solve network problems