Graph Theory / Networks - Year 12 Maths Applications ATAR

Network / Graph

A set of points called vertices connected by a set of lines called edges

Vertices

The Junctions or End Points

Edges / Arcs

The connections connecting Vertices

Faces / Regions

Separated areas, including the outside of a network

Vertex

Singular of Vertices

Even Vertex

Has an even number of edges coming off it

Odd Vertex

Has an odd number of edges coming off it

Traverseability 1

A network is traverseable if it can be drawn without lifting the pen off the page, and without going over the same edge twice but can have repeated vertices

Traversability 2

A network with more than 2 odd vertices is not traversable, and if a network has 0 odd vertices any vertex can be the beginning but will also be the end.

Traversability 3

With 2 odd vertices, either odd vertex can be the start, and the other will be the end.

Loop

An edge that starts and finishes at the same vertex

Multiple Edges

Two or more edges connecting the same two vertices

Undirected Graph

Has no direct edges (shown by arrows)

Directed Graph

Has directed edges or arcs which is indicated by arrows on all edges

Weighted Graph

Each edge contains information (for example cost, distance, time, etc)

Simple Graph

A network that is undirected, unweighted, has no loops and no multiple edges.

Simple Directed Graph

A simple graph with directions shown by arrows

Simple Weighted Graph

A simple graph with weights / information on all edges

Walk

A sequence of vertices in which there is an edge from each vertex to the next vertex where vertices and edges may be repeated

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 where all the edges and vertices are different, with no repeats

Cycle / Closed Path

A path that starts and finishes at the same vertex

Open Path

A path that starts and finishes at different vertices

Trail

A walk with no repeated edges where vertices can be repeated

Closed Trail

A trail that starts and finishes at the same vertex

Open Trail

A trail that starts and finishes at different vertices

Trails + Paths Note

All paths are trails but not all trails are paths

Connected Vertices

It's possible to travel from one vertex to every other vertex through edges

Adjacent Vertices

Two vertices that are directly connected by an edge.

Connected Networks

All vertices can be connected with no isolated vertices

Disconnected Networks

All vertices cannot be connected and contains isolated vertices

Bridge

An edge in a connected graph that, when removed, leaves the graph disconnected

Complete Graph / Complete Network

Each vertex is connected to every other vertex

Kn

A complete graph with 'n' vertices

Minimum Number of Edges

To calculate, use n-1 in connected graphs

Maximum Number of Edges

To calculate, use n(n-1)/2 in complete graphs