Consists of points (vertices or nodes) which are connected by lines (edges or arcs)
1 of 17
Subgraph
Is a graph G, each of whose vertices belongs to G and each of whose edges belongs to G
2 of 17
Weighted graph/network
A graph which has a number associated with each edge
3 of 17
Degree/valency
The number of edges incident to a vertex, a vertex is odd if it has odd degree
4 of 17
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 of 17
Cycle (circuit)
A closed path, ie the end vertex of the last edge is the start vertex of the first edge
6 of 17
Connected graph
All vertices are connected
7 of 17
Directed edges
The edges of a graph have a direction associated with them
8 of 17
Digraph
A graph with directed edges
9 of 17
Tree
A connected graph with no cycles
10 of 17
Spanning tree
A subgraph which includes all the vertices of a graph and is also a tree
11 of 17
Minimum spanning tree
A spanning tree such that the total length of its arcs is as small as possible
12 of 17
Complete graph
A graph in which each of the vertices is connected to every other vertex
13 of 17
Total float
Latest start time - early start time - duration of event
14 of 17
Bipartite graph
Consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
15 of 17
Matching
The pairing of some or all of the elements of one set, X, with elements of a second set, Y.
16 of 17
Complete matching
A matching where every member of X is paired with a member of Y
17 of 17
Other cards in this set
Card 2
Front
Is a graph G, each of whose vertices belongs to G and each of whose edges belongs to G
Back
Subgraph
Card 3
Front
A graph which has a number associated with each edge
Back
Card 4
Front
The number of edges incident to a vertex, a vertex is odd if it has odd degree
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 in which no vertex appears more than once
Comments
No comments have yet been made