Decision Maths definitions

Exact definitions required for specific terms in the D1 exam.

HideShow resource information
• Created by: Stephanie
• Created on: 17-05-12 09:19

graph

consists of vertices (nodes) which are connected by edges (arcs)

1 of 12

subgraph

A part of a graph, small section of it

2 of 12

Tree

A connected graph with no cycles

3 of 12

spanning tree

All nodes connected

4 of 12

Bipartite graph

Consists of two sets of vertices, X and Y, edges only join vertices between X and Y, not vertices within a set.

5 of 12

Complete Graph

A graph in which every vertex is directly connected by an edge to each of the other vertices.

6 of 12

Complete bipartite graphs

Every vertex of set X is connected by an edge to every vertex of set Y

7 of 12

Minimum Spanning Tree

A tree that contains all of its vertices and is of minimum weight

8 of 12

Eulerian

All vertices have an even order (valency/ degree)

9 of 12

Semi- Eulerian

Two vertices have odd order (valency)

10 of 12

hand shaking lemma ( why even n.o of vertices with

Each arc has two ends so will contribute 2 to the sum of valencies in the graph. The sum of the valencies is equal to the number of arcs multiplied by 2.   Therefore the sum of the valencies must be even                                                     Any odd numbers must appear in pairs                                                                     Even number of odd valencies

11 of 12

Dummy activity

An activity of zero duration used to show a logical relationship in the arrow diagramming method. Dummy activities are used when logical relationships cannot be completely or correctly described with regular activity arrows. Dummies are shown graphically as a dashed line headed by an arrow.

12 of 12