Страница 15 номер 32, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
На острове 7 посёлков, связанных между собой десятью дорогами. Какое наибольшее количество дорог можно одновременно закрыть на ремонт так, чтобы по-прежнему из любого посёлка можно было добраться до любого другого?
Посёлки — вершины графа, дороги — рёбра: 7 вершин и 10 рёбер. «По-прежнему» означает, что и сейчас из любого посёлка можно добраться до любого другого, то есть граф связный.
Пусть после закрытия нескольких дорог граф из открытых дорог связный. Разомкнув в нём все циклы, если они есть, получим его остовное дерево: в нём все 7 вершин, значит, \(7 - 1 = 6\) рёбер, и все они — открытые дороги. Поэтому открытых дорог не меньше 6, а закрытых — не больше \(10 - 6 = 4\).
Закрыть 4 дороги можно: возьмём любое остовное дерево исходного графа — в нём 6 рёбер — и закроем остальные \(10 - 6 = 4\) дороги. Открытые дороги образуют дерево, а дерево — связный граф, поэтому из любого посёлка по-прежнему можно добраться до любого другого.
Значит, наибольшее число дорог, которые можно одновременно закрыть на ремонт, равно 4 — это цикломатическое число графа.
Ответ: 4 дороги.
На острове 7 посёлков, связанных между собой десятью дорогами. Какое наибольшее количество дорог можно одновременно закрыть на ремонт так, чтобы по-прежнему из любого посёлка можно было добраться до любого другого?
Посёлки — вершины графа, дороги — его рёбра: ребро соединяет два посёлка, если их связывает дорога. В графе 7 вершин и 10 рёбер. Слово «по-прежнему» означает, что и сейчас из любого посёлка можно добраться до любого другого, то есть граф связный.
Пусть закрыли несколько дорог так, что граф из открытых дорог остался связным. Разомкнём в нём все циклы, если они есть, — получится остовное дерево этого графа. В нём все 7 вершин, значит, \(7 - 1 = 6\) рёбер, и все они — открытые дороги. Поэтому открытых дорог не меньше 6, а закрытых — не больше \(10 - 6 = 4\).
Закрыть 4 дороги можно. Возьмём любое остовное дерево исходного графа — в нём 6 рёбер — и закроем остальные \(10 - 6 = 4\) дороги. Открытые дороги образуют дерево, а дерево — связный граф, поэтому из любого посёлка по-прежнему можно добраться до любого другого.
Значит, наибольшее число дорог, которые можно одновременно закрыть на ремонт, равно 4 — это цикломатическое число графа.
Ответ: 4 дороги.
