Graphs and networks

Question 1

What is a graph?

Answer 1

A collection of vertices and edges

Question 2

What is a vertex/node?

Answer 2

A point on a graph

Question 3

What is an edge/arc?

Answer 3

A line connecting two points on a graph

Question 4

What is a network?

Answer 4

A graph in which the edges have a weight (e.g. distance) associated with it

Question 5

What is a subgraph?

Answer 5

A graph in which all vertices and edges are also present in another larger graph

Question 6

What is the degree/valency/order of a vertex?

Answer 6

The number of edges incident to it

Question 7

What is a path?

Answer 7

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

Question 8

What is a walk?

Answer 8

A path in which it is permitted to return to vertices more than once

Question 9

What is a cycle/circuit?

Answer 9

A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge

Question 10

What does it mean for two vertices to be connected?

Answer 10

There exists a path between them

Question 11

What is a connected graph?

Answer 11

A graph in which all vertices are connected to each other

Question 12

What is a loop?

Answer 12

An edge that starts and finishes at the same vertex

Question 13

What is a simple graph?

Answer 13

A graph which has no loops and no pair of vertices being joined by more than one edge

Question 14

What is a digraph?

Answer 14

A graph in which the edges have a direction associated with them

Question 15

What is a tree?

Answer 15

A connected graph with no cycles

Question 16

What is a spanning tree?

Answer 16

A subgraph that is a tree and also contains all the vertices of the original graph

Question 17

What is a bipartite graph?

Answer 17

A graph consisting of two sets of vertices, X and Y. The edges only go between a vertex in X and a vertex in Y

Question 18

What is a complete graph?

Answer 18

A graph in which every vertex is directly joined to every other vertex

Question 19

How is a complete graph notated?

Answer 19

Kᵥ, where v is the number of vertices

Question 20

What is a complete bipartite graph?

Answer 20

A bipartite graph in which each vertex in one set is directly joined to every vertex in the other set

Question 21

How is a complete bipartite graph notated?

Answer 21

Kᵢ,ⱼ, where i is the number of vertices in set X and j is the number of vertices in set Y

Question 22

What is graph isomorphism?

Answer 22

The property of two graphs having a difference appearance but still showing the same information

Question 23

What is an adjacency matrix?

Answer 23

A matrix that records the number of edges linking vertices

Question 24

What is a distance matrix?

Answer 24

A matrix that records the distances between vertices

Question 25

In adjacency and distance matrices, which out of the row and the column represents the vertex that the edge is going from, and which represents the vertex that the edge is going to?

Answer 25

The row represents the vertex that the edge is going from, and the column represents the vertex that the edge is going to