D1 Edexcel Definitions

Front 1

Connected Graph

Back 1

All pairs of vertices are connected by a path

Front 2

Tree

Back 2

Connected Graph with no cycles

Front 3

Spanning Tree

Back 3

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

Front 4

Minimum Spanning Tree

Back 4

A spanning tree with the total lenght of the arcs being as small as possible

Front 5

Graph

Back 5

Consists of points connected by lines

Front 6

Valency/Degree

Back 6

Of a vertex is the number of edges incident to it

Front 7

Subgraph

Back 7

Of G is a graph each of whose vertices and edges belong to G

Front 8

Network

Back 8

A graph which has numbers (weight) associated with each edge

Front 9

Path

Back 9

A finite sequence of edges such that the end vertex of one edge is the start vertex of the next, with no vertex appearing more than once

Front 10

Cycle

Back 10

A closed path, I.e. the end vertex of the last edge is the start vertex of the first edge

Front 11

Matching

Back 11

Pairing of some or all of the elements in one set with elements of a second set

Front 12

Bipartite Graph

Back 12

Consists of 2 sets of vertices X and Y. The edges only join vertices in X to vertices in Y and vice vera

Front 13

Euler's Hand-Shaking Lemma

Back 13

Each arc has two ends so will contribute two valancies to the whole graph.

Therfore, the sum of the valancies= 2 x the number of arcs.

So the total degree of the network I'd always even and so any off valancies must occur in pairs

Front 14

Alternating Path

Back 14

Path from one unmatched vertex in one set to unmatched vertex in another set which alternates between using arcs in/not in the initial matching