Cтраница 4
Рассмотрим следующее отношение эквивалентности R вХ ( / У классами эквивалентности будут: а) точки из 5, объединенные с их прообразами, б) точки, не участвующие в отображении. [46]
Примерами отношения эквивалентности являются конгруэнтность и равенство. [47]
Сколько отношений эквивалентности существует на множествах из двух, трех, четырех и п элементов. [48]
С отношениями эквивалентности связана важная идея производящих функций. Это понятие помогает при решении вопросов перечисления элементов как конечных, так и бесконечных множеств. [49]
Теперь рассмотрим отношение эквивалентности -, определенное в следствии 3.1.7. Очевидно, что любые две смежные вершины удовлетворяют этому отношению, поскольку паросочетание, не покрывающее обе эти вершины, может быть пополнено соединяющим их ребром и, значит, не является наибольшим. Из связности графа G вытекает, что любые две его вершины должны быть эквивалентны. Но это означает, что всякое наибольшее паросочетание не может не покрывать более одной вершины. [50]