Flashcards
Graphs
Flashcards do conjunto (18)
- 1Complete GraphA graph where every vertex is connected to every other vertex. Its total edges, (Kn)=n(n-1)/2 where n=no. of vertices
- 2Complete Matching GraphWhere all the vertices in one subset connect to all the vertices in another./
- 3Cycle / CircuitA closed path/trail with at least one edge
Closed = finishes at its start point - 4Degree/Order/ValencyNumber of edges connected to a vertex
- 5Directed Graph (Digraph)Has direction - e.g. One-way paths
- 6Eulerian 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
- 7Hamiltonian CycleA cycle/circuit/path/trail that visits every vertex. It has (n-1)!/2 permutations
- 8LoopAn arc beginning and ending on the same vertex. Loops contribute 2 to the arc count
- 9Minimum Spanning TreeA spanning tree with the minimum weight for the graph
- 10PathA trail where no vertex is visited more than once
- 11Planar GraphA 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 - 12Semi-EulerianA 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
- 13Simple GraphA graph with no loops, no multiple edges and every vertex is connected
- 14Spanning treeA tree that connects all the vertices, (n). It has n-1 edges
- 15Trail/WalkA sequence of vertices that link up to each other through edges
- 16Traversible GraphGraph with an Eulerian/semi-Eulerian trail
- 17TreeConnected graph with no cycles
- 18Weighted GraphA graph where numbers are linked with edges, representing time/distance/money etc