離散數學›Ch6 圖論第 17 題／共 34 題
17. 平面圖、Euler公式、girth
#LS-06-017中平面圖Euler公式girth
- (10%) A network engineer is designing a fault-tolerant routing backbone for a data-center fabric. The backbone consists of 20 routers, arranged physically in a cylindrical grid: There are 4 horizontal layers ("rings"), each containing 5 routers. Horizontally, each layer forms a 5-router cycle (i.e., the leftmost and rightmost routers are connected). Vertically, each of the 5 columns also forms a 4-router cycle (i.e., the top and bottom switches are connected). Thus, every router has degree 4: two connections within its horizontal ring, and two within its vertical ring. Determine whether this cylindrical multi-ring backbone can be embedded on a flat PCB without wiring intersections. Justify your answer using only Euler's formula and girth-based edge bounds. In graph theory, the girth of an undirected graph is the length of the shortest cycle contained in the graph.
📄 成大115
▤完整推導請見《WH 資工筆記 · 離散數學》Ch6 圖論