Next: Shortest Paths Up: A Tutorial on Network Previous: Introduction

Terminology

A network or graph consists of points, and lines connecting pairs of points. The points are called nodes or vertices. The lines are called arcs. The arcs may have a direction on them, in which case they are called directed arcs. If an arc has no direction, it is often called an edge. If all the arcs in a network are directed, the network is a directed network. If all the arcs are undirected, the network is an undirected network.

Two nodes may be connected by a series of arcs. A path is a sequence of distinct arcs (no nodes repeated) connecting the nodes. A directed path from node i to node j is a sequence of arcs, each of whose direction (if any) is towards j. An undirected path may have directed arcs pointed in either direction.

A path that begins and ends at the same node is a cycle and may be either directed or undirected.

A network is connected if there exists an undirected path between any pair of nodes. A connected network without any cycle is called a tree, mainly because it looks like one.