Created by ThalanirII
over 8 years ago


Question  Answer 
Complete Graph  A graph where every vertex is connected to every other vertex. Its total edges, (Kn)=n(n1)/2 where n=no. of vertices 
Complete Matching Graph  Where all the vertices in one subset connect to all the vertices in another./ 
Cycle / Circuit  A closed path/trail with at least one edge Closed = finishes at its start point 
Degree/Order/Valency  Number of edges connected to a vertex 
Directed Graph (Digraph)  Has direction  e.g. Oneway paths 
Eulerian Trail (Pronounced Oilerian)  A trail that uses every edge of the graph. (The graph is Eulerian/Traversible). If the graph is Eulerian, each node must have even order 
Hamiltonian Cycle  A cycle/circuit/path/trail that visits every vertex. It has (n1)!/2 permutations 
Loop  An arc beginning and ending on the same vertex. Loops contribute 2 to the arc count 
Minimum Spanning Tree  A spanning tree with the minimum weight for the graph 
Path  A trail where no vertex is visited more than once 
Planar Graph  A graph which can be drawn without any arcs intersecting. There is a complicated way of deciding whether a given graph is planar, but otherwise experiment by stretching the arcs to remove intersections 
SemiEulerian  A nonclosed Eulerian trail (doesn't finish at start). There must be exactly 2 oddorder nodes, with the rest even. The trail will begin at one oddorder node, and end at the other one 
Simple Graph  A graph with no loops, no multiple edges and every vertex is connected 
Spanning tree  A tree that connects all the vertices, (n). It has n1 edges 
Trail/Walk  A sequence of vertices that link up to each other through edges 
Traversible Graph  Graph with an Eulerian/semiEulerian trail 
Tree  Connected graph with no cycles 
Weighted Graph  A graph where numbers are linked with edges, representing time/distance/money etc 
Want to create your own Flashcards for free with GoConqr? Learn more.