# D1vocab

0.0 / 5

HideShow resource information

- Created by: S1mba
- Created on: 01-05-14 10:20

Complete matching

A matching where every member of one set is paired to a member of the other set.

1 of 25

Digraph

Graph in which all edges have a specified direction. (These are called directed edges)

2 of 25

Bipartite graph

2 distinct sets of vertices. Edges only join a vertex of one set to a vertex of the other set, not vertices within a set.

3 of 25

Minimum spanning tree/ Minimum connector

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

4 of 25

Matching

Is a one to one pairing of some or all of the elements of one set with elements of a second set. One to one means each element of the first set is paired with only one element of the second set.

5 of 25

Path

Finite sequence of edges, end vertex of one edge is the start vertex of the next edge. No vertex appears more than once.

6 of 25

Total float

Amount of time an activities can be delayed without affecting the duration of the project. Eg. F(a,b)=late(b)-early(a)-duration(a,b).

7 of 25

Degree/ Valency/ Order

The number of edges incident to a vertex. A vertex is odd/even if the degree is odd/even.

8 of 25

Cycle/ Circuit

Closed path. Closed means the end vertex of the final edge is the start vertex of the first edge.

9 of 25

Complete graph/ Connected graph

Graph in which all vertices are connected. Denoted Kn if it has n vertices.

10 of 25

Connected vertices

Vertices with a path between them.

11 of 25

Complete graph

A graph in which all of the vertices are connected to every other vertex.

12 of 25

Spanning tree

Sub graph which includes all vertices of the original graph. Is a tree, with no cycles.

13 of 25

Graph

Contains points (vertices/nodes) connected by lines (arcs or edges).

14 of 25

Subgraph of graph G

Is a graph, each of whose vertices belong to G and each of whose edges belongs to G.

15 of 25

Tree

Connected graph with no cycles.

16 of 25

Weighted graph/ Network

Graph with numbers associated with each edge.

17 of 25

Maximal matching

A matching in which the number of arcs is as big as possible.

18 of 25

Critical path

Path from source node to sink node. Which only follows critical activities. The longest path in the network.

19 of 25

Dummy activity

1) Activity _depends only on activity _ but activity _ depends on activities _&_. 2) To enable the unique representation of activities _&_ in terms of their end events.

20 of 25

Critical activity

An activity for which an increase in its duration results in a corresponding increase in the duration of the project. An activity with a float of zero.

21 of 25

Semi-traversible (semi-eulerian) graph

Graph with precisely two odd valences. The start and finish point of a traverse around the graph must be the odd vertices.

22 of 25

Alternating path

Path starting at an unmatched node from one set of a bipartite graph and finishing at an unmatched node from the other set. Using arcs alternately in and not in the in initial matching.

23 of 25

Non-traversible graph

A graph with more than two odd nodes.

24 of 25

Traversible (eulerian) graph

A graph which you can draw over all of the arcs exactly once without taking your pen of the paper. A graph with no odd nodes.

25 of 25

## Other cards in this set

### Card 2

#### Front

Graph in which all edges have a specified direction. (These are called directed edges)

#### Back

Digraph

### Card 3

#### Front

2 distinct sets of vertices. Edges only join a vertex of one set to a vertex of the other set, not vertices within a set.

#### Back

### Card 4

#### Front

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

#### Back

### Card 5

#### Front

Is a one to one pairing of some or all of the elements of one set with elements of a second set. One to one means each element of the first set is paired with only one element of the second set.

#### Back

## Similar Mathematics resources:

0.0 / 5

2.0 / 5

3.0 / 5

0.0 / 5

0.0 / 5

4.0 / 5

0.0 / 5

0.0 / 5

0.0 / 5

5.0 / 5

Teacher recommended

## Comments

No comments have yet been made