1. Basic Graph Definition

A graph is a symbolic representation of a network and of its connectivity. It implies an abstraction of the reality so it can be simplified as a set of linked nodes.

Graph theory is a branch of mathematics concerned about how networks can be encoded and their properties measured.

In transport geography most networks have an obvious spatial foundation, namely road, transit and rail networks, which tend to be defined more by their links than by their nodes. This it is not necessarily the case for all transportation networks. For instance, maritime and air networks tend to be more defined more by their nodes than by their links since links are often not clearly defined. A telecommunication system can also be represented as a network, while its spatial expression can have limited importance and would actually be difficult to represent. Mobile telephone networks or the Internet, possibly to most complex graphs to be considered, are relevant cases of networks having a structure that can be difficult to symbolize. However, cellular phones and antennas can be represented as nodes while the links could be individual phone calls. Servers, the core of the Internet, can also be represented as nodes within a graph while the physical infrastructure between them, namely fiber optic cables, can act as links. Consequently, all transport networks can be represented by graph theory in one way or the other.

The following elements are fundamental at understanding graph theory:

Graph. A graph G is a set of vertex (nodes) v connected by edges (links) e. Thus G=(v , e).

Vertex (Node). A node v is a terminal point or an intersection point of a graph. It is the abstraction of a location such as a city, an administrative division, a road intersection or a transport terminal (stations, terminuses, harbors and airports).

Edge (Link). An edge e is a link between two nodes. The link (i , j) is of initial extremity i and of terminal extremity j. A link is the abstraction of a transport infrastructure supporting movements between nodes. It has a direction that is commonly represented as an arrow. When an arrow is not used, it is assumed the link is bi-directional.

Sub-Graph. A sub-graph is a subset of a graph G where p is the number of sub-graphs. For instance G’ = (v’, e’) can be a distinct sub-graph of G. Unless the global transport system is considered in its whole, every transport network is in theory a sub-graph of another. For instance, the road transportation network of a city is a sub-graph of a regional transportation network, which is itself a sub-graph of a national transportation network.

Buckle. A link that makes a node correspond to itself is a buckle.

Planar Graph. A graph where all the intersections of two edges are a vertex. Since this graph is located within a plane, its topology is two-dimensional.

Non-planar Graph. A graph where there are no vertex at the intersection of at least two edges. This implies a third dimension in the topology of the graph since there is the possibility of having a movement "passing over" another movement such as for air transport. A non-planar graph has potentially much more links than a planar graph.

2. Links and their Structures

A transportation network enables flows of people, freight or information, which are occurring along its links. Graph theory must thus offer the possibility of representing movements as linkages, which can be considered over several aspects:

Connection. A set of two nodes as every node is linked to the other. Considers if a movement between two nodes is possible, whatever its direction. Knowing connections makes it possible to find if it is possible to reach a node from another node within a graph.

Path. A sequence of links that are traveled in the same direction. For a path to exist between two nodes, it must be possible to travel an uninterrupted sequence of links. Finding all the possible paths in a graph is a fundamental attribute in measuring accessibility and traffic flows.

Chain. A sequence of links having a connection in common with the other. Direction does not matter.

Length of a Link, Connection or Path. Refers to the label associated with a link, a connection or a path. This label can be distance, the amount of traffic, the capacity or any attribute of that link. The length of a path is the number of links (or connections) in this path.

Cycle. Refers to a chain where the initial and terminal node is the same and that does not use the same link more than once is a cycle.

Circuit. A path where the initial and terminal node corresponds. It is a cycle where all the links are traveled in the same direction. Circuits are very important in transportation because several distribution systems are using circuits to cover as much territory as possible in one direction (delivery route).

3. Basic Structural Properties

The organization of nodes and links in a graph conveys a structure that can be described and labeled. The basic structural properties of a graph are:

Symmetry and Asymmetry. A graph is symmetrical if each pair of nodes linked in one direction is also linked in the other. By convention, a line without an arrow represents a link where it is possible to move in both directions. However, both directions have to be defined in the graph. Most transport systems are symmetrical but asymmetry can often occur as it is the case for maritime (pendulum) and air services. Asymmetry is rare on road transportation networks, unless one-way streets are considered.

Completeness. A graph is complete if two nodes are linked in at least one direction. A complete graph has no sub-graph.

Connectivity. A complete graph is described as connected if for all its distinct pairs of nodes there is a linking chain. Direction does not have importance for a graph to be connected, but may be a factor for the level of connectivity. If p>1 the graph is not connected because it has more than one sub-graph. There are various levels of connectivity, depending on the degree at which each pair of nodes is connected.

Complementary. Two sub graphs are complementary if their union results in a complete graph. Multimodal transportation networks are complementary as each sub-graph benefits from the connectivity of other sub-graphs.

Root. A node r where every other node is the extremity of a path coming from r is a root. Direction has an importance. A root is generally the starting point of a distribution system, such as a factory or a warehouse.

Trees. A connected graph without a cycle is a tree. A tree has the same number of links than nodes plus one. (e = v-1). If a link is removed, the graph ceases to be connected. If a new link between two nodes is provided, a cycle is created. A branch of root r is a tree where no links are connecting any node more than once.

Articulation Node. In a connected graph, a node is an articulation node if the sub-graph obtained by removing this node is no longer connected. It therefore contains more than one sub-graph (p > 1). An articulation node is generally a port or an airport, or an important hub of a transportation network, which serves as a bottleneck.

Isthmus. In a connected graph, an isthmus is a link that is creating, when removed, two sub-graphs having at least one connection.