3700698
Description
Flashcards by ThalanirII, updated more than 1 year ago
|
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(n-1)/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. One-way paths |
| Eulerian Trail (Pronounced Oiler-ian) | 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 (n-1)!/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 |
| Semi-Eulerian | A non-closed Eulerian trail (doesn't finish at start). There must be exactly 2 odd-order nodes, with the rest even. The trail will begin at one odd-order 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 n-1 edges |
| Trail/Walk | A sequence of vertices that link up to each other through edges |
| Traversible Graph | Graph with an Eulerian/semi-Eulerian 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.