Keyterms

Question 1

Graph

Answer 1

Points (called vertices or nodes) connected by lines (edges or arcs)

Question 2

Weighted graph or network

Answer 2

A graph that has a number associated with each edge (usually called its edge)

Question 3

Subgraph

Answer 3

A graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph.

It is part of the original graph.

Question 4

Degree (or valency or order) of a vertex

Answer 4

The number of edged that meet at that vertex

Question 5

Even degree /odd degree

Answer 5

A degree of a vertex that is even / odd

Question 6

Walk

Answer 6

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

Question 7

Path

Answer 7

A walk in which no vertex is visited more than once

Question 8

Trail

Answer 8

A walk in which no edge is visited more than once

Question 9

Hamiltonian cycle

Answer 9

A cycle that includes every vertex

Question 10

Connected vertices/graph

Answer 10

Two vertices where there is a path between them/ all vertices are connected

Question 11

Loop

Answer 11

An edge that starts and finishes at the same vertex

Question 12

Simple graph

Answer 12

A graph in which there are no loops and there is at most one edge connecting any pair of vertices.

Question 13

Directed edges

Answer 13

The edges of the graph that have a direction associated with them

Question 14

Directed graph (or digraph)

Answer 14

A graph with directed edges

Question 15

Tree

Answer 15

A connected graph with no cycles

Question 16

Spanning tree

Answer 16

A subgraph which includes all vertices of the original graph and is also a tree

Question 17

Complete graph

Answer 17

A graph in which every vertex is directly connected by a single edge to each of the other vertices

Question 18

Isomorphic graphs

Answer 18

Graphs which show the same information but may be drawn differently

Question 19

Adjacency matrix

Answer 19

A matrix in which each entry describes the number of arcs joining the corresponding vertices

Question 20

Distance matrix

Answer 20

A matrix in which the entries represent the weight of each arc, not the number of arcs.

Question 21

Minimum spanning tree (MST)

Answer 21

A spanning tree such that the total length of its arcs (edges) is as small as possible

Question 22

Eulerian graph/network

Answer 22

Any connected graph whose vertices are all even

Question 23

Eulerian circuit

Answer 23

A trail that includes every edge and starts and finishes at the same vertex.

Question 24

Semi-eulerian graph

Answer 24

One which contains a trail that includes every edge but starts and finishes at different vertices

—> any connected graph with exactly 2 odd verices

Question 25

Algorithm

Answer 25

A finite sequence of step-by-step instructions out to solve a problem

Question 26

Flow chart

Answer 26

The shape of each box tells you about its function