Ультраметризация взвешенных графов
Пусть (G,w) — взвешенный граф. Найдены необходимые и достаточные условия, при которых вес w:E(G)→R^+ продолжается до псевдоультраметрики на V(G), получен критерий единственности такого продолжения. Доказано, что граф является полным k-дольным с k≥2 тогда и только тогда, когда для любого веса, продол...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50011 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Ультраметризация взвешенных графов / А.А. Довгошей, Е.А. Петров // Доп. НАН України. — 2012. — № 6. — С. 17-23. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50011 |
|---|---|
| record_format |
dspace |
| spelling |
Довгошей, А.А. Петров, Е.А. 2013-10-02T17:35:19Z 2013-10-02T17:35:19Z 2012 Ультраметризация взвешенных графов / А.А. Довгошей, Е.А. Петров // Доп. НАН України. — 2012. — № 6. — С. 17-23. — Бібліогр.: 12 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/50011 519.173+515.124 Пусть (G,w) — взвешенный граф. Найдены необходимые и достаточные условия, при которых вес w:E(G)→R^+ продолжается до псевдоультраметрики на V(G), получен критерий единственности такого продолжения. Доказано, что граф является полным k-дольным с k≥2 тогда и только тогда, когда для любого веса, продолжающегося до псевдоультраметрики, среди всех таких продолжений найдется наименьшая псевдоультраметрика. Дана структурная характеристика графов, для которых субдоминантная псевдоультраметрика является ультраметрикой для любого строго положительного веса, продолжающегося до псевдоультраметрики. Нехай (G,w) — зважений граф. Знайдені необхідні і достатні умови, за яких вага w:E(G)→R^+ продовжується до псевдоультраметрики на V(G), отримано критерій єдиності такого продовження. Доведено, що граф є повним k-частковим з k≥2 тоді і тільки тоді, коли для будь-якої ваги, що продовжується до псевдоультраметрики, серед усіх таких продовжень знайдеться найменша псевдоультраметрика. Дано структурну характеристику графів, для яких субдомінантна псевдоультраметрика є ультраметрикою для будь-якої строго додатної ваги, що продовжується до псевдоультраметрики. Let (G,w) be a weighted graph. The necessary and sufficient conditions under which the weight w:E(G)→R^+ can be extended to a pseudoultrametric on V(G) are found. A criterion of the uniqueness of this extension is also obtained. It is proved that a graph is a complete k-partite with k≥2 if and only if, for every pseudoultrametrizable weight w, there exists the smallest pseudoultrametric, agreed with w. We characterize the structure of graphs, for which a subdominant pseudoultrametric is an ultrametric for every strictly positive pseudoultrametrizable weight. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Ультраметризация взвешенных графов Ультраметризація зважених графів Ultrametrization of weighted graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Ультраметризация взвешенных графов |
| spellingShingle |
Ультраметризация взвешенных графов Довгошей, А.А. Петров, Е.А. Математика |
| title_short |
Ультраметризация взвешенных графов |
| title_full |
Ультраметризация взвешенных графов |
| title_fullStr |
Ультраметризация взвешенных графов |
| title_full_unstemmed |
Ультраметризация взвешенных графов |
| title_sort |
ультраметризация взвешенных графов |
| author |
Довгошей, А.А. Петров, Е.А. |
| author_facet |
Довгошей, А.А. Петров, Е.А. |
| topic |
Математика |
| topic_facet |
Математика |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Ультраметризація зважених графів Ultrametrization of weighted graphs |
| description |
Пусть (G,w) — взвешенный граф. Найдены необходимые и достаточные условия, при которых вес w:E(G)→R^+ продолжается до псевдоультраметрики на V(G), получен критерий единственности такого продолжения. Доказано, что граф является полным k-дольным с k≥2 тогда и только тогда, когда для любого веса, продолжающегося до псевдоультраметрики, среди всех таких продолжений найдется наименьшая псевдоультраметрика. Дана структурная характеристика графов, для которых субдоминантная псевдоультраметрика является ультраметрикой для любого строго положительного веса, продолжающегося до псевдоультраметрики.
Нехай (G,w) — зважений граф. Знайдені необхідні і достатні умови, за яких вага w:E(G)→R^+ продовжується до псевдоультраметрики на V(G), отримано критерій єдиності такого продовження. Доведено, що граф є повним k-частковим з k≥2 тоді і тільки тоді, коли для будь-якої ваги, що продовжується до псевдоультраметрики, серед усіх таких продовжень знайдеться найменша псевдоультраметрика. Дано структурну характеристику графів, для яких субдомінантна псевдоультраметрика є ультраметрикою для будь-якої строго додатної ваги, що продовжується до псевдоультраметрики.
Let (G,w) be a weighted graph. The necessary and sufficient conditions under which the weight w:E(G)→R^+ can be extended to a pseudoultrametric on V(G) are found. A criterion of the uniqueness of this extension is also obtained. It is proved that a graph is a complete k-partite with k≥2 if and only if, for every pseudoultrametrizable weight w, there exists the smallest pseudoultrametric, agreed with w. We characterize the structure of graphs, for which a subdominant pseudoultrametric is an ultrametric for every strictly positive pseudoultrametrizable weight.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50011 |
| citation_txt |
Ультраметризация взвешенных графов / А.А. Довгошей, Е.А. Петров // Доп. НАН України. — 2012. — № 6. — С. 17-23. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT dovgošeiaa ulʹtrametrizaciâvzvešennyhgrafov AT petrovea ulʹtrametrizaciâvzvešennyhgrafov AT dovgošeiaa ulʹtrametrizacíâzvaženihgrafív AT petrovea ulʹtrametrizacíâzvaženihgrafív AT dovgošeiaa ultrametrizationofweightedgraphs AT petrovea ultrametrizationofweightedgraphs |
| first_indexed |
2025-12-07T13:23:19Z |
| last_indexed |
2025-12-07T13:23:19Z |
| _version_ |
1850855967906856960 |