Cтраница 1
Отношение изоморфизма является отношением эквивалентности, разбивающим множество всех мультиграфов на классы эквивалентности, которые можно рассматривать как абстрактные мультигра-фы. Изоморфные мультиграфы представляют собой один и тот же абстрактный мультиграф. В настоящее время в связи с отсутствием стандарта на машинное представление [84] существует многс способов ввода в ЭВМ структурных формул и их топологическю графов. Весом вершины при этом служит символ химического элемент или радикала, а весом ребра - кратность химической связи. [1]
Отношение изоморфизма между графами рефлексивно, ибо у любого графа существует тождественный автоморфизм. Оно, кроме того, симметрично: если 0 ( /, §) - изоморфизм графа С на граф Я, то существует обратный изоморфизм 0 - 1 ( / -, § - 1) графа Я на граф О. Наконец, отношение изоморфизма между графами является транзитивным: если 0 ( /, §) - изоморфизм графа С на Я и ф ( / ь 1) - изоморфизм графа Я на К, то существует изоморфизм фб ( / 1 /, § §) графа О на граф К. Легко проверяется, что так определенное умножение изоморфизмов обладает свойством ассоциативности. [2]
Поскольку отношение изоморфизма рефлексивно, симметрично и транзитивно, то оно является отношением эквивалентности. Поэтому любые преобразования графа, не выводящие его из класса изоморфизма, являются тождественными преобразованиями. [3]
Итак, отношение изоморфизма между графами является отношением эквивалентности. Следовательно, оно разбивает класс всех графов на непустые и попарно непересекающиеся подклассы, называемые классами изоморфизма или классами изоморфных графов. [4]
Так как отношение максимального изоморфизма является отношением эквивалентности, то отсюда вытекает: если деревья t и t7 не являются максимально изоморфными, то совокупности деревьев TI ( t) и TI ( t) не пересекаются. [5]
Ясно, что отношение изоморфизма рефлексивно, симметрично и транзитивно. [6]
Иначе говоря, отношение изоморфизма областей транзитивно. [7]
Очевидно, что установленное отношение изоморфизма множеств деревьев является рефлексивным, симметричным и транзитивным, то есть отношением эквивалентности. [8]
Непосредственно проверяется, что отношение изоморфизма характеристических функций является рефлексивным, симметричным и транзитивным. [9]
Совокупность свойств 1 - 3 означает, что отношение изоморфизма линейных пространств на множестве всех линейных пространств над одним и тем же полем есть отношение эквивалентности и потому разбивает это множество на непересекающиеся классы изоморфных линейных пространств. Ниже мы установим критерий изоморфизма линейных пространств. [10]
В целях удобства мы употребляем знак для обозначения отношения изоморфизма между моделями языка X. Совершенно ясно, что отношение является отношением эквивалентности. [11]
Такое взаимно однозначное отображение F, сохраняющее смежность, называется отношением изоморфизма. [12]
Теорема 3.6.7. Отношение условно рациональной эквивалентности на полурешетках совпадает с отношением изоморфизма. [13]
Теорема 3.6.9. Отношение условной рациональной эквивалентности на булевых алгебрах совпадает с отношением изоморфизма. [14]
В этой главе излагается постановка задачи разложения графов в классе эквивалентности по отношению изоморфизма. Доказываются теоремы о необходимом и достаточном условии разложения графов по операциям умножения, суммирования, композиции и суперпозиции и приводятся алгоритмы разложения по указанным операциям. Формулируются теоремы и даются алгоритмы разложения графов по двум операциям - одной теоретико-множественной ( объединение или пересечение) и одной алгебраической ( умножение или композиция) операции. [15]