Karteikarten
D1 Keywords
Karten in diesem Stapel (26)
- 1AlgorithmSystematic process with precise instructions to find a solution to a problem
- 2Bipartite GraphGraph which can be divided into two subsets in such a way that each edge of a graph joins a vertex from one subset to a vertex in the other, but not to a vertex in the same subset
- 3Complete GraphGraph where each vertex is connected to every other vertex
- 4Complete Bipartite GraphBipartite graph where each vertex in one subset is connected to every other vertex in the other subset
- 5CyclePath that completes a loop and returns to its starting point
- 6Degree of a vertexNumber of edges connected to that vertex
- 7Directed NetworkNetwork in which there is a set direction of movement
- 8Eulerian CycleCycle that crosses every edge of a graph exactly once and returns to the start vertex
- 9Hamiltonian CycleCycle that passes through every vertex of a graph once and only once and returns to the start vertex
- 10NetworkGraph in which every edge has a value called a weight
- 11Minimum Spanning TreeSubgraph connecting all vertices with the minimum weight
- 12Simple GraphGraphs with no loops and not more than one pair of edges connecting any pair of vertices
- 13TreeConnected graph that contains no cycles
- 14Kruskal's AlgorithmBuilds a minimum spanning tree by adding one edge at a time, choosing the smallest arc each time and avoiding cycles
- 15Prim's AlgorithmBuilds a minimum spanning tree by adding one edge at a time to a connected graph, choosing the smallest connected arc each time and avoiding cycles
- 16Dijkstra's AlgorithmObtains the shortest route from A to B
- 17How do you find the shortest path?Working backwards from T, if Final Y - weight = Final X then XY is on the path
- 18Traversable GraphCan be drawn without removing your pen from the paper and without going over the same edge twice
- 19Hand-Shaking TheoremThe sum of the valencies of a graph is equal to twice the number of edges
- 20Route Inspection AlgorithmFinds a route of minimum weight that traverses every edge at least once and returns to the start vertex
- 21Critical ActivitiesActivities that must be started on time to avoid delaying the whole project
- 22FloatMaximum time by which an activity can be delayed without delaying the whole project
- 23Feasible RegionRegion within which the solution lies in a linear programming problem
- 24Maximum MatchingOptimal solution linking as many pairs as possible in a bipartite graph
- 25Complete MatchingMatching where every vertex in one subset is paired with a vertex in the other subset
- 26Alternating PathJoins an unmatched vertex in X to an unmatched vertex in Y
Is a path such that edges are alternately in and not in a matching
Informationen
- Beschreibung
- Karteikarten am D1 Keywords, erstellt von Nathan Hall am 13/04/2017.
- Erstellt von
- Nathan Hall
- Aufrufe
- 3
- Bewertung
Mehr zu Graph and Network Algorithms