1. Phrase the below story and claim in terms of graph theory, and prove the claim it makes: In an alternate universe the solution to ghting Coronavirus is to change how airports work in Canada. From now on, intercity ights can now only go in one direction. The plane between Calgary and Edmonton either only goes to Calgary (from Edmonton) or vice versa. Further, between any pair of cities, one of them can y to the other. In this setup, there will be some city that from any other city you can either y immediately to it, or y through one other airport to get there. In this world Canada has n airports. Hint: think about complete graphs, directed graphs and also the airport with the most incoming ights.
1. Phrase the below story and claim in terms of graph theory, and prove the claim it makes:
In an alternate universe the solution to ghting Coronavirus is to change how airports work in Canada. From now on, intercity ights can now only go in one direction. The plane between Calgary and Edmonton either only goes to Calgary (from Edmonton) or vice versa. Further, between any pair of cities, one of them can y to the other. In this setup, there will be some city that from any other city you can either y immediately to it, or y through one other airport to get there. In this world Canada has n airports.
Hint: think about complete graphs, directed graphs and also the airport with the most incoming ights.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images