Сравн-ие мощн.как отн-ие поряд.

Если |A|=|B|, |A|=|A’|, |B|=|B’|, то мощн. A’не пре-восх.мощ.B’.Док-во: B1’=h(B1).gofoh: A’à B1’ причем взаимооднн., т.к. g-также взаимоодн.соотв., т.е.B’ найд-ся кус-к, кот.отобр.A. Отн-ие нестрогого порядка. Реф-ть: мощ.А не прев.мощ.А.Тран-ть: Если мощн.А не прев.мощ.В и В не прев.мощн. С, то мощ.А не прев. мощ.С. .С2=g(B1), fog: Aà c2 взаи-моод.отобр.Антисим-ть:.А посред-ством f отобр-ет какую-то часть B(B1).В поср-вом g отобр.какую-то часть B на A.Мощн.А не превосх.мощн.В.|A|< =|B|.

Структура центра дерева

l(V)-эксцентриситет верш.l(V)=max d(U, V), d-расст., U, V-верш.r(Г)-рад.графа, r(г)=min{l(V)}, d=max{l(V)}.Центр графа-мн-во таких верш.V, эксцен-т кот.совпад.с рад.графа.{V: l(V)=r(l)}. Нарис.примеры.У люб.дер.центр сост.из 1 или 2 смеж.верш.Эксц-т уменьш-ся на 1, если мы удал.из дер.все висящ.верш.с соотв.дугами.В конце кон-цов мы придем к 1 или 2 верш., кот.явл.центром.