Flashcards in hazel defs Deck (21):

1

## Subgraph

###
a graph whose vertices and edges belong to the original graph

2

## Weight

### a number associated with an edge

3

## Degree/Valency/Order

###
number of edges incident to a vertex

4

## 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 in which no vertex appears more than once

5

## Cycle

### a closed path

6

## Connected Graph

### a graph that has a path between all the vertices

7

## Digraph

### a graph that has edges with directions associated with them

8

## Tree

### connected graph with no cycles

9

## Spanning Tree

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

10

## Minimum Spanning Tree

### a spanning tree such that the total length of its arcs is as small as possible

11

## Complete Graph

### a graph in which each of the vertices is connected to every other vertex

12

## Bipartite Graph

### a graph which consists of two sets of vertices, where the edges only join vertices to the other set, not vertices within a set

13

## Alternating Path

###
- a path starting at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately ‘not in’ or ‘in’ the initial matching.

14

## Matching

###
the pairing of some or all of the elements of one set to elements of the second set

15

## Complete Matching

###
every member of one set of a bipartite graph is paired with a member of the other set

16

## Total Float

###
Total Float is the amount of time that an activity can be delayed from its early start date without delaying the project finish date.

Total float = (latest time) – (earliest time) – (duration)

17

## Explain why there must always be an even [or zero] number of vertices with odd valency.

###
• Each arc will add two to the total sum of the valencies of the whole graph.

• Therefore, the sum of the valencies is always even.

• Therefore, vertices with an odd number of valencies must exist in pairs.

• Therefore, there is always an even number of odd valencies.

18

## The purpose of dummies

###
1. E.g. If activity D depends only on activity B but activity E depends on activities B and C.

2. E.g. so that I and J are represented uniquely in terms of their end events.

19

##
Differences between kruskal and prime

###
1: For Kruskal’s algorithm you need to sort the edges into ascending order. For Prim’s

algorithm you do not.

2: For Kruskal’s algorithm you choose the shortest edge to start the tree. For Prim’s

algorithm you choose any vertex to start a tree.

3: For Kruskal’s algorithm you add edges to the tree. For Prim’s you add vertices to the

tree.

4: For Kruskal’s algorithm you need to check for cycles. For Prim’s algorithm you do not.

5: For Prim’s algorithm, the tree grows in a connected fashion. Kruskal’s algorithm may be

disconnected until the last edge is added.

6: Prim’s algorithm can be applied to a distance matrix. Kruskal’s algorithm cannot.

20

## Explain why it is not possible to transport the statues using fewer crates than 5 bins

### There are 5 items over half the bin size (30). No two of these 5 can be paired in a bin, so at least 5 bins will be required.

21