Further Maths- Graphs and networks

Graph

A set of points that are connected by lines

Node

A vertex

Weighted graph

If there is a number associated with an edge

Valency

Order

Order

The number of arcs incident from a node

Walk

A route through the graph from one edge to the next

Path

Is a walk in which no vertex is visited more than once

Trail

Is a walk in which no edge is visited more than once

Cycle

Is a walk where the end vertex and start vertex are the same

Hamiliton Cycle

Is a cycle that includes every vertex

Loop

An edge that starts and finished at the same node

Simple Graph

Has no loops and each vertex is connected to another vertex only once

Connected graph

If all the vertices are connected

Digraph

A graph that has direction associated to it

Euler's handshaking lemma

In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges.

Tree

A connected graph with no cycles

Spanning Tree

a subgraph which includes all the vertices and is also a tree

Isomorphic

Two graphs showing the same information but drawn differently

completed graph

Is a graph where each vertex is connected to each of the other vertices by a single edge

Kn

A completed graph with n vertices

Degree

Order