Karteikarten
D1 Definitions
Karten in diesem Stapel (31)
- 1GraphA graph consists of vertices [nodes] which are connected by edges [arcs].
- 2SubgraphA subgraph is a part of a graph.
- 3Weighted graphA graph in which there is a number associated with each edge [its weight].
- 4Degree of valency/orderThe number of edges incident to a vertex.
- 5PathA 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.
- 6WalkA path in which you are permitted to return to vertices more than once.
- 7Cycle/circuitA closed ‘path’ i.e. the end vertex of the last edge is the start vertex of the first edge.
- 8ConnectedTwo vertices are ‘connected’ if there is a path between them. A graph is connected if all its vertices are connected.
- 9LoopAn edge that starts and finishes at the same vertex.
- 10Simple graphA graph in which there are no loops and not more than one edge connecting any pair of vertices.
- 11Digraph/Directed edgesA graph in which the edges have a direction associated with them
- 12TreeA connected graph with no cycles.
- 13Spanning treeA subgraph of a graph which includes all the vertices of the graph and is also a tree.
- 14Bipartite graphA graph consisting of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
- 15Complete graphA graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices, the connected graph is denoted kn.
- 16Complete bipartite graphA graph in which there are r vertices in set X and s vertices in set Y [denoted kr,s].
- 17Isomorphic graphsA graph showing the same information as another but which is drawn differently.
- 18Adjacency matrixA matrix which records the number of direct links between vertices.
- 19Distance matrixA matrix which records the weights on the edges. Where there is no weight, this indicated by
- 20Early event timeThe earliest time of arrival at the event allowing for the completion of al preceding activities.
- 21Late event timeThe latest time that the event can be left without extending the time needed for the project.
- 22Critical activityAn activity where any increase in its duration results in a corresponding increase in the duration of the whole project i.e. it has a total float of zero.
- 23Critical pathA path from the source node to the sink node which entirely follows critical activities. It is the longest path contained in the network.
- 24Total floatThe amount of time an activity may be delayed without affecting the duration of the project.
- 25MatchingA matching is the 1 to 1 pairing of some, or all, of the elements of one set, X, with elements of a second set, Y, in a bipartite graph.
- 26Maximal matchingA matching in which the number of arcs is as large as possible.
- 27Complete matchingA complete matching is the 1 to 1 pairing of all of the elements of one set, X, with elements of a second set, Y, in a bipartite graph.
- 28Alternating pathA 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
- 29The purpose of dummies:1.E.g. If activity D depends only on activity B but activity E depends on activities B and C.
2.To enable the unique representation of activities in terms of their end events. - 30Explain why there must always be an even [or zero] number of vertices with odd valency in every graph.Each arc has two ends and so will contribute to 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.
- 31Differences between Kruskal’s and Prim’s Algorithm:1. Kruskal’s algorithm always starts with the arc of lowest weight while Prim’s can start at any node.
2. Kruskal’s algorithm produces a MST in a ‘chaotic’ manner while Prim’s MST grows with linked arcs.
3. Unlike Kruskal’s algorithm, you do not have to check for cycles with Prim’s algorithm.
4. Prim’s algorithm can be applied to a distance matrix while Kruskal’s algorithm cannot.
Informationen
- Beschreibung
- Definitions for graphs etc in D1 AQA maths includes dummies and a couple of key points on Kruskal's algorithm and Prim's algorithm as well as why you should always have an even numbered amount of odd valencies
- Erstellt von
- Joseph Tedds
- Aufrufe
- 79
- Tags
- Bewertung