smc-4789-30-Cycle

Networks, SMB-015 MC

Consider the following four statements about the graph above:

- The graph is planar.
- The graph contains a cycle.
- The graph is connected.
- The graph contains an Eulerian trail.

How many of these statements are true?

Show Answers Only

`C`

Show Worked Solution

`text{Consider each statement:}`

`text{Graph is planar}\ -> \text{edges only meet at vertices (True)}`

`text{Graph contains a cycle}\ -> \text{multiple cycles exist (True)}`

`text{Graph is connected}\ -> \text{a path exists to connect any}`

`text{two vertices (True)}`

`text{Graph contains an Eulerian trail}\ -> \text{requires two (only)}`

`text{vertices of an odd degree (False)}`

`=> C`

Networks, SMB-011

A network diagram is drawn below.

Starting at vertex `Q`, identify all five different paths that end at vertex `S`. (2 marks)

--- 3 WORK AREA LINES (style=lined) ---
Starting at vertex `P`, identify four different cycles that exist in the network. (2 marks)

--- 3 WORK AREA LINES (style=lined) ---
Starting at vertex `P`, what is the total number of cycles that exist in the network. (1 mark)

--- 2 WORK AREA LINES (style=lined) ---

Show Answers Only

i. `text{Paths from}\ Q–S:`

`QS, QRS, QRPS, QPRS, QPS`

ii. `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any vertices.}`

`text{Possible cycles (any 4 from the following):}`

`PQRP, PQSRP, PQRSP, PQSP, PSRP`

`PSRQP, PSQRP, PSQP`

iii. `8\ \text{(see listed in part (ii))}`

Show Worked Solution

i. `text{Paths from}\ Q–S:`

`QS, QRS, QRPS, QPRS, QPS`

ii. `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any vertices.}`

`text{Possible cycles (any 4 from the following):}`

`PQRP, PQSRP, PQRSP, PQSP, PSRP`

`PSRQP, PSQRP, PSQP`

iii. `8\ \text{(see listed in part (ii))}`

Networks, SMB-010

Starting at vertex `A`, identify all the different paths that finish at vertex `D`, using only three edges. (2 marks)

--- 3 WORK AREA LINES (style=lined) ---
Starting at vertex `A`, identify a cycle route? (1 mark)

--- 1 WORK AREA LINES (style=lined) ---
Explain the difference between a cycle and a circuit route. (1 mark)

--- 2 WORK AREA LINES (style=lined) ---

Show Answers Only

i. `text{Three edge paths from}\ A–D:`

`ACED, ABCD, ABED, AECD`

ii. `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any.}`

`text{Possible cycles (many examples exist in this network):}`

`ABEA, ABCEA, ACBA, …`

iii. `text{A circuit is a path that begins and ends at the same vertex.}`

`text{A cycle begins and ends at the same vertex, without}`

`text{repeating any vertices.}`

Show Worked Solution

i. `text{Three edge paths from}\ A–D:`

`ACED, ABCD, ABED, AECD`

ii. `text{Cycle: a path that ends at the same vertex without}`

`text{repeating any.}`

`text{Possible cycles (many examples exist in this network):}`

`ABEA, ABCEA, ACBA, …`

iii. `text{A circuit is a path that begins and ends at the same vertex.}`

`text{A cycle begins and ends at the same vertex, without}`

`text{repeating any vertices.}`

Networks, SMB-009

Starting at vertex `A`, identify three different cycles in the above network. (2 marks)

--- 3 WORK AREA LINES (style=lined) ---
Starting at vertex `A`, how many different cycles exist in this network? (1 mark)

--- 2 WORK AREA LINES (style=lined) ---

Show Answers Only

i. `text{Possible cycles (select 3):}`

`ABECA, ABEDA, ACEBA, ACEDA, ADEBA, ADECA`

ii. `text{6 (see above)}`

Show Worked Solution

i. `text{Cycle definition: edges cannot be repeated, only first and last}`

`text{vertices can be be repeated.}`

`:.\ text{Possible cycles (select 3):}`

`ABECA, ABEDA, ACEBA, ACEDA, ADEBA, ADECA`

ii. `text{6 (see above)}`