A graph consists of vertices (nodes) which are connected by edges

1 of 27

Subgraph

Part of a graph

2 of 27

Weighted graph

A graph in which there is a number associated with each edge

3 of 27

Degree of valency

The number of edges incident to a vertex

4 of 27

Path

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

5 of 27

Cycle

A closed path i.e.the end vertex of the last edge is the starting vertex of the first edge

6 of 27

Connected

Two vertices are 'connected' if there is a path between them. A graph is connected if all of it's vertices are connected

7 of 27

Digraph

A graph in which the edges have a direction associated with them- edges are directed edges

8 of 27

Tree

A connected graph with no cycles

9 of 27

Spanning tree

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

10 of 27

Bipartite graph

A graph consisting of 2 sets of vertices, X and Y. the edges only join vertices in X to vertices in Y, not vertices within the same set

11 of 27

Complete graph

A graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices, the connected graph is denoted kn

12 of 27

Distance matrix

A matrix which records the weights on the edges, No weight is indicated by '-'

13 of 27

Minimum spanning tree

A spanning tree such that the total length of its arcs are as small as possible

14 of 27

Differences between Kruskal's and Prim's

Kruskal's always starts at the arc of lowest weight, Prim's can start at any node. Kruskals produces a minimum spanning tree is a chaotic manner, Prim's grows with linked arcs. Prim's algorithm does not have to be checked for cycles.

15 of 27

Eularian graph

All the valencies are even- graph is transversable

16 of 27

Semi-Eularian graph

Precisely 2 valencies are odd, the rest are even- semi-transversable

17 of 27

Early event time

The earliest time of arrival at an event allowing for the completion of all preceding events

18 of 27

Late event time

The latest time that an event can be left without extending the overall time of the project

19 of 27

Critical activity

An activity where any increase in it's duration results in a corresponding increase in the overall time.

20 of 27

Critical path

A path from the source node to the sink node which entirely follows critical activities. Longest path contained in the network

21 of 27

Total float

The amount of time an activity may be delayed without affecting the duration of the project

22 of 27

Purpose of Dummies

1. E.g. If activity D depends only on activity B, but activity E depends on activities B and C. 2. To enable the unique representation of activities in terms of their end events.

23 of 27

Matching

A one-to-one pairing of some or all of the elements of one set, X with another set Y in a bipartite graph

24 of 27

Maximal matching

a matching in which the number of arcs is as large as possible

25 of 27

Complete matching

1 to 1 pairing of all the elements in set X, with elements of set Y, in a bipartite graph

26 of 27

Alternating path

A path starting with an unmatched node on one set and finishing with an unmatched node on the other set. Uses arcs that are alternately 'in' and 'not in' from the initial matching

27 of 27

Other cards in this set

Card 2

Front

Part of a graph

Back

Subgraph

Card 3

Front

A graph in which there is a number associated with each edge

Back

Card 4

Front

The number of edges incident to a vertex

Back

Card 5

Front

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

## Comments

No comments have yet been made