Раздел «Язык Ruby».DivideMethod:

Сильно связные компоненты и разбиение на классы эквивалентности

Экземпляры класса 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) совпадают с классами эквивалентности.