consists of vertices (nodes) which are connected by edges (arcs)
A part of a graph, small section of it
A connected graph with no cycles
All nodes connected
Consists of two sets of vertices, X and Y, edges only join vertices between X and Y, not vertices within a set.
A graph in which every vertex is directly connected by an edge to each of the other vertices.
Complete bipartite graphs
Every vertex of set X is connected by an edge to every vertex of set Y
Minimum Spanning Tree
A tree that contains all of its vertices and is of minimum weight
All vertices have an even order (valency/ degree)
Two vertices have odd order (valency)
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
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.