A full network investigation

For a connected planar graph, which first step finds the number of faces?

Switch between the two drawing arrangements. Follow A–C–D–E in each. Check that every labelled endpoint pair is unchanged; a line crossing is not a new junction unless a vertex is marked

What stays the same when only the drawing positions change?

Preserve the model while changing the drawing

The reused explorer preserves endpoints when vertices move; it does not compute shortest paths or minimum connectors. For the investigations below, use the stated weights, not drawn lengths

1. 1Include the outer face For a connected planar graph, Euler's formula counts the infinite outer face as well as the enclosed regions \(\displaystyle v+f=e+2\)
2. 2Use the degree sum The sum of all vertex degrees is twice the number of edges \(\displaystyle \sum\deg(v)=2e\)
3. 3Use odd vertices for Euler routes In a connected graph, zero odd vertices allows a circuit and two odd vertices give the endpoints of an open trail \(\displaystyle o=0\Rightarrow\text{circuit},\quad o=2\Rightarrow\text{open trail}\)
4. 4Keep optimisations separate A shortest path joins two specified vertices, while a minimum spanning tree reaches every vertex \(\displaystyle \text{shortest path}:A\to D,\quad \text{MST}:V(G)\)

Construct the network and its adjacency representations

A hypothetical community site has six service sheds A–F. Underground conduits may follow existing two-way corridors AB, BC, CD, DE, EF, FA, AC and AD only. Installation costs, in hundreds of dollars, are respectively 4,2,3,5,6,12,7,10. Assume these additive costs include all construction for each link and remain fixed. Corridors can be walked in either direction, but cost weights do not represent walking distances or times. Separately, a one-way service uses only A→B, B→C and A→C.

1. 1Construct and explain Draw the undirected weighted network from the description, stating vertex, edge and weight meanings. Redraw it without changing any endpoint pair. Produce a labelled adjacency table in row-source/column-destination order A,B,C,D,E,F, using 1 for an available direct link and 0 otherwise. Keep this unweighted table distinct from the cost record. Explain whether the graph is simple, connected and planar; count vertices, edges and degrees. Use Euler’s relation to derive faces including the outer face, not an unverified rendered crossing count
2. 2Compare the directed model Draw the separate three-stop digraph and construct its labelled adjacency table in order A,B,C with the same explicit row-source convention. Explain the A-to-C and C-to-A entries, direct versus indirect reachability, and the number of two-edge A-to-C walks. Do not apply undirected parity or connector procedures to this different directed model
3. 3Record your independent construction Before opening the model response, choose the model and method and save your own labelled diagram, adjacency record, complete algorithm trace, tool formulas or commands, independent checks and written conclusion. Diagrams and complete external adjacency tables are self/teacher-reviewed, not app-captured whole-matrix responses

Model response: Construct the network and its adjacency representations

Compare the entire representation and argument. A checked scalar or chosen option is not the complete independent investigation

1. 1Exact unweighted representation With rows and columns A,B,C,D,E,F, the adjacency rows are A:(0,1,1,1,0,1), B:(1,0,1,0,0,0), C:(1,1,0,1,0,0), D:(1,0,1,0,1,0), E:(0,0,0,1,0,1), F:(1,0,0,0,1,0). The table is symmetric with zero diagonal; costs belong in a separate table keyed by endpoint pair. A-to-E is not a direct link although E is reachable. This is a simple connected graph with six vertices, eight edges and degrees (4,2,3,3,2,2); the degree sum 16 equals twice the edge count
2. 2Planarity and faces Place A,B,C,D,E,F in order around a hexagon and draw AC and AD inside. The two diagonals share A and need no other intersection, establishing a planar representation. For this connected planar graph, f=e−v+2=8−6+2=4, including the outer face. A differently arranged drawing could show apparent crossings without changing the graph; only marked junctions count as vertices. The model diagram below is not a scale map
3. 3Separate directed representation The directed adjacency rows are A:(0,1,1), B:(0,0,1), C:(0,0,0). Entry row A,column C is 1, but row C,column A is 0. A reaches C directly and via B; C cannot return to A. Exactly one two-edge walk goes from A to C, namely A→B→C. This row-source convention is declared for these adjacency tables; do not silently import the source-column transition convention from Chapter 11.

In this conduit network, what does the edge weight 12 on FA mean?

Given information

\(\displaystyle (\deg A,\deg B,\deg C,\deg D,\deg E,\deg F)=(4,2,3,3,2,2)\)

Find the number of edges from the complete degree list

Given information

\(\displaystyle v=6,\quad e=8,\quad\text{connected planar graph}\)

Derive the number of faces, including the outer face

Using row-source adjacency, which statement is correct for the separate digraph?

Given information

\(\displaystyle A\to B,\quad B\to C,\quad A\to C\quad\text{only}\)

Count the two-edge walks from A to C in the directed model

Construct every-edge and every-vertex routes

Use the undirected corridor network from the construction task. An inspection must walk every corridor exactly once; another visit must reach every shed once and return to the start. These are existence/construction tasks, not claims of shortest walking distance because no walking lengths are supplied

1. 1Select and construct Choose the relevant Eulerian or Hamiltonian notion for each requirement. Determine whether an every-edge closed circuit exists and, if not, give an open every-edge trail with its required endpoints. Produce an explicit every-vertex closed cycle. Verify each consecutive connection and count used edges or visited vertices according to the relevant definition
2. 2Separate what is proved Explain why the open Eulerian trail may revisit vertices and why the Hamiltonian cycle need not use every edge. Give a walk that repeats an edge and classify why it is not a trail. Do not use the absence of an Euler circuit to infer the absence of a Hamiltonian cycle
3. 3Record your independent construction Before opening the model response, choose the model and method and save your own labelled diagram, adjacency record, complete algorithm trace, tool formulas or commands, independent checks and written conclusion. Diagrams and complete external adjacency tables are self/teacher-reviewed, not app-captured whole-matrix responses. The excluded automatic whole-matrix family stays excluded. Actual tool operation and reports are not automatically marked

Model response: Construct every-edge and every-vertex routes

Compare the entire representation and argument. A checked scalar or chosen option is not the complete independent investigation

1. 1Eulerian construction and verification Only C and D have odd degree. Hence no closed every-edge Eulerian circuit exists, but an open Eulerian trail must start at one and end at the other. One trail is C–B–A–C–D–A–F–E–D. Its successive edges are CB,BA,AC,CD,DA,AF,FE,ED: exactly the eight available edges, each once. A and other vertices may be revisited; edge repetition is the prohibited feature here
2. 2Hamiltonian construction and comparison A–B–C–D–E–F–A is a Hamiltonian cycle: each of the six vertices appears once before returning to A, and every step is an available edge. It omits AC and AD, which is permitted. Thus this graph has a Hamiltonian cycle even though it has no Eulerian circuit. A–B–C–B is a valid walk but not a trail because edge BC is traversed twice, once in each direction; it is also not a path because B repeats

Given information

\(\displaystyle (\deg A,\deg B,\deg C,\deg D,\deg E,\deg F)=(4,2,3,3,2,2)\)

How many odd-degree vertices determine the open Eulerian endpoints?

In the network with vertices A–F and edges AB, BC, CD, DE, EF, FA, AC and AD, which requirement is met by A–B–C–D–E–F–A?

Choose and verify shortest-path and connector methods

The site now needs either a least-cost installed path from A to E, or a minimum-cost connected installation reaching all six sheds. Use the original costs in hundreds of dollars with no extra fees. Choose a method suited to each objective rather than treating the two totals as interchangeable

1. 1Produce the full Dijkstra record Apply Dijkstra from A. Record every permanent vertex, all tentative distance labels after each relaxation and the predecessor of each final label. Recover the least-cost A-to-E path and check its sum independently. Compare the least-cost A-to-F path with the path between those vertices inside the final minimum connector
2. 2Produce and verify Prim traces Apply Prim from A, listing the complete eligible cut at each step, the selected edge, reached set and running total. Repeat from F. Verify that each final graph has six vertices, five edges, connectedness and no cycle. Explain why a cheap edge detached from the current tree is not eligible. Use a separate enumeration of spanning trees or an explicit cut argument to verify optimality, and record the tool operations actually used
3. 3Record your independent construction Before opening the model response, choose the model and method and save your own labelled diagram, adjacency record, complete algorithm trace, tool formulas or commands, independent checks and written conclusion. Diagrams and complete external adjacency tables are self/teacher-reviewed, not app-captured whole-matrix responses. The excluded automatic whole-matrix family stays excluded. Actual tool operation and reports are not automatically marked

Model response: Choose and verify shortest-path and connector methods

Compare the entire representation and argument. A checked scalar or chosen option is not the complete independent investigation

1. 1Complete Dijkstra label record Start A=0 and all other labels unknown/infinite. After making A permanent, tentative labels in order B,C,D,E,F are 4(A),7(A),10(A),∞,12(A). After B: C=6(B), D=10(A), E=∞, F=12(A). After C: D=9(C), E=∞, F=12(A). After D: E=14(D), F=12(A). After F: E remains 14(D), since 12+6=18 is worse. Finally make E permanent. Permanent order is A,B,C,D,F,E; final labels in A,B,C,D,E,F order are (0,4,6,9,14,12). Predecessors are (none,A,B,C,D,A)
2. 2Recover and independently check Tracing E←D←C←B←A gives A–B–C–D–E, total 4+2+3+5=14 units, or $1400. The direct A–D–E alternative costs 15 and A–F–E costs 18. A–F itself is the least-cost A-to-F path at 12, whereas the A-to-F path in the minimum connector below costs 20. A minimum connector does not minimise every pairwise route. With positive weights, any repeated-vertex detour can be removed to reduce cost, so exhaustive simple-path enumeration is an independent check
3. 3Prim from A: every eligible cut From {A}, eligible AB4,AC7,AD10,AF12: take AB, total4. From {A,B}, BC2,AC7,AD10,AF12: take BC, total6. From {A,B,C}, CD3,AD10,AF12: take CD, total9. From {A,B,C,D}, DE5,AF12: take DE, total14. From {A,B,C,D,E}, EF6,AF12: take EF, total20. The selected edges AB,BC,CD,DE,EF form one connected acyclic graph with five edges. At each step the cheapest crossing edge is uniquely identified; the cut property justifies including it in a minimum connector
4. 4Prim from F and tool verification From {F}, EF6,FA12: take EF, total6. Then DE5,FA12: take DE, total11. Then CD3,AD10,FA12: take CD, total14. Then BC2,AC7,AD10,FA12: take BC, total16. Then AB4,AC7,AD10,FA12: take AB, total20. A detached BC2 was not eligible at the first step from F. Both starts give the same unique minimum connector, costing $2000. For a reproducible spreadsheet, store From,To,Cost and a reached flag for each endpoint; mark eligibility with =(reachedFrom<>reachedTo), choose the minimum eligible cost, update reached flags and record the row before repeating. For Dijkstra, record candidate=currentDistance+edgeCost and replace a temporary label only when smaller. A separate exhaustive tool can test every five-edge subset for connectedness and total cost; record actual commands and outputs, not merely the supplied trace

Given information

\(\displaystyle AB=4,\ BC=2,\ CD=3,\ DE=5,\ EF=6,\ FA=12,\ AC=7,\ AD=10\)

Find the least cost from A to E in hundreds of dollars under the original model

Given information

\(\displaystyle d(C)=6,\ w(CD)=3,\ d(D)\text{ previously }=10\)

After relaxing through C, find D’s improved tentative label

Given information

\(\displaystyle AB=4,\ BC=2,\ CD=3,\ DE=5,\ EF=6,\ FA=12,\ AC=7,\ AD=10\)

Starting Prim at F, give the first chosen edge weight

Given information

\(\displaystyle AB=4,\ BC=2,\ CD=3,\ DE=5,\ EF=6,\ FA=12,\ AC=7,\ AD=10;\quad1\text{ cost unit}=\$100\)

Find the complete minimum connector cost in dollars

Revise assumptions and report the changed decisions

Reconsider the same site in three separate scenarios, each starting from the original network. First, corridor FA is unavailable. Second, corridor DE is unavailable instead. Third, all original links are available but each installed link carries an extra fixed $200 setup fee in addition to its original cost. Do not combine the scenarios

1. 1Reconstruct and verify For each closure, reconstruct the permitted edge set and recalculate the least-cost A-to-E and A-to-F paths and the minimum connector. Do not merely delete an edge from a previous answer and assume the result remains connected. For the fee scenario, update every weight in matching units and investigate which original optimum changes. Explain why equal per-edge additions affect all spanning trees equally but not all paths equally
2. 2Write a qualified recommendation Write a short report choosing a path or all-site connector according to the stated purpose, comparing original and revised costs, giving complete witness routes/edge sets and explaining assumptions. Identify information absent from this model, such as capacities, reliability, permits and actual surveyed costs. Explain why minimum total installation cost does not imply redundancy or shortest walking routes
3. 3Record your independent construction Before opening the model response, choose the model and method and save your own labelled diagram, adjacency record, complete algorithm trace, tool formulas or commands, independent checks and written conclusion. Diagrams and complete external adjacency tables are self/teacher-reviewed, not app-captured whole-matrix responses. The excluded automatic whole-matrix family stays excluded. Actual tool operation and reports are not automatically marked

Model response: Revise assumptions and report the changed decisions

Compare the entire representation and argument. A checked scalar or chosen option is not the complete independent investigation

1. 1Two distinct closures Without FA, the original connector AB,BC,CD,DE,EF remains feasible and minimum at 20 units. A-to-E remains 14, but A-to-F must use A–B–C–D–E–F at 20. Without DE instead, E can only connect via EF; a minimum connector is AB,BC,CD,AF,FE, total 4+2+3+12+6=27. The shortest A-to-E path is then A–F–E at 18 and A-to-F remains 12. Deleting DE from the original tree alone would disconnect it; adding AF repairs the separation
2. 2A fixed fee can change the shortest path but not this connector The extra $200 is 2 cost units per selected edge. Every spanning tree on six vertices has five edges, so every tree total rises by 10; the unique minimum edge set stays AB,BC,CD,DE,EF, now costing 30 units or $3000. Paths have different edge counts: original A–B–C–D–E becomes 14+4×2=22, while A–D–E becomes 15+2×2=19 and A–F–E becomes 18+2×2=22. Re-running Dijkstra or enumerating all simple paths verifies A–D–E as the new minimum, costing $1900. Selecting the fewest edges without checking weights would still not be a general method
3. 3Example conditional report For a connection only from A to E, the original minimum installation is A–B–C–D–E at $1400; for all sheds, use AB,BC,CD,DE,EF at $2000. If FA closes, choose A–B–C–D–E at $1400 for A to E, A–B–C–D–E–F at $2000 for A to F, and AB,BC,CD,DE,EF at $2000 for all sheds. If DE closes, choose A–F–E at $1800 for A to E, A–F at $1200 for A to F, and AB,BC,CD,AF,FE at $2700 for all sheds. Under a $200 per-link fee, choose A–D–E at $1900 for the first purpose and retain the same tree at $3000 for the second. The complete positive-cost edge list, correct units, graph constraints, independent path/tree checks and Prim/Dijkstra traces support these conditional decisions. No tree has redundant cycles, so a fault-tolerant design requires a different objective and further information. These assumed costs do not establish actual prices, physical feasibility, permission, capacity, reliability or travel times; external evidence is needed before a real installation decision

Given information

\(\displaystyle AB=4,\ BC=2,\ CD=3,\ EF=6,\ FA=12,\ AC=7,\ AD=10\)

Find the minimum connector total in hundreds of dollars when DE alone is unavailable

Given information

\(\displaystyle AB=4,\ BC=2,\ CD=3,\ DE=5,\ EF=6,\ FA=12,\ AC=7,\ AD=10;\quad1\text{ unit}=\$100\)

With a $200 setup fee on every installed link, find the least A-to-E installation cost in dollars

Given information

\(\displaystyle W_{\min}=20\text{ cost units},\quad6\text{ vertices},\quad\$200\text{ extra per edge},\quad1\text{ unit}=\$100\)

Find the minimum all-site connector cost in dollars after the same per-link fee

What does the minimum connector establish?