5099

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

A Graph Bottleneck Inequality

Наименование источника: 

  • arXiv.org

Обозначение и номер тома: 

0810

Город: 

  • Ithaca

Издательство: 

  • Cornell University

Год издания: 

2008

Страницы: 

P. 1-6 http://arxiv.org/abs/0810.2732
Аннотация
Для взвешенного мультиграфа пусть f_{ij} – общий вес остовных входящих лесов, где вершина i принадлежит дереву, входящему в j. В статье доказано, что f_{ij}f_{jk} = f_{ik}f_{jj} тогда и только тогда каждый направленный путь из i в k содержит j («равенство узкого места»). В противном случае f_{ij}f_{jk} < f_{ik}f_{jj} («неравенство узкого места»). В работе «A new family of graph distances» это неравенство положено в основу построения нового семейства графовых расстояний: оно обеспечивает выполнение неравенства треугольника. Эта взаимосвязь двух неравенств связана с тем фактом, что неравенство узкого места является мультипликативным аналогом неравенства треугольника для функций близости.

Библиографическая ссылка: 

Чеботарев П.Ю. A Graph Bottleneck Inequality / arXiv.org. Ithaca: Cornell University, 2008. 0810. С. P. 1-6 http://arxiv.org/abs/0810.2732.