Decision 1 Chapter 2

Question 1

Graph

Answer 1

A number of nodes which are connected by edges

Question 2

Subgraph

Answer 2

Part of a graph

Question 3

Weighted graph

Answer 3

A graph where each edge has a number associated with it

Question 4

The number of edges incident to a vertex (3 words)

Answer 4

Degree
Valency
Order

Question 5

Path

Answer 5

A finite sequence of edges such that the end vertex of one edge is the start vertex of the next and in which no vertex appears twice

Question 6

Walk

Answer 6

A path where you can visit each vertex more than once

Question 7

Cycle / Circuit

Answer 7

A path where the end vertex of the last edge is the start vertex of the first edge

Question 8

Connected vertices

Answer 8

If there is a path between them

Question 9

Connected graph

Answer 9

All vertices are connected

Question 10

Loop

Answer 10

An edge that starts and finishes at the same vertex

Question 11

Simple graph

Answer 11

No loops and not more than one edge connecting any pair of vertices

Question 12

Digraph

Answer 12

A graph where the edges have a direction

Question 13

Tree

Answer 13

A connected graph with no cycles

Question 14

Spanning tree

Answer 14

A subgraph which is also a tree

Question 15

Bipartite graph

Answer 15

Consists of two sets of vertices where only vertices from opposite sets may be connected

Question 16

Complete graph

Answer 16

Every vertex is directly connected to every other vertex

Question 17

Isomorphic graphs

Answer 17

Graphs that show the same information but are drawn differently

Question 18

Adjacency matrix

Answer 18

Records the number of direct links between vertices

Question 19

Distance matrix

Answer 19

Records the weights of edges