Сильно связные компоненты и разбиение на классы эквивалентности
Экземпляры класса Set имеют методdivide
, который получает блок с двумя аргументами, задающую бинарное отношение на элементах множества, то есть отображающая пару элементов
(a,b) в true или false.
Обычно используют отношение эквивалентности, то есть транзитивное, рефлексивное и симметричное отношение.
Результат вычисления есть множество классов эквивалентности, но которые разбилось исходное множество.
require 'set' m = Set.new([1,2,4,5,6,7,4,3,3,433,546,6,6,324,21,14,55,23,45]) m.divide { |a,b| a%7 == b%7 }.each {|s| puts s.inspect}
#<Set: {1}> #<Set: {4}> #<Set: {5}> #<Set: {546, 7, 14, 21}> #<Set: {324, 23, 2}> #<Set: {55, 6, 433}> #<Set: {45, 3}>
Задача.
Докажите, что если булева функция f(a,b) задает отношение эквивалентности, то сильно связные компоненты графа с матрицей смежности f(a,b)
совпадают с классами эквивалентности.