Эта публикация цитируется в
18 статьях
Субдоминантная псевдоультраметрика на графах
А. А. Довгошей,
Е. А. Петров Институт прикладной математики и механики НАН Украины, г. Донецк
Аннотация:
Пусть
$(G,w)$ — взвешенный граф. Найдены необходимые и достаточные условия, при которых вес
$w\colon E(G)\to \mathbb{R}^+$ продолжается до псевдоультраметрики на
$V(G)$, получен критерий единственности такого продолжения. Доказано, что граф является полным
$k$-дольным с
$k\geqslant 2$ тогда и только тогда, когда для любого веса, продолжающегося до псевдоультраметрики, среди всех таких продолжений найдется наименьшая псевдоультраметрика, согласованная с
$w$. Дана структурная характеристика графов, для которых субдоминантная псевдоультраметрика является ультраметрикой для любого строго положительного веса, продолжающегося до псевдоультраметрики.
Библиография: 14 названий.
Ключевые слова:
взвешенный граф, бесконечный граф, ультраметрическое пространство, метрика кратчайшего пути, полный
$k$-дольный граф.
УДК:
519.173+
515.124
MSC: 05C78,
54E35 Поступила в редакцию: 19.08.2011 и 27.02.2013
DOI:
10.4213/sm7925