hazel defs Flashcards
Subgraph
a graph whose vertices and edges belong to the original graph
Weight
a number associated with an edge
Degree/Valency/Order
number of edges incident to a vertex
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
Cycle
a closed path
Connected Graph
a graph that has a path between all the vertices
Digraph
a graph that has edges with directions associated with them
Tree
connected graph with no cycles
Spanning Tree
a subgraph which includes all the vertices of the original graph and is also a tree
Minimum Spanning Tree
a spanning tree such that the total length of its arcs is as small as possible
Complete Graph
a graph in which each of the vertices is connected to every other vertex
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
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.
Matching
the pairing of some or all of the elements of one set to elements of the second set
Complete Matching
every member of one set of a bipartite graph is paired with a member of the other set
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)
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.
The purpose of dummies
- E.g. If activity D depends only on activity B but activity E depends on activities B and C.
- E.g. so that I and J are represented uniquely in terms of their end events.
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.
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.
Define traversable and semi traversable (eularian)
A Graph is Traversable if you can go over each edge once and only once, starting and finishing at the same vertex.
A Graph is semi-traversable if you can go over each edge once and only once starting and finishing at different vertices.
