A communications link in a network should be provided with a backup link if its failure makes it impossible for some message to be sent. For each of the communications networks shown here in (a) and (b), determine those links that should be backed up.
(a)

(b)

A vertex basis in a directed graph G is a minimal set B of vertices of G such that for each vertex v of G not in B there is a path to v from some vertex B.

Transcribed Image Text:

Boston Chicago New York San Francisco Washington Denver Los Angeles Bangor Burlington SeattlePortland Boston Denver Chicago Franeisconss Ciy Wi New York Washington Kansas City Salt Lake Atlanta Los City Angeles