Scribd Logo
Upload

Welcome to Scribd!

  • 237 views

    Activity # 8 Mathematics of Graphs: (Shortest Distance)

    Uploaded by

    Huricane Sky
    This document contains an activity worksheet for a mathematics of graphs course. It includes multiple questions testing different graph concepts: 1) Finding Hamiltonian circuits and shortest distances in a weighted graph. 2) Identifying Eulerian circuits and walks in graphs. 3) Calculating chromatic numbers. 4) Drawing graph models to represent transportation networks and finding optimal routes between locations. The student must apply graph theory concepts like coloring, circuits, walks and routing to solve each problem.

    Copyright:

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

    Activity # 8 Mathematics of Graphs: (Shortest Distance)

    Uploaded by

    Huricane Sky
    237 views6 pages
    This document contains an activity worksheet for a mathematics of graphs course. It includes multiple questions testing different graph concepts: 1) Finding Hamiltonian circuits and shortest distances in a weighted graph. 2) Identifying Eulerian circuits and walks in graphs. 3) Calculating chromatic numbers. 4) Drawing graph models to represent transportation networks and finding optimal routes between locations. The student must apply graph theory concepts like coloring, circuits, walks and routing to solve each problem.

    Original Description:

    Notes

    Original Title

    _Activity08

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains an activity worksheet for a mathematics of graphs course. It includes multiple questions testing different graph concepts: 1) Finding Hamiltonian circuits and shortest distances in a weighted graph. 2) Identifying Eulerian circuits and walks in graphs. 3) Calculating chromatic numbers. 4) Drawing graph models to represent transportation networks and finding optimal routes between locations. The student must apply graph theory concepts like coloring, circuits, walks and routing to solve each problem.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    237 views6 pages

    Activity # 8 Mathematics of Graphs: (Shortest Distance)

    Uploaded by

    Huricane Sky
    This document contains an activity worksheet for a mathematics of graphs course. It includes multiple questions testing different graph concepts: 1) Finding Hamiltonian circuits and shortest distances in a weighted graph. 2) Identifying Eulerian circuits and walks in graphs. 3) Calculating chromatic numbers. 4) Drawing graph models to represent transportation networks and finding optimal routes between locations. The student must apply graph theory concepts like coloring, circuits, walks and routing to solve each problem.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 6

    Activity # 8 Mathematics of Graphs

    Name: Zsa Zsa C. Bautista TOTAL: 100 POINTS


    Direction. Show your work for each of the following. Submit in a PDF File on or before
    July 15, 2021 at 5:00 P.M.

    1. Find all Hamiltonian circuit starting at vertex A in the weighted graph. Then find
    the shortest distance. 10pts

    A-C-D-E-B-A A-C-B-E-D-A
    AC = 8 AC = 8
    CD = 2 CB = 1
    DE = 7 BE = 9
    EB = 9 ED = 7
    BA = 5 DA = 7
    TOTAL = 31 TOTAL = 32
    (shortest distance)

    2. Consider the figure below.


    a) Give 2 possible Eulerian circuit that starts and ends at vertex A. 10pts

    1. AJIAGFEDCEHBCIBA

    2. ABCDEFGHECIBHIJA
    b) Give 2 possible Eulerian walk. You can start at any vertex. 10pts

    1. CDECBAFD

    2. CBAFDECD

    3. Determine the chromatic number for each of the following. 5pts each

    a) b)
    Chromatic number: 2 Chromatic number: 5

    4. Solve the following problem.

    a) The table below shows the nonstop flights offered by an international airline.
    Draw a graph model to represent this information, where each vertex represents
    a country and an edge connects two vertices if there is a non-stop flight between
    the corresponding countries. 10pts

    South
    Korea Singapore China Australia Spain
    South Korea - no yes no yes
    Singapore no - yes yes no
    China yes yes - yes yes
    Australia no yes yes - yes
    Spain yes no yes yes -

    Answer:
    b) Lea wants to tour Asia. She will start and end her journey in Tokyo and visit
    Hongkong, Bangkok, Seoul, and Beijing. The airfares available to her between
    cities are given in the table below. Draw a weighted graph that represents the
    travel costs between cities and find a low-cost route. 20pts

    Tokyo Hongkong Bangkok Seoul Beijing


    Tokyo - $845 $1275 $470 $880
    Hongkong $845 - $320 $515 $340
    Bangkok $1275 $320 - $520 $365
    Seoul $470 $515 $520 - $225
    Beijing $880 $340 $365 $225 -

    Answers:

    Low-cost route: Tokyo – Seoul – Beijing – Bangkok – Hongkong – Toyko

    Tokyo to Seoul $470


    Seoul to Beijing $225
    Beijing to Bangkok $365
    Bangkok to HongKong $320
    HongKong to Tokyo $845
    Total: $2225
    c) Justin needs to visit the pet store, the shopping mall, the local farmer’s market,
    and the pharmacy. His estimated driving times (in minutes) between the locations
    are given in the table below. Draw a graph model that represents the table below
    and find two possible routes, starting and ending at home, that will help Justin
    minimize his total travel time. 20pts
    Pet Shopping Farmer's
    Home store mall market Pharmacy
    Home - 18 27 15 8
    Pet store 18 - 24 22 10
    Shopping mall 27 24 - 20 32
    Farmer's
    market 15 22 20 - 22
    Pharmacy 8 10 32 22 -

    Answers:

    1st Possible Route Minutes 2nd Possible Route Minutes


    Home to Farmer’s market 15 Home to Pharmacy 8
    Farmer’s market to shopping mall 20 Pharmacy to Pet store 10
    Shopping mall to Pet store 24 Pet store to Farmer’s market 22
    Pet store to Pharmacy 10 Farmer’s market to Shopping mall 20
    Pharmacy to home 8 Shopping mall to Home 27
    Total: 77 Total: 87

    d) Five charity organizations of Dumaguete City send trucks on various routes to


    pick up donations on different schools.

    Charity A covers SU, NORSU, and STI


    Charity B covers NORSU, FU, and AMA
    Charity C covers STI, ACSAT, and SPUD
    Charity D covers ACSAT, FU, and SU
    Charity E covers AMA, SPUD, and MDC

    Each charity has its truck travel down all three schools on its route on the same day, but
    no two charities wish to visit the same schools on the same day. Draw a graph model
    that represents the situation. Use graph coloring to design a schedule for the charities.
    Arrange their pickup routes so that no school is visited twice on the same day by
    different charities. The schedule should use the least possible number of days. 20pts
    Hint: Let the charity organizations represent the vertices.

    A B C D E
    A - Yes Yes Yes No
    B Yes - No Yes Yes
    C Yes No - Yes Yes
    D Yes Yes Yes - No
    E No Yes Yes No -

    Answers:
    The schedule should use at least 3 days.

    You might also like