Scribd
Upload
442 views2 pages

Problem Set (Math of Graphs)

1. Draw a weighted graph representing airfare costs between cities Nicole wants to visit in Asia. Use the greedy algorithm to find a low-cost route. 2. Use the edge-picking algorithm to find a low-cost route for Nicole between the same Asian cities. 3. Represent a map as a graph and find the minimum number of colors needed to color the graph. 4. Students volunteered for films in groups but there are only 3 cameras. Use graph coloring to schedule camera lending over the fewest days so each group can film with full participation.

Uploaded by

HERNANDO REYES
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
442 views2 pages

Problem Set (Math of Graphs)

1. Draw a weighted graph representing airfare costs between cities Nicole wants to visit in Asia. Use the greedy algorithm to find a low-cost route. 2. Use the edge-picking algorithm to find a low-cost route for Nicole between the same Asian cities. 3. Represent a map as a graph and find the minimum number of colors needed to color the graph. 4. Students volunteered for films in groups but there are only 3 cameras. Use graph coloring to schedule camera lending over the fewest days so each group can film with full participation.

Uploaded by

HERNANDO REYES
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

PROBLEM SET

(Mathematics of Graphs)

1. Nicole wants to tour Asia. She will start and end her journey in Tokyo
and visit Hong Kong, Bangkok, Seoul, and Beijing. The airfares (in US
Dollars) available to her between cities are given in the table. Draw a
weighted graph that represents the travel costs between cities and use
the greedy algorithm to find a low-cost route.

Tokyo Hong Kong Bangkok Seoul Beijing


Tokyo --- 845 1275 470 880
Hong Kong 845 --- 320 515 340
Bangkok 1275 320 --- 520 365
Seoul 470 515 520 --- 225
Beijing 880 340 365 225 ---

2. Use edge-picking algorithm to find a low-cost route for the traveler in


item 1.

3. Represent the map by a graph and find a coloring of the graph that
uses the smallest possible number of colors.
4. Students in a film class have volunteered to form groups and create
several short films. The class has three digital video cameras that
may be checked out for one day only, and it is expected that each
group will need the entire day to finish shooting. All members of each
group must participate in the film they volunteered for, so a student
cannot work on more than one film on any given day.

Film 1 will be made by Renz, Anika, and Ryan.

Film 2 will be made by Ynah, Sophia, and Renz.

Film 3 will be made by KC, Renz, and Sophia.

Film 4 will be made by Joyce, Jasmine, and Abby.

Film 5 will be made by Jasmine, Ryan, and Ynah.

Film 6 will be made by Anika, KC, and Abby.

Use graph coloring to design a schedule for lending the cameras, using the
smallest possible number of days, so that each group can shoot its film and
all members can participate.

You might also like