Graphs and networks - decision maths

Question 1

What is a walk?

Answer 1

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

Question 2

What is a path?

Answer 2

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

Question 3

What is a trail?

Answer 3

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

Question 4

What is a cycle?

Answer 4

A cycles 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 5

what is a hamilton cycle?

Answer 5

A cycle that includes every vertex

Question 6

What are vertices (or nodes)?

Answer 6

The points on a graph

Question 7

What are edges?

Answer 7

The lines between vertices

Question 8

What is a subgraph?

Answer 8

A graph that doesn’t include all the edges or vertices.

Question 9

What is the degree, valency or order of a vertext?

Answer 9

The number of edges attached to that vertex

Question 10

What is the difference between a connected and non-connected graph?

Answer 10

Connected graph has all it’s vertices connected by edges. Non connected doesn’t.

Question 11

What is a loop?

Answer 11

An edge that starts and finishes at the same vertex

Question 12

What is a simple graph?

Answer 12

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

Question 13

What is a directed graph or digraph?

Answer 13

A graph where the edges have a direction associated with them (represented by arrows).

Question 14

What is a tree?

Answer 14

A connected graph with no cycles

Question 15

What is a spanning tree?

Answer 15

A tree that includes all a graphs vertices

Question 16

What is a complete graph?

Answer 16

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

Question 17

What is an isomorphic graph?

Answer 17

A graph which show the same information as another graph but is drawn differently.

Question 18

What is an adjacancy matrix?

Answer 18

A matrix that provides information about the connections between the vertices in a graph (each entry inb an adjacency matrix describes the number of arcs joining the corresponding vertices.

Question 19

What is a distance matrix?

Answer 19

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

Question 20

What is Euler’s handshaking lemma?

Answer 20

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, including possibly zero.

Question 21

What is a eulerian graph?

Answer 21

A graph with nodes with all even order

Question 22

What is a semi eulerian graph?

Answer 22

A graph with only 2 odd nodes