UNIT 4 GENERAL MATH QCAA

Finance, Graphs + Networks, Networks and decision mathematics

edge

lines on a graph

vertex

the points on the graph

single graph/network

each pair of vertices is connected by at most one edge

complete graph/network

each vertex connects to every other vertex

connected graph/network

possible to travel between any given pair of vertices

disconnected graph/network

at least one vertex which can’t be reached

directed graph (digraph)

only move along the edges in one way by arrows

undirected graph

edges can be travelled in either direction

degree

number of edges connected to a vertex

subgraph

a small part of any graph

loop

edge which travels to and from one vertex

planar

when graph is re-drawn to have no crossing edges

face

flat surfaces in graph including the entire thing as a whole

walk

any route taken through a network, including routes that repeat edges and vertices

closed walk

a route taken through a network that starts and ends at the same vertex

trail

a walk in which no edges are repeated

path

a walk in which no vertices are repeated, except possibly the start and finish

cycle

a path beginning and ending at the same vertex

closed trail

a trail beginning and ending at the same vertex

Eulerian trail

connected graph which allows you to start a a vertex, traverse each edge only once and return to vertex where started

semi-Eulerian

connected graph which allows start at a vertex and traverse each edge only once without returning to the start

Hamiltonian cycle

includes every vertex exactly once, which ending at initial vertex

semi-Hamiltonian cycle

includes every vertex exactly once, but ends at a vertex other than the starting vertex

weighted graphs

attach value to edges

trees

are simple connected with no circuits

spanning trees

subgraphs that include all the vertices of the original graphs

prims algorithm

1. vertex with the lowest weighted edges

2. progressively select lowest edges

3. continue until all are selected