Decision Maths: 2. Graphs And Networks

Question 1

What is a Graph

Answer 1

A graph consists of points (called vertices or nodes), which are connected by lines (edges or arcs)

Question 2

What is a Weighted Graph/Network

Answer 2

If a graph has a number associated with each edge (usually called it’s weight), then the graph is known as a weighted graph or network.

Question 3

What are Connected Graphs

Answer 3

Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.

Question 4

What is a Simple Graph

Answer 4

A simple graph is one which there are no loops and there is at most one edge connecting any pair of vertices.

Question 5

What is a Directed Graph

Answer 5

A directed graph is one in which the edges of the graph have a direction associated with them, the edges are known as directed edges. Directed graph is often abbreviated to digraph.

Question 6

What are Vertices/Nodes

Answer 6

The vertices/nodes are the points on a graph (A,B,C,D,E). This list is sometimes called the vertex set.

Question 7

What are the Edges/Arcs

Answer 7

The edges/arcs are the lines connecting vertices (AB,AC,AF…). This list is sometimes called the edge set

Question 8

What is a Subgraph

Answer 8

A subgraph of G is a graph, each of whose vertices belong to G and each of whose edges belongs to G. It is simply a part of the original graph.

Question 9

What the Degree or Valency of a Vertex (+How do we say if a Vertex is even or odd)

Answer 9

The degree, or valency, or order of a vertex is the number of edges incident (connected) to it.

(If a vertex has even degree we say it is even, similarly if the vertex has odd degree we say it is an odd vertex)

Question 10

If you have odd degrees, will you have an even or odd amount of them

Answer 10

If you have odd degrees, you’ll always have an even number of them.

Question 11

What is A Walk

Answer 11

A walk is a route through a graph along edges from one vertex to the next.

Question 12

What is A Path

Answer 12

A path is a walk in which no vertex is visited more than once

Question 13

What is A Trail

Answer 13

A trail is a walk in which no edge is visited more than once

Question 14

What is A Cycle

Answer 14

A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.

Question 15

What is A Hamiltonian Cycle

Answer 15

A Hamiltonian cycle is a cycle which includes every vertex

Question 16

What is A Loop

Answer 16

A loop is an edge which starts and finishes at the same vertex

Question 17

If a graph represented a telephone network, why would you want multiple edges going from one node to another?

Answer 17

So an organisation can make different calls at the same time.

Question 18

What is the Handshake Lemma

Answer 18

In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges, as a consequence, the number of odd vertices must be even. This result is known as the handshake lemma.

Question 19

Can you draw a graph with an odd number of odd vertices?

Answer 19

No, it’s impossible

Question 20

Example Question:

Graham is attempting to draw a graph which has vertices of the following orders.

2n-1, 2^n+2, n^2, 2n+1, 2^n-1

State a restriction on the value of n which would make the graph constructible

Answer 20

n has to be odd

(To make an even number of odd vertices)

Question 21

What is A Tree

Answer 21

A tree is a connected graph with no cycles

Question 22

What is a Spanning Tree

Answer 22

A spanning tree is a subgraph, which includes all the vertices and is a tree

Question 23

What is A Complete Graph

Answer 23

A complete graph is a graph in which every vertex is directly connected by a single edge to each of the other vertices.

Question 24

a) How many edges are required to drawn Kn of a Complete Graph

b) How many edges are required to draw K10

Answer 24

a) n(n-1) / 2 = 1/2n (n-1)

b) (10 x 9) / 2 = 45

Question 25

What is a Circuit

Answer 25

A walk in which the start vertex and the end vertex are the same

Question 26

What are Isomorphic Graphs

Answer 26

Isomorphic graphs are graphs which show the same information but may be drawn differently.

Question 27

How can you tell if 2 graphs are Isomorphic (the same)

Answer 27

• Numbers of nodes
• Numbers of Arcs
• Order/Valency of the nodes
• Check both edge sets of the graph match up

Question 28

What is an Adjacency Matrix

Answer 28

An adjacency matrix represents a graph or network

(in a table for example)

Question 29

What does each entry in a non-weighted graph in an adjacency matrix describe?

Answer 29

In a non weighted graph each entry describes the number of arcs joining the corresponding vertices

Question 30

What do the entries in a distance matrix in an adjacency matrix describe?

Answer 30

In a distance matrix the entries represent the weight of each arc, not the number of arcs.

Question 31

In a directed distance network, will the matrix be symmetrical or not?

Answer 31

In a directed distance network, the matrix will not be symmetrical.