Unit 4

Question 1

A cycle that visits all vertices exactly once is called…

Answer 1

A cycle that visits all vertices in the network exactly once is called a Hamiltonian cycle! It starts at a vertex, visits every other vertex exactly once and then returns to the starting vertex.

Question 2

True or False??
A graph is Hamiltonian if and only if it contains an even number of vertices.

Answer 2

It’s false! Unlike Eulerian graphs, there is no simple condition to determine if a graph is Hamiltonian. A graph is Hamiltonian if it contains a Hamiltonian cycle!

Question 3

True or False??
A Hamiltonian cycle doesn’t have to pass through every edge.

Answer 3

It’s true! A Hamiltonian cycle doesn’t have to pass through every edge. Instead, it only needs to hit every vertex exactly once. Only Eulerian circuits and trails need to pass through every edge exactly once.

Question 4

True or False??
A Hamiltonian graph cannot be Eulerian.

Answer 4

It’s false! A graph can be both Hamiltonian and Eulerian if it contains both a Hamiltonian cycle and an Eulerian circuit. This is possible if a walk passes through all of the vertices and edges in the cycle, before returning to the starting vertex.

Question 5

True or False??
A network must be either Hamiltonian or Eulerian.

Answer 5

It’s false! A graph can be neither Hamiltonian or Eulerian. This can happen when there are no walks that can pass through every vertex or edge exactly once.

Question 6

A graph is semi-Hamiltonian if it only contains a….

Answer 6

A graph is semi-Hamiltonian if it only contains a Hamiltonian path! Unlike a Hamiltonian graph, semi-Hamiltonian graphs don’t contain a Hamiltonian cycle. Instead, they have a Hamiltonian path, which is a path that hits every vertex exactly once, without starting and ending at the same vertex.

Question 7

A cycle that visits all vertices exactly once is called…

Answer 7

A cycle that visits all vertices in the network exactly once is called a Hamiltonian cycle! It starts at a vertex, visits every other vertex exactly once and then returns to the starting vertex.

Question 8

A graph is semi-Hamiltonian if it only contains a….

Answer 8

A graph is semi-Hamiltonian if it only contains a Hamiltonian path! Unlike a Hamiltonian graph, semi-Hamiltonian graphs don’t contain a Hamiltonian cycle. Instead, they have a Hamiltonian path, which is a path that hits every vertex exactly once, without starting and ending at the same vertex.

Question 9

A walk with no repeated edges is called a…

Answer 9

Trail

Question 10

True or False??

The direction of an edge is represented by an arrow.

Answer 10

True

Question 11

How do you find the sum of degrees?

Answer 11

The sum of the amount of directions each vertex has

Question 12

A connected planar graph has 11 vertices and 14 edges.
How many faces does it have?

Answer 12

5

Question 13

A graph is semi-Hamiltonian if it only contains a….

Answer 13

A graph is semi-Hamiltonian if it only contains a Hamiltonian path! Unlike a Hamiltonian graph, semi-Hamiltonian graphs don’t contain a Hamiltonian cycle. Instead, they have a Hamiltonian path, which is a path that hits every vertex exactly once, without starting and ending at the same vertex.

Question 14

A cycle that visits all vertices exactly once is called…

Answer 14

A cycle that visits all vertices in the network exactly once is called a Hamiltonian cycle! It starts at a vertex, visits every other vertex exactly once and then returns to the starting vertex.

Question 15

What are the dots that represent objects in a network called?

Answer 15

In a network, the dots that represent objects are called vertices! Another word for a vertex is a node.

Question 16

A graph is Eulerian if and only if…

Answer 16

A graph is Eulerian if and only if each vertex has an even degree! An Eulerian graph is a network containing an Eulerian circuit, a walk that starts and ends at the same vertex and visits every edge in the network once.

For this reason, all vertices in an Eulerian graph must have an even degree so the walk can visit each vertex via an incoming edge and travel to the next vertex via an outgoing edge.

Question 17

The repayments on a loan of $150,000 over a 20-year term at 9.6% p.a. are $1408.01 per month.
What is the balance owing at the end of 2 months?
Give your answer correct to the nearest cent.

Answer 17

First, let’s find the balance owing at the end of the first month.

We’re told that we have an initial loan balance of $150,000, paying an interest of 9.6% p.a. The monthly repayments are $1408.01 each.

To find the interest gained, we must first convert our interest rate into a monthly rate:

9.6% / 12
= 0.8%

150,000 × 0.008

=$1200

Our balance owing will just be the balance at the start of the month, plus the interest, less the monthly payment:

150,000 +1200 −1408.01
=$149,791.99

150,000+1200−1408.01
=$149,791.99

We now repeat this process to find the balance owing at the end of the second month.

Our interest will be:

149,791.99 × 0.008
=$1198.34 (nearest cent)

149,791.99 × 0.008
=$1198.34 (nearest cent)

Question 18

True or false?? The shortest path between two vertices is the path with the least number of edges.

Answer 18

False

Question 19

True or False??
The shortest path can be found using Kruskal’s algorithm or Prim’s algorithm.

Answer 19

It’s false! Kruskal’s algorithm and Prim’s algorithm are actually used to find the minimum spanning tree which connects all the vertices with the least total weight.

To find the shortest path between any two vertices, we would instead use trial and error or solve it by inspection.

Question 20

How do we find the shortest path between two vertices?

Answer 20

The shortest path from one vertex to another can be found using trial and error! Although there are formal algorithms that help us find the shortest path, we’ll only be using trial and error or solving by inspection in this course.