Chapter 2

Question 1

A graph

Answer 1

Consists of vertices (nodes) which are connected by edges (arcs)

Question 2

A subgraph

Answer 2

Is part of a graph

Question 3

A weighted graph

Answer 3

Has a number associated with each edge (its weight)

Question 4

The degree, valency or order of a vertex

Answer 4

Is the number of edges incident to it

Question 5

A path

Answer 5

Is a finite sequence of edges, such that the end vertex of one edge of the sequence is the start vertex of the next, and in which no vertex appears more than once

Question 6

A walk

Answer 6

Is a path in which you are permitted to return to vertices more than once

Question 7

A cycle (circuit)

Answer 7

Is a closed path, so the end vertex of the last edge is the start vertex of the first edge

Question 8

Two vertices are connected if

Answer 8

There is a path between them

Question 9

A graph is connected if

Answer 9

All its vertices are connected

Question 10

A loop

Answer 10

Is an edge that starts and finishes at the same vertex

Question 11

A simple graph

Answer 11

Is one in which there are no loops and not more than one edge connecting a pair of vertices

Question 12

Directed edges (in a digraph)

Answer 12

If the edges have a direction associated to them

Question 13

A tree

Answer 13

A connected graph with no cycles

Question 14

A spanning tree

Answer 14

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

Question 15

A bipartite graph

Answer 15

Consists of two sets of vertices, X and Y. The edges can only join vertices in X to vertices in Y, not vertices within a set

Question 16

A complete graph

Answer 16

Is a graph in which every vertex is directly connected by an edge to each other vertices. If the graph has n vertices the connected graph is denoted kn

Question 17

A complete bipartite graph

Answer 17

Is a graph in which there are r vertices in set X and s vertices in set Y (denoted k r,s)

Question 18

Isomorphic graphs

Answer 18

Show the same information but are drawn differently

Question 19

An adjacency matrix

Answer 19

Records the number of direct links between vertices

Question 20

A distance matrix

Answer 20

Records the weights on the edges. Where here is no weight, this is indicated by ‘-‘