Further Maths - Chapter 2 Graphs

Graph

points which are connected by lines

Points

verticies/nodes

Lines

edges/arcs

What is it called if a graph has a number associated with each edge?

weighted graph/network

Subgraph

a portion of a graph

The number of edges meet at a vertex

degree/valency/order

Walk

a route thorugh graph

Path

a walk where no vertex is visited more than once

Trail

a walk where no edge is visted more than once

Cycle

a walk where the end vertex is the same as the start vertex and no other vertex is visited more than once

Hamiltonian Cycle

a cycle that includes every vertex

Loop

an edge that starts and finishes at same vertex

Simple Graph

no loops and at least one edge connecting any pair of vertices

Diagraph

a directed graph

Tree

A connected graph with no cycles

Spanning tree

A subgraph which includes all the vertices of a graph and is also a tree

Complete graph

Every vertex is directly connected by a single edge to each of the other vertices

Isomorphic graphs

Graphs that show the same information but may drawn be differently

Planar graph

A graph drawn in a plane where no two edges cross

Planar graph algorithm