Chapter 2 Vocab list

Question 1

Graph

Answer 1

collection of vertices & edges.

Question 2

Vertex/Node

Answer 2

the dots in a graph (usually where 2 or

more edges meet, but not necessarily).

Question 3

Edge/Arc

Answer 3

a line between two vertices.

Question 4

Tree

Answer 4

a graph with no cycles.

Question 5

Order (degree) of a vertex

Answer 5

the number of edges starting

or finishing at that vertex.

Question 6

Simple graph

Answer 6

a graph with no loops or multiple edges.

Question 7

A path

Answer 7

a route from one vertex to another which does not repeat any edge.

Question 8

A cycle

Answer 8

a route starting and finishing at the same vertex.

Question 9

Connected graph

Answer 9

a graph in which there is a route from

each vertex to any other vertex (i.e. the graph is in one part)

Question 10

Complete graph

Answer 10

a simple graph in which every pair of

vertices is connected by an edge.

Question 11

Bipartite graph

Answer 11

one in which the vertices are in two sets

and each edge has a vertex from each set.

Question 12

Planar graph

Answer 12

one which can be drawn with no edges

crossing.

Question 13

Sub graph

Answer 13

any set of edges & vertices taken from a

graph is a sub-graph.

Question 14

Di-graph

Answer 14

a graph in which the edges indicate direction.

Question 15

Incidence matrix

Answer 15

a matrix representing the edges in a

graph.

Question 16

Isomorphic graphs

Answer 16

shows same information but drawn differently

Question 17

Adjacency matrix

Answer 17

records number of direct links between verticies

Question 18

Distance matrix

Answer 18

records the weight on the edges.