Y1 - Decision - C2 - Graphs & Networks

Question 1

2 What is a graph?

Answer 1

A finite number of vertices (or nodes) connected by edges (or arcs)

Question 2

2 What is a weighted graph? What is it also known as?

Answer 2

A graph that has numbers assigned to each edge, also called a network

Question 3

2 What is a tree?

Answer 3

A connected graph with no cycle

Question 4

2 What is a subgraph?

Answer 4

A graph whose vertices and edges belong to another graph but it is only part of the original

Question 5

2 What is a walk?

Answer 5

A route through a graph along edges from one vertex to another

Question 6

2 What is a path?

Answer 6

A walk in which no vertex is visited more than once

Question 7

2 What is a trail?

Answer 7

A walk in which no edge is visited more than once

Question 8

2 What is a cycle? What is it also known as?

Answer 8

A walk in which the end vertex is the same as the starting vertex (also a closed path)

Question 9

2 What is a Hamiltonian Cycle?

Answer 9

A cycle in which all vertices are visited

Question 10

2 What does it mean if a graph is connected?

Answer 10

If all the vertices are joined to the graph

Question 11

2 What is a loop?

Answer 11

An edge that starts and finishes at the same vertex

Question 12

2 What is a simple graph?

Answer 12

A graph with no loops and where there is at most one edge connecting any pairs of vertices

Question 13

2 What is a digraph?

Answer 13

A graph where edges have a direction

Question 14

2 What is a spanning tree?

Answer 14

A subgraph which includes all original vertices that is also a tree

Question 15

2 What is the expression for the number of edges in a spanning tree for a connected graph of n vertices?

Answer 15

n-1

Question 16

2 What is a complete graph?

Answer 16

Every vertex is connected to each other by a single edge (think k1, k2, k3, …)

Question 17

2 What is the expression for the number of Hamiltonian cycles in a complete graph with n vertices?

Answer 17

((n-1)!)/2

Question 18

2 What is an isomorphic graph?

Answer 18

A pair of graphs which shows the same information but are drawn differently

Question 19

2 What is an adjacency matrix?

Answer 19

A table describing the number of arcs joining the corresponding vertices

Question 20

2 What is a distance matrix?

Answer 20

A table in which the entries represent the weight of each arc, not the number of arcs

Question 21

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

Answer 21

The number of edges coming out of the vertex

Question 22

2 What is the Handshake Lemma?

Answer 22

In any undirected graph, the sum of the degrees of vertices is equal to 2x the number of edges - therefore the number of odd vertices must be even