Decision 1 Definitions EDEXCEL AS MATHS 3.5 / 5 based on 2 ratings ? MathematicsNetworks, algorithms and problem solvingASEdexcel Created by: amywhitt163Created on: 03-05-14 21:15 Graph Consists of points (called vertices or nodes) which are connected by lines (edges or arcs) 1 of 20 Degree/Valency/Order if a vertex The number of edges incident to it. 2 of 20 Traversable A graph is traversable if it is possible to traverse (travel along) every arc just once without taking your pen from the paper. 3 of 20 Network A graph whose edges have a numerical value (weight). 4 of 20 Directed Graph (Digraph) Travelling in one direction along an edge. 5 of 20 Path A 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. 6 of 20 Walk A path in which you are permitted to return to vertices more than once. 7 of 20 Cycle or Circuit A closed "path" 8 of 20 Loop An edge that starts and finishes at the same vertex. 9 of 20 Simple graph A graph where there are no loops and doesn't have more than one edge connecting any pair of vertices. 10 of 20 Subgraph Part of the original graph. 11 of 20 Tree A connected graph with no cycles. 12 of 20 Spanning tree A subgraph that contains all of the vertices of the original graph and is also a tree. 13 of 20 Minimum spanning tree (MST) A spanning tree such that the total length of its arcs is as small as possible. 14 of 20 Bipartite graph Two sets of nodes. Arcs may connect nodes from different sets, but never from the same set. 15 of 20 Complete matching If both sets have n nodes, a complete matching is a matching with n arcs. 16 of 20 Maximal matching Matching in which the number of arcs is as large as possible. 17 of 20 Critical activity Any increase in its duration results in a corresponding increase in the duration of the whole project. 18 of 20 Critical path A path from the source node to the sink node which entirely follows critical activities. A critical path is the longest path contained in the network. 19 of 20 At each node on a critical path... The early event time is equal to the late event time. 20 of 20
Comments
No comments have yet been made