Unit 3 Maths Applications: Network Terminology

Traversable network

A network that can be traced over without taking the pen off paper and without repeating edges

Weighted network

Shows distances or amounts on the edges

Directed edges (digraphs)

Have arrows indicating the directions that each edge can go

Simple graphs

Undirected, unweighted graphs with no loops and no multiple edges

Simple digraph

A digraph with no loops and no multiple edges

Complete graph

A graph where each point connects to every other vertex

Walk

A sequence of vertices where each vertex is joined to the next vertex in the sequence by an edge

Closed walk

A walk that starts and finishes at the same vertex

Open walk

A walk that starts and finishes at different vertices

Path

A walk with no repeated edges or vertices, other than ending at the starting vertex

Closed path

Also known as a cycle. A path that starts and finishes at the same vertex

Open path

A path that starts and finishes at different vertices

Length of a walk

The number of edges in a walk

Trail

A walk with no repeated edges

Bridge

Connects two subgraphs together

Traversable networks have...

1. All vertices have an even number order, OR

2. Exactly 2 off orders from 2 vertices

Start and ending vertices

1. If even: start anywhere and end at the same point

2. If 2 are odd: start at one odd number and end at the other odd

Euler's rule

Applies to planar networks (can be drawn without overlapping edges):

Vertices + faces = edges + 2

Semi-Eularian graph

Two vertices are off, forms an open trail

Eularian graphs

All vertices are even, forms a closed trail

Semi-Hamiltonian graph

Open path

Hamiltonian graph

Closed cycle, no repeated vertices