Graph Theory Course

This project deals with the Greedy Algorithm approaches. The goal of the project is to create a Minimum Cost Network of Computers (MCNC) for Al-Hilal Saudi company. Given a connection cost of every pair of computers that can be connected (there may be pairs of computers between which no direct connection can be built), Al- Hilal company aims to connect every computer with another either with a direct connection or via a sequence of connections with a minimum total cost. The computer network must satisfy the following hard constraint: Al-Hillal possesses two supercomputers that must be directly connected due to the high frequency and quantity of messages exchanged between them. See the illustration example. Example with 5 computers where A and D are the supercomputers, there is no edge between computers A and E means that the two computers cannot be directly connected. 55 100 99 25 55 33 E 35 10 D a. Represent the problem MCNC with a graph; explain the semantic of each entity of the graph modeling the problem: (1.5pts) al node: a.2 edge: a.3 weight: b. Give the names of two greedy algorithm approaches which can be used to solve the problem MCNC (Ipts). 1. 2. c. Analyze the two algorithms (Ipts) 1. Give the time complexity of each algorithm 2. Give the space complexity of each algorithm d. Whenever two computers cannot be directly connected which connection cost is assigned to this pair? (0.5)