Chapter 2: Graphs and Networks

Question 1

Graph

Answer 1

A series of points connected with lines

Question 2

Network

Answer 2

A graph which has a quantity

Question 3

Vertex Set

Answer 3

A set of vertices, written in {…..}

Question 4

Edge Set

Answer 4

A set of edges, written in {…..}

Question 5

Order/Valency/Degree of a vertex

Answer 5

How many connections a point has

Question 6

Subgraph

Answer 6

A section of graph that has come from the original graph, it can be a small section or the whole thing

Question 7

Cycle

Answer 7

A graph/subgraph which starts and ends at the same point

Question 8

Path

Answer 8

A sequence of edges where each vertex is used once

Question 9

Walk

Answer 9

A path where you can use vertices more than once

Question 10

Connected Graph

Answer 10

A graph where every point has an edge to at least one other point

Question 11

Loop

Answer 11

An edge that starts and finishes at the same point, Valency of 2

Question 12

Simple Graph

Answer 12

No loops, no more than one edge between two points

Question 13

Digraph

Answer 13

A graph that has direction

Question 14

Tree

Answer 14

A connected graph with no cycles

Question 15

Spanning tree

Answer 15

A subgraph which is a tree

Question 16

Bipartite Graph

Answer 16

Two sets of vertices, where edges only join between sets and not within their own

Question 17

Complete graph

Answer 17

A graph where every point is connected to every other point

Question 18

Isomorphic graphs

Answer 18

Graphs which have the same information, ie. they are the same, but are shown differently

Question 19

Adjancency Matrix

Answer 19

A matrix which records the number of direct links between vertices

Question 20

Distance matrix

Answer 20

A matrix which records the weights on edges