Ged102-a14-module-6.docx

GED102/A14 NAME: CASTRO, Christian John R.

Assigned Number: 10

1. Which graph is Hamiltonian?

Graph 2 is Hamiltonian. 2. The cost of flying between various European cities is shown in the following table. Use both the greedy algorithm and the edge-picking algorithm to find a low-cost route that visits each city just once and starts and ends in London. Which route is more economical?

Answer: start

London, England (A)

Berlin, Germany (B)

Vienna, Austria (F)

Paris, France (C)

Madrid, Spain (E)

Rome, Italy (D)

A-C-E-D-F-B-A= $1935 3. During the annual conference of a professional organization, nine topics were proposed for simultaneous plenary discussions. However, some topics need to be scheduled in different time slots. The table summarizes which topic cannot be discussed in the same schedule. a. How many time slots should be scheduled? b. Which topic should be included in each time slot?

Answer:

2 (RED) 1 (BLUE)

3 (GREEN)

9 (VIOLET)

4 (ORANGE)

8 (BLACK)

5 (GREEN)

7 (BLUE)

a. 6 time slots b. Time Slot 1: Topic 1 and 7 Time Slot 2: Topic 2 and 6 Time Slot 3: Topic 3 and 5 Time Slot 4: Topic 4 Time Slot 5: Topic 8 Time Slot 6: Topic 9

6 (RED)