# D1 Definitions

HideShow resource information
• Created by: amyclaire
• Created on: 13-06-18 12:44
Subgraph
Subset of vertices and edges, part of graph
1 of 18
Degree/ valency
Number of arcs incident to a vertex
2 of 18
Path
Finite sequence of edges such that the end vertex of 1 edge is the start vertex of the next, no vertex appears more than once
3 of 18
Cycle
Closed path where end vertex of last edge is start vertex of first edge
4 of 18
Connected graph
Graph where all vertices connected
5 of 18
Simple graph
No loops, no more than one edge connecting each pair of vertices
6 of 18
Digraph
Edges have direction
7 of 18
Number of direct lines between vertices
8 of 18
Tree
Connected graph with no cycles
9 of 18
Eulerian
All valencies even
10 of 18
Traversable
Possible to travel along every arc just once without taking pen off paper
11 of 18
Total float
Amount of time an activity's start may be delayed without affecting duration of project
12 of 18
Spanning tree
Subgraph that is a tree and includes all vertices
13 of 18
Bipartite graph
2 sets of vertices X & Y, edges join X to Y not vertices within another set
14 of 18
Complete graph
Every vertex directly connected by an edge to each of other vertices
15 of 18
Isomorphic graph
Show same information but drawn differently
16 of 18
Alternating path
Starts at an unmatched node on one side of a bipartite graph and finishes at an unmatched node. Uses arcs that are alternately not in and in the initial matching
17 of 18
Critical path
Longest path from source to sink node
18 of 18

## Other cards in this set

### Card 2

#### Front

Number of arcs incident to a vertex

Degree/ valency

### Card 3

#### Front

Finite sequence of edges such that the end vertex of 1 edge is the start vertex of the next, no vertex appears more than once

### Card 4

#### Front

Closed path where end vertex of last edge is start vertex of first edge

### Card 5

#### Front

Graph where all vertices connected