D1: Graph Theory + Definitions

a mathematical model that consists of arcs/edges and nodes/vertices

a weighted graph i.e. a graph with numbers associated to its edges

list of all the vertices in a given graph

a list of all the edges in a given graph

A part of the original graph (vertices and edges also belong to original graph)

number of edges incident to it

a route through a graph along edges from one vertex to the next

a walk with no repeated vertices

a walk with no repeated edges

a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once (or a trail that starts and ends at the same vertex)

A cycle that visits every vertex of a graph

...there is a path between them

...all its vertices are connected

an edge that starts and finishes at the same vertex

the vertex the loop originates from has a degree of 2 and not 1 due to it. this is because the loop is incident at the vertex twice.

a graph with no loops or multiple edges between vertices

a graph with a direction associated with the edges

in any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges. As a consequence, the sum of the degrees must always be even.

to determine whether a graph can exist - if the sum of the degrees is odd, that implies the number of edges is not an integer which is impossible

an even amount of vertices with an odd degree

a simple connected graph with no loops or circuits

a tree which includes all the vertices of the graph

a graph where every vertex is directly connected by a single edge to each and every other vertex

Kₙ where n is the number of vertices in the graph

graphs that show the same information but are drawn differently

- they have the same number of vertices with the same degree

- the vertices are connected in the same way

- the vertices may have different labels as they are not the same graph but still an equivalence

a matrix that provides information about the connections between the vertices in a graph

the number of arcs joining two points

it counts as two arcs as they can go in either direction ∴ the entry would be 2

(it is a similar principle to how e.g. AB could be 1 ∴ BA would also be 1)

the matrix associated with a weighted graph

the weight of the arc joining two nodes

the smallest weight; this is because when an algorithm is applied to the matrix to e.g. find the shortest route, the least value is desired.

a spanning tree such that the total length of its edges is as small as possible

minimum connector

A trail that starts and ends at the same vertex and traverse every arc no more than once

A trail that traverses every arc no more than once, but doesn’t start and end at the same vertex

• all vertices are even

• connected

• contains a Eulerian circuit

• exactly two vertices are odd

• connected

• contains a semi-Eulerian circuit