Graph Theory 0.0 / 5 ? MathematicsGraphs and transformationsA2/A-levelAQA Created by: Daisy MaltonCreated on: 29-01-16 13:06 Degree The number of edges connected to a vertex 1 of 18 Directed Graph A graph with directed edges 2 of 18 Complete Graph (Kn) N vertices with each vertex joined to each other vertex once 3 of 18 Bipartite Graph Has two sets of vertices and the edges only connect vertices from one set to the other 4 of 18 Trail A sequence of edges that only includes edges once 5 of 18 Path A trail that only uses a vertex once 6 of 18 Cycle A closed path 7 of 18 Hamiltonian Cycle A cycle that visits all vertices 8 of 18 Eulerian Trail A trail using all the edges of a graph, for it to exist, the degree of each vertex must be even 9 of 18 Semi - Eulerian Trail A graph that uses all the edges but has a non-closed trail (different start and finish points) 10 of 18 Tree A connected graph with no cycles 11 of 18 Spanning Tree A simple connected graph with one fewer edge than total vertices 12 of 18 Minimum Spanning Tree A spanning tree with minimum weight 13 of 18 Kruskal's Algorithm Adds edges to a tree in order of size 14 of 18 Prim's Algorithm Adds the nearest vertex to a current tree 15 of 18 Dijkstra's Algorithm Enables the shortest path between two points to be found 16 of 18 Traversable Graph A graph that can be drawn without taking the pen from the paper and without going over an edge twice 17 of 18 Chinese Postman Route Each edge must be walked along at least once, the least pairings of odd vertices must be walked along on one extra occasion. 18 of 18
Comments
No comments have yet been made