Vocabulary

Cycle

a WALK that ends at the same VERTEX it began but only visits other vertices in the walk once e.g., 2-3-4-(2) in the diagram.

Related Terms

Cyclic and Cyclical - Adjectives describing an object with cycles e.g., cyclical network

Acyclic and Acyclical - Adjectives describing an object without cycles e.g., acyclical network

Loop - A loop is a cycle that only contains one vertex, the start/end vertex

Degree

The degree of a vertex is the number of edges connected to the vertex. For a directed network this includes edges into and out of the vertex. In the diagram, the degree of C is 4 and the degree of H is 2.

Directed Network

A directed network is a NETWORK in which each edge has a specified direction.

Edge

An edge is a connection between two VERTICES in a NETWORK.

Related Terms

Directed Edge - A directed edge is an edge with a specified direction of flow

Weighted Edge - A weighted edge is an edge with a specified weighting

Minimum Spanning Tree

A minimum spanning tree is a SPANNING TREE of a WEIGHTED NETWORK in which the sum of the weights of the included EDGES are minimised.

Related Concept

There can often be multiple minimum spanning trees of a cyclical and wieghted network. But, in the example at right, the purple lines represent the unique minimum spanning tree for this network.

Network

A network is a collection of VERTICES and EDGES representing the connection of elements.

Related Terms

Graph - Same as a network

Sub-network - A part of subset of a larger network

Path

A path is a WALK where no VERTICES or EDGES are repeated. For example, a possible path in the network shown to the right is b-c-d-a.

Shortest Path

A shortest path between two vertices can be thought of as a path of minimum weight.

There are often several shortest paths (all of equal length) between two given vertices.

For example, a shortest path in the diagram shown to the right is A-B-E-F-J and has weight 8.

Spanning Tree

A spanning tree is a sub-NETWORK of a larger CYCLIC network that connects all of the VERTICES of the full network without any cycles.

Related Concept

For a cyclic network, there are multiple spanning trees e.g., both the trees shown in red in the diagram are spanning trees of the full network.

Tree

A tree is a NETWORK that has no CYCLES.

Related Concept

For any set of more than 2 vertices, there are multiple trees that can connect all the vertices. The number of possible trees is determined by Cayley's Formula, n^(n-2). For example, the set of 6 vertices in the diagram can be joined by any of 1296 trees.

Vertex

A vertex is a point within a NETWORK, usually labelled.

Related Terms

Node - Same as a vertex

Vertices - Plural of vertex

Walk

A walk is a trip in a NETWORK travelling to through any number of VERTICES using any of the connecting EDGES. For example, a possible walk through the network shown at right is a-b-c-d-a-d.

Weighted Network

A weighted network is a NETWORK in which all edges carry a specified weight.