D1 Flashcards
Bipartite graph
Graph consisting of 2 distinct vertices X and Y, where arcs can only join a vertex in X to a vertex in Y
Path
Finite sequence of edges, such that the end vertex of one edge is the start vertex of the next, and in which no vertex appears more than once, and there are no cycles.
Alternating path
Path from an unmatched vertex in X to an unmatched vertex in Y which alternately uses arcs in and not in the matching
Matching
The one to one matching of some elements of X with elements of Y
Complete matching
The one to one matching between all elements of X onto Y
The difference between Prim’s and Kruskal’s
In Prim:
The tree grows in a connected way
The nearest unattached vertex is added
Easy to use when a network is given in matrix form
There is no need to check for cycles
In Kruskal:
The shortest arc is added unless it completes a cycle
Complete/Connected graph
When all pairs of a graph’s vertices are connected
Tree
A connected graph with no cycles, loops or multiple edges
Spanning tree/Subgraph
A tree that includes all of the vertices of the graph
Minimum spanning tree/minimum connector
A spanning tree of minimum total length
Why is it impossible to draw a network with an odd number of odd vertices
Each arc contributes 2 to the sum of degrees, so this sum must be even. Therefore there must be an even (or 0) number of vertices of odd degree.
Valency
Number of arcs incident to a vertex.
Cycle
A closed path, where the end vertex of the last edge is the start vertex of the first edge
Loop
An edge that starts and finishes at the same vertex
Total float
The amount of time an activity may be delayed without affecting the duration of the project
