Ультраметризация взвешенных графов

Довгошей, А. А.; Петров, Е. А.

Пусть (G, w) - взвешенный граф. Найдены необходимые и достаточные условия, при которых вес <$E w:~E(G)~symbol О~{bold roman R} sup +> продолжается до псевдоультраметрики (ПУМ) на V(G), получен критерий единственности такого продолжения. Доказано, что граф является полным k-дольным с <$E k~symbol У~2> тогда и только тогда, когда для любого веса, продолжающегося до ПУМ, среди всех таких продолжений найдется наименьшая ПУМ. Дана структурная характеристика графов, для которых субдоминантная ПУМ является ультраметрикой для любого строго положительного веса, продолжающегося до ПУМ.


	Наукова періодика України		Доповіді Національної академії наук України