# Graph Theory

HideShow resource information
Degree
The number of edges connected to a vertex
1 of 18
Directed Graph
A graph with directed edges
2 of 18
Complete Graph (Kn)
N vertices with each vertex joined to each other vertex once
3 of 18
Bipartite Graph
Has two sets of vertices and the edges only connect vertices from one set to the other
4 of 18
Trail
A sequence of edges that only includes edges once
5 of 18
Path
A trail that only uses a vertex once
6 of 18
Cycle
A closed path
7 of 18
Hamiltonian Cycle
A cycle that visits all vertices
8 of 18
Eulerian Trail
A trail using all the edges of a graph, for it to exist, the degree of each vertex must be even
9 of 18
Semi - Eulerian Trail
A graph that uses all the edges but has a non-closed trail (different start and finish points)
10 of 18
Tree
A connected graph with no cycles
11 of 18
Spanning Tree
A simple connected graph with one fewer edge than total vertices
12 of 18
Minimum Spanning Tree
A spanning tree with minimum weight
13 of 18
Kruskal's Algorithm
Adds edges to a tree in order of size
14 of 18
Prim's Algorithm
Adds the nearest vertex to a current tree
15 of 18
Dijkstra's Algorithm
Enables the shortest path between two points to be found
16 of 18
Traversable Graph
A graph that can be drawn without taking the pen from the paper and without going over an edge twice
17 of 18
Chinese Postman Route
Each edge must be walked along at least once, the least pairings of odd vertices must be walked along on one extra occasion.
18 of 18

## Other cards in this set

### Card 2

#### Front

A graph with directed edges

Directed Graph

### Card 3

#### Front

N vertices with each vertex joined to each other vertex once

### Card 4

#### Front

Has two sets of vertices and the edges only connect vertices from one set to the other

### Card 5

#### Front

A sequence of edges that only includes edges once