# Graphs

### Description

names and definitions
Flashcards by ThalanirII, updated more than 1 year ago
 Created by ThalanirII over 8 years ago
13
0

## Resource summary

 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

### Similar

A level Computing Quiz
Biological Definitions
Love through the ages
Social Psychology As level
Biology AQA 3.2.5 Mitosis
AQA Biology 8.1 structure of DNA
Function and Structure of DNA
PSYA1 - attachment, AQA psychology
AQA Biology 12.1 cellular organisation
AS Biology Unit 1
Psychology subject map