D1 Definitions

  • 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
Adjacency matrix
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

Back

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

Back

Preview of the back of card 3

Card 4

Front

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

Back

Preview of the back of card 4

Card 5

Front

Graph where all vertices connected

Back

Preview of the back of card 5
View more cards

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all D1 resources »