Graphs

Description

names and definitions
ThalanirII
Flashcards by ThalanirII, updated more than 1 year ago
ThalanirII
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
Show full summary Hide full summary

Similar

A level Computing Quiz
Zacchaeus Snape
Biological Definitions
Yamminnnn
Love through the ages
acasilva001
Social Psychology As level
Gurdev Manchanda
Biology AQA 3.2.5 Mitosis
evie.daines
AQA Biology 8.1 structure of DNA
Charlotte Hewson
Function and Structure of DNA
Elena Cade
PSYA1 - attachment, AQA psychology
T W
AQA Biology 12.1 cellular organisation
Charlotte Hewson
AS Biology Unit 1
lilli.atkin
Psychology subject map
Jake Pickup