Flashcards
D1 key definitions
Cards in this deck (22)
- 1GraphConsists of points (vertices or nodes) which are connected by lines (edges or arcs)
- 2SubgraphOf G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G
- 3Weighted graph or networkA graph that has a number associated with each edge (weight)
- 4Degree or Valency or OrderThe number of edges connected to it
- 5Sum of degrees2x number of edges (counting each end of each edge)
- 6PathA finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in whcih no vertex appears more than once
- 7WalkA path in which you are permitted to return to vertices more than once
- 8CycleA closed path, i.e. the end vertex of the last edge is the start vertex of the first edge
(R U V W T R) - 9DigraphA graph with directed edges
- 10LoopAn edge that start and finishes at the same vertex
- 11Simple graphA graph with no loops, and not having more than one edge connecting any pair of vertices
- 12TreeA connected graph with no cycles
- 13Spanning treeOf graph G is a subgraph which includes all the vertices of G and is also a tree
- 14Bipartite graphConsists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. (IF there are r vertices in X and s vertices in Y, then the graph is: K(r,s)
- 15Complete graphA graph in which every vertex is directly connected to each of the other vertices. If the graph has n vertices, the connected graph is denoted by Kn
- 16Isomorphic graphGraphs that show the same information differently
- 17Adjacency matrixRecords the number of direct links between vertices
- 18Distance matrixRecords the weights on the edges
- 19Minimum spanning tree (MST)A spanning tree such that the total length of its arcs is as small as possible. (MST is sometimes called a minimum connector)
- 20EulerianAll the valencies in the graph are even
- 21Semi-EulerianAll the valencies, except 2, are even
- 22TraversableCan travel along every arc just once without taking your pen from the paper
Information
- Description
- AS - Level Maths Flashcards on D1 key definitions, created by Ben C on 21/03/2017.
- Created by
- Ben C
- Views
- 4
- Tags
- Rating