о предмногообразиях полугрупп

427

Покажем , что теория ир.с.графа сводится к77? ^jP/ формулами f№j и z(S,u), Пусть<Af,/0^ -конечный ир.с.граф и ^=*{/77;,.».,/77 \ . Рассмотрим в 2^ лугруппу Г с множеством образующихL'^'MUО и определяющими

шениями :

( m' , mj ) m^ = [m^,mj)mj , (3)

Cm^ , mj ) imj , m^ ) = {.rn-^mpim^^rrij). (4)

Изоморфизм^|лгеГ / ^^ ( яг ) г , '2^ ( ^ , ^ ) ^=<'A / , P> докажем в два этапа.

Первый этап. Покажем, что [хе T/f.icc)^ = M и [х£ T^f (X)} =/Р . Легко проверить, что [^/f. (Хп ~ Zr , На Р справедливо тождество X(JZ *= й^и t так как оно выполняется на о . Используя это во, равенства (4) и иррефлексивность О , получаем:

Следовательно , РЯ. [х /f (ДГ)]

Покажем , что MЯ:\x/fiX)] . ПустъПгеМ , £eL \\т\игп^£^. да для равенс1Ечаа/Т7-» Ï/ контрпримером будет полугруппа S и гомомор - физм çp , определяемый отображением: {—*"Ä,Z,\j^]—*" ^* . но, для всякого равенства Ь^^^Ь^ из (3) или (4) (p^i )^ ÇD ii^) ^та¥. как 2^ -левый нуль, но р(,ь /'^ ß^ , а (р(пг j ~ ^^ • Следовательно,

f^ ( m } & . m^^ 1^ влечетт-^ . Таккак |:г//'№;}и|ас//^Гх)}=/,= = Нир и {бс//№)} n|x//^fj?)} « ^ . то |х/Дл:;}«^ и{д:/£, (а:;}«

Второй этап. Покажем, что t(mj^, m^)¥=^(mj^,m£) ^ О . Пусть {i^j^^rnp)tp . Тогда из (3) следует, что в качестве Z , о котором рится в Ъ(х,и) , можно взять Г^^г^.т^Л Докажем обратное. Если ла Ъ(/П^(,гп^) истинна, то kf^o и существует пара (/тг /77^) из/9 , такая

что

Опровергнем три возможности: р^к и q^k , (У=^к' ирф{ , p=^k и

1 , Допустим, чторф^к и 0=^к . Рассмотрим гомоморфизм ср , оп - ределяемый отображением (Щр, rnJ-*-Û, т^--*- а . /^ \ {{гПр^Шо )] -*• <^; »

\^к ] —^^ • Равенства (4) при указанном гомоморфизме, очевидно, сохраняются. Если ьфр или iФо, i то равенство из (3) также спра - ведливо, поскольку р {т^^^гп») ^ Еу и Sf -левый нуль в S . Если ж^и^р иу»^ . то (3) содержит равенство {ппр,т^.)тр^ {гПр^Щд)mq . И в этом