Scribd Logo
Upload

Welcome to Scribd!

  • 415 views

    HW4

    Uploaded by

    당근으로만든무말랭이
    The document contains practice problems from a chapter on network flows. It lists 30 problems involving determining paths, cycles, trees, and spanning trees in networks; constructing minimal spanning trees; finding shortest routes using Dijkstra's and Floyd-Warshall algorithms; determining efficient message routes between geographical areas; and finding maximal and optimal flows in networks. The problems range from simple tasks like finding a path in a network to more complex problems involving algorithms for minimal spanning trees, shortest paths, and maximal flows.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    HW4

    Uploaded by

    당근으로만든무말랭이
    415 views5 pages
    The document contains practice problems from a chapter on network flows. It lists 30 problems involving determining paths, cycles, trees, and spanning trees in networks; constructing minimal spanning trees; finding shortest routes using Dijkstra's and Floyd-Warshall algorithms; determining efficient message routes between geographical areas; and finding maximal and optimal flows in networks. The problems range from simple tasks like finding a path in a network to more complex problems involving algorithms for minimal spanning trees, shortest paths, and maximal flows.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains practice problems from a chapter on network flows. It lists 30 problems involving determining paths, cycles, trees, and spanning trees in networks; constructing minimal spanning trees; finding shortest routes using Dijkstra's and Floyd-Warshall algorithms; determining efficient message routes between geographical areas; and finding maximal and optimal flows in networks. The problems range from simple tasks like finding a path in a network to more complex problems involving algorithms for minimal spanning trees, shortest paths, and maximal flows.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    415 views5 pages

    HW4

    Uploaded by

    당근으로만든무말랭이
    The document contains practice problems from a chapter on network flows. It lists 30 problems involving determining paths, cycles, trees, and spanning trees in networks; constructing minimal spanning trees; finding shortest routes using Dijkstra's and Floyd-Warshall algorithms; determining efficient message routes between geographical areas; and finding maximal and optimal flows in networks. The problems range from simple tasks like finding a path in a network to more complex problems involving algorithms for minimal spanning trees, shortest paths, and maximal flows.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 5

    OR 확정 과제4

    6-1) For each network in Figure 6.32, determine (a) a path, (b) a cycle, (c) a tree, and (d) a spanning
    tree.

    6-3) Draw the network defined by

    𝑁 = {1,2,3,4,5}

    𝐴 = {(1,2), (1,5), (2,3), (2,4), (3,4), (3,5), (4,3), (4,5), (5,2)}

    6-7) Solve Example 6.2-1 starting at node 6 (instead of node 1), and show that the algorithm
    produces the same solution. (아래에 Example 6.2-1 참고)

    6-10) Figure 6.34 gives the mileage of the feasible links connecting nine offshore natural gas
    wellheads with an inshore delivery point. Because wellhead 1 is the closest to shore, it is equipped
    with sufficient pumping and storage capacity to pump the output of the remaining eight wells to
    the delivery point. Determine the minimum pipeline network that links the wellheads to the delivery
    point.

    6-12) Electro produces 15 electronic parts on 10 machines. The company wants to group the
    machines into cells designed to minimize the “dissimilarities” among the parts processed in each
    cell. A measure of “dissimilarity,” 𝑑𝑖𝑗 , among the parts processed on machines 𝑖 and 𝑗 can be
    expressed as

    𝑛𝑖𝑗
    𝑑𝑖𝑗 = 1 −
    𝑛𝑖𝑗 + 𝑚𝑖𝑗

    Where 𝑛𝑖𝑗 is the number of parts shared between machines 𝑖 and 𝑗, 𝑚𝑖𝑗 is the number of parts
    that are used by either machine 𝑖 or machine 𝑗 only.

    The following table assigns the parts to machines:

    (b) Show that the determination of the cells can be based on the minimal spanning tree solution.

    (c) For the data given in the preceding table, construct the two- and three-cell solutions
    (*(b), (c)만 풀면 됩니다)

    6-18) The network in Figure 6.36 gives the distances in miles between pairs of cities 1,2,…, and 8.
    Use Dijkstra’s algorithm to find the shortest route between the following cities:

    (a) Cities 1 and 7.

    (b) Cities 1 and 6.

    (*(a), (b)만 풀면 됩니다.)

    6-21) In Example 6.3-5, use Floyd’s algorithm to determine the shortest routes between each
    of the following pairs of nodes: (아래에 Example 6.3-5 참고)

    (a) From node 5 to node 1.

    (b) From node 3 to node 5.

    (c) From node 1 to node 4.

    (d) From node 3 to node 2.


    6-23) The Tell-All mobile-phone company services six geographical areas. The satellite distances (in
    miles) among the six areas are given in Figure 6.39. Tell-All needs to determine the most efficient
    message routes that should be established between each two areas in the network.

    6-25) In Example 6.3-6, use LP to determine the shortest routes between the following pairs of
    nodes: (아래에 Example 6.3-6, 6.3-4 참고)

    (a) Node 1 to node 5.

    (b) Node 2 to node 5.

    (*Formulation만 하면 됩니다.)
    6-30) Determine the maximal flow and the optimum flow in each arc for the network in Figure 6.40.

    You might also like