Комбінаторика однорідних розшарувань скінченних метричних просторів
Розглянуто конструкцію та деякі властивості однорідного розшарування над скінченними метричними просторами. Описано матрицю відстаней, граф сусідства та групу ізометрій розшарування. The construction and some properties of homogeneous bundles of finite metric spaces are considered. The matrices of d...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/37803 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Комбінаторика однорідних розшарувань скінченних метричних просторів / Б.В. Олiйник, В. I. Сущанський // Доп. НАН України. — 2011. — № 6. — С. 17-22. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-37803 |
|---|---|
| record_format |
dspace |
| spelling |
Олійник, Б.В. Сущанський, В.І. 2012-10-22T16:59:23Z 2012-10-22T16:59:23Z 2011 Комбінаторика однорідних розшарувань скінченних метричних просторів / Б.В. Олiйник, В. I. Сущанський // Доп. НАН України. — 2011. — № 6. — С. 17-22. — Бібліогр.: 6 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/37803 519.1 Розглянуто конструкцію та деякі властивості однорідного розшарування над скінченними метричними просторами. Описано матрицю відстаней, граф сусідства та групу ізометрій розшарування. The construction and some properties of homogeneous bundles of finite metric spaces are considered. The matrices of distances, neighborhood graphs, and isometry groups of these bundles are described. Робота частково пiдтримана Мiжнародним благодiйним фондом вiдродження Києво-Могилянської академiї. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Комбінаторика однорідних розшарувань скінченних метричних просторів Combinatorics of homogeneous bundles of finite metric spaces 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 |
2011 |
| language |
Ukrainian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Combinatorics of homogeneous bundles of finite metric spaces |
| description |
Розглянуто конструкцію та деякі властивості однорідного розшарування над скінченними метричними просторами. Описано матрицю відстаней, граф сусідства та групу ізометрій розшарування.
The construction and some properties of homogeneous bundles of finite metric spaces are considered. The matrices of distances, neighborhood graphs, and isometry groups of these bundles are described.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/37803 |
| citation_txt |
Комбінаторика однорідних розшарувань скінченних метричних просторів / Б.В. Олiйник, В. I. Сущанський // Доп. НАН України. — 2011. — № 6. — С. 17-22. — Бібліогр.: 6 назв. — укр. |
| work_keys_str_mv |
AT olíinikbv kombínatorikaodnorídnihrozšaruvanʹskínčennihmetričnihprostorív AT suŝansʹkiiví kombínatorikaodnorídnihrozšaruvanʹskínčennihmetričnihprostorív AT olíinikbv combinatoricsofhomogeneousbundlesoffinitemetricspaces AT suŝansʹkiiví combinatoricsofhomogeneousbundlesoffinitemetricspaces |
| first_indexed |
2025-11-24T16:59:13Z |
| last_indexed |
2025-11-24T16:59:13Z |
| _version_ |
1850490082180464640 |
| fulltext |
УДК 519.1
© 2011
Б.В. Олiйник, В. I. Сущанський
Комбiнаторика однорiдних розшарувань скiнченних
метричних просторiв
(Представлено академiком НАН України М.О. Перестюком)
Розглянуто конструкцiю та деякi властивостi однорiдного розшарування над скiнчен-
ними метричними просторами. Описано матрицю вiдстаней, граф сусiдства та групу
iзометрiй розшарування.
У повiдомленнi розглядаються лише скiнченнi метричнi простори, а тому далi пiд “метрич-
ним простором” розумiється “скiнченний метричний простiр”. Метричний простiр (X, dX )
назвемо розшаруванням кратностi m над метричним простором (Y, dY ), якщо простiр X
розбивається в диз’юнктне об’єднання m пiдпросторiв, кожен з яких є iзометричним просто-
ру Y . Розглядатимемо спецiальний, порiвняно вузький клас розшарувань, для яких вiдстань
мiж кожними двома шарами є сталим числом. Формально ця конструкцiя визначається та-
ким чином. Розшарування
X =
m
⋃
i=i
Yi (1)
назвемо однорiдним з визначальною вiдстанню a, a ∈ R, a > 0, якщо для довiльних i, j,
i 6= j, iснує iзометрична вiдповiднiсть fij мiж пiдпросторами Yi, Yj така, що для довiльних
точок u ∈ Yi, v ∈ Yj має мiсце рiвнiсть
dX(u, v) = a+ dYj
(fij(u), v). (2)
Зокрема, вiдстань мiж вiдповiдними точками шарiв Yi i Yj дорiвнює a. Легко зрозумiти,
що конструкцiя однорiдного розшарування є спрощеним варiантом прямого добутку мет-
рик (див. [1, с. 141], а саме, простiр X є iзометричним добутку метричного простору Y на
еквiдистантний простiр над множиною {1, 2, . . . ,m} з ненульовою вiдстанню a. А тому, з то-
чнiстю до iзометрiї, однорiдне розшарування не залежить вiд вибору вiдповiдностей fij. Це
означає, що однорiдне розшарування над простором Y однозначно задається парою чисел:
кратнiстю розшарування m i визначальною вiдстанню a. Позначатимемо таке розшарува-
ння простору Y символом (m,a)Y .
Кожна метрика d на множинi X = {x1, . . . , xn} однозначно визначається своєю матри-
цею вiдстаней Md = ||d(xi, xj)||
n
i,j=1, яка є симетричною i має нульову головну дiагональ.
Матриця вiдстаней розшарування метричного простору може бути охарактеризована таким
чином. Символом M⊗m позначимо m-й кронекерiвський степiнь n × n-матрицi M , тобто
блочно-дiагональну матрицю вимiру nm×nm, вздовж головної дiагоналi якої розташовано
блоки, що дорiвнюють M , а всi iншi елементи цiєї матрицi — нульовi. Покладемо також,
що M×m — матриця, що складається з m2 блокiв, кожен з яких дорiвнює M :
M×m =
M M . . . M
M M . . . M
. . . . . . . . . . . .
M M . . . M
.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №6 17
Символом In позначимо n× n-матрицю, усi елементи якої дорiвнюють одиницi.
Твердження 1. Нехай (X, d) є m-кратним розшаруванням над простором (Y, dY ),
|Y | = n, з визначальною вiдстанню a. Тодi iснує таке упорядкування точок простору X,
при якому має мiсце рiвнiсть
MdX = (MdY )
×m + aIn·m − (aIn)
⊗m. (3)
Точки x, y метричного простору (X, d) назвемо сусiднiми, якщо не iснує жодної вiдмiнної
вiд x i y точки z ∈ X, яка лежить мiж ними, тобто такої, що виконується рiвнiсть d(x, y) =
= d(x, z) + d(z, y).
Граф вiдношення сусiдства на множинi X називають каркасом (або скелетом) метри-
чного простору (X, d) (див. [2]). Позначатимемо цей граф символом Kr(X, d). Конструкцiя
розшарувань природним чином визначається для неорiєнтованих графiв. Розшарованим
графом (див. [3]) є граф, множину вершин якого можна розбити на пiдмножини таким
чином, що всi утворенi пiдграфи iзоморфнi мiж собою. Якщо при цьому двi вершини, що
належать до рiзних пiдграфiв, з’єднанi ребром тодi i тiльки тодi, коли одна з них є iзоморф-
ним образом iншої (вважаємо, що iзоморфiзми графiв є фiксованими), то така конструкцiя
називається призмоїдним графом (див. [4]).
Твердження 2. Граф сусiдства розшарування (X, dX ) кратностi m над метричним
простором (Y, dY ) iзоморфний m-кратному призмоїдному графу каркаса метричного про-
стору (Y, dY ).
Це твердження допускає деяке уточнення.
Нехай G1 = (V1, E1) i G2 = (V2, E2) — два простих графи. Прямим добутком графiв
(див. [5]) G1 i G2 називається граф, заданий на множинi вершин V1×V2, двi вершини якого
(u1, v1) i (u2, v2) з’єднанi ребром тодi i тiльки тодi, коли u1 = u2 i вершини v1 та v2 з’єднанi
ребром в G2, або v1 = v2 i вершини u1 та u2 з’єднанi ребром в G1.
Теорема 1. Граф сусiдства розшарування (X, dX ) кратностi m над метричним про-
стором (Y, dY ) iзоморфний прямому добутку повного графа Km i каркаса метричного про-
стору (Y, dY ).
Наслiдок 1. Довiльнi двi сусiднi вершини з кожного шару Yl, 1 6 l 6 m, належать
до m − 1 циклу довжини 4 в графi сусiдства розшарування (X, dX ) кратностi m над ме-
тричним простором (Y, dY ).
Метрика d називається деревною метрикою, якщо граф вiдношення сусiдства на просто-
рi X є деревом. Окремим типом деревних метрик є ультраметрики. Простiр (X, d) називати-
мемо антиподним, якщо для кожної точки u цього простору iснує антипод — точка v така,
що d(u, v) = diamX. Простiр (X, d) називатимемо строго антиподним, якщо для кожної
точки u цього простору iснує єдиний антипод.
Твердження 3. Нехай (X, dX ) є розшаруванням кратностi m, m > 2, над метричним
простором (Y, dY ). Тодi:
1) простiр (X, dX ) не є деревним (зокрема, ультраметричним) метричним простором;
2) якщо простiр (Y, dY ) — антиподний, то простiр (X, dX) також антиподний. Про-
стiр (X, dX ) є строго антиподним простором тодi i лише тодi, коли m = 2, а простiр
(Y, dY ) — строго антиподний.
Трикутником у метричному просторi (X, d) називається довiльна трiйка рiзних точок
простору. Трикутник [x, y, z] вироджений, якщо одна з точок x, y, z лежить мiж двома iн-
шими. У n-точковому просторi можна утворити (n3 ) трикутникiв, певна частина яких буде
18 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №6
виродженими. Кiлькiсть вироджених (чи невироджених) трикутникiв є важливою комбiна-
торною характеристикою метричного простору. Число вироджених трикутникiв у просто-
рi X називатимемо його 3-рангом i позначатимемо r3(X).
Трикутник [x, y, z] у метричному просторi (X, d) назвемо a-виродженим, якщо d(x, y) +
+d(z, y) = d(x, z)+a. Число a-вироджених трикутникiв у просторi X позначатимемо r3,a(X).
Теорема 2. Нехай (Y, dY ) — n-точковий метричний простiр. Має мiсце рiвнiсть
r3((m,a)Y ) = r3(Y )(m+ 2(m2 )) + 2n(n− 1)(m2 ) + r3,a(Y )(m3 ).
Доведення. Зафiксуємо рiзнi точки u, v i w метричного простору (m,a)Y . Припустимо,
що вони утворюють вироджений трикутник, причому точка v лежить мiж точками u i w.
Точки u, v i w можуть належати однiй копiї простору (Y, dY ), двом копiям або трьом.
Порахуємо кiлькiсть вироджених трикутникiв у кожному з випадкiв.
1. Нехай точки u, v i w належать однiй копiї простору Y . 3-ранг простору Y дорiвнює
r3(Y ), всього є m копiй простору Y , тому таких трiйок точок iснує m · r3(Y ).
2. Пронумеруємо, як i ранiше, iзометричнi копiї Y1, Y2, . . . , Ym простору (Y, dy), а iзоме-
тричнiй вiдповiдностi мiж просторами Yl i Yk позначимо flk, 1 6 k, l 6 n.
Нехай точки u, v i w належать до двох копiй Yl i Yk простору Y , причому при iзо-
метричнiй вiдповiдностi жодна з цих точок не переходить в iншу. Точки u, v i w будуть
утворювати вироджений трикутник у таких випадках:
a) u ∈ Yl, v, w ∈ Yk, i трикутник [u, fkl(v), fkl(w)] є виродженим в Yl;
b) u, v ∈ Yl, w ∈ Yk, i трикутник [u, v, fkl(w)] є виродженим в Yl.
Покажемо, що точки u, v i w в просторi (m,a)Y утворюють вироджений трикутник,
якщо його утворюють точки [u, fkl(v), fkl(w)]. Пункт b доводиться аналогiчно.
Справдi, за визначенням метрики d мають мiсце рiвностi
d(u, v) = dY (u, fkl(v)) + a, d(x,w) = dY (u, fkl(w)) + a,
d(v,w) = dY (fkl(v), fkl(w)). (4)
Оскiльки точки fkl(v), u, fkl(w) утворюють вироджений трикутник, то, необмежуючи за-
гальностi, вважаємо, що справедливою є рiвнiсть
dY (u, fkl(w)) = dY (u, fkl(v)) + dY (fkl(v), fkl(w)).
Звiдси, враховуючи рiвностi (4), отримуємо
d(u, v) + d(v,w) = d(u,w),
тобто точки u, v i w в просторi (m,a)Y утворюють вироджений трикутник.
Отже, при фiксованих l i k кожному виродженому трикутнику в просторi Yl вiдповi-
дають два вироджених трикутники в розшаруваннi (m,a)Y , вершини яких мiстяться в ша-
рах Yl i Yk. Крiм того, якщо fkl(v) = u, то при довiльнiй точцi w або з простору Yl, або
з простору Yk трикутник [u, v, w] є виродженим.
Таким чином, якщо точки u, v i w мiстяться в двох копiях Yl i Yk простору Y , то кiлькiсть
вироджених трикутникiв у розшаруваннi дорiвнюватиме
(m2 ) · (2r3(Y ) + 2n(n− 1)).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №6 19
3. Нехай тепер точки u, v i w належать до трьох копiй простору Y , тобто жоднi двi
точки не мiстяться в деякому шарi Yi. Цi точки будуть утворювати вироджений трикутник
у тому i тiльки тому разi, коли при iзометричнiй вiдповiдностi жодна з них не переходить
в iншу, i образи точок u i v в тiй копiї простору Y , яка мiстить w, разом з w утворюють
a-вироджений трикутник. Отже, таких трикутникiв буде r3,a(Y ) · (m3 ).
Додаючи числа вироджених трикутникiв у кожному з випадкiв, отримуємо
r3((m,a)Y ) = m · r3(Y ) + (m2 ) · (2r3(Y ) + 2n(n− 1)) + r3,a(Y ) · (m3 ),
що i доводить твердження теореми.
Наслiдок 2. Якщо a > 2 diam Y , то
r3((m,a)Y ) = m · r3(Y ) + (m2 ) · (2r3(Y ) + 2n(n− 1)).
Кажуть, що точки x1, x2, . . . , xn метричного простору (X, dX) лежать на однiй прямiй,
якщо кожен трикутник з вершинами в цих точках є виродженим. На множинi точок, якi
лежать на однiй прямiй, природно визначається вiдношення лiнiйного порядку. Для того
щоб впорядкована множина точок x1, x2, . . ., xn лежала на однiй прямiй достатньо, щоб
для довiльного i, 1 6 i 6 n− 2, трiйка точок xi, xi+1, xi+2 лежала на однiй прямiй. Надалi
будемо вважати, що якщо точки x1, x2, . . ., xn метричного простору (X, dX) лежать на
однiй прямiй, то для довiльного i, 1 6 i 6 n− 2, точка xi+1 лежить мiж точками xi i xi+2.
Прямою у метричному просторi X називається максимальна за включенням множи-
на точок, якi лежать на однiй прямiй. Довжиною прямої x1, x2, . . ., xn простору (X, dX )
називається сума dX(x1, x2) + dX(x2, x3) + · · · + dX(xn−1, xn).
Теорема 3. Нехай метричний простiр Y мiстить пряму, яка складається з l то-
чок. Тодi метричний простiр (m,a)Y мiстить пряму, що складається з ml точок. Якщо
довжина початкової прямої дорiвнює λ, то довжина визначеної нею прямої у просторi
(m,a)Y дорiвнює mλ + a(m − 1).
Пряму x1, x2, . . . , xn простору (X, dX ) називатимемо замкненою, якщо справедливою
є рiвнiсть dX(xn, x1) + dX(x1, x2) = dX(xn, x2). Якщо пряма x1, x2, . . . , xn у метричному
просторi (X, dX ) замкнена, то для довiльного k, 1 6 k 6 n, послiдовнiсть точок xk, xk + 1,
. . . , xn x1, x2, . . . , xk−1 також утворює пряму в просторi X.
З доведення теореми 3 випливає
Наслiдок 3. Якщо число m є парним, то в розшаруваннi (m,a)Y кратностi m над
простором (Y, dY ) всi прямi є замкненими.
Теорема 4. Нехай (Y, dY ) — метричний простiр, m, m > 2, — деяке натуральне число.
Група iзометрiй розшарування (X, dX ) кратностi m, m > 2, над метричним простором
(Y, dY ) мiстить прямий добуток повної симетричної групи Sm i групи iзометрiй простору
(Y, dY ). Якщо визначальна вiдстань a розшарування не мiститься у множинi значень
метрики d, то має мiсце спiввiдношення
Is(m,a)Y ≃ Sm × IsY. (5)
Доведення. 1. Нехай, як i ранiше, Y = {y1, . . . , yn}. Прямий добуток груп пiдстановок
Sm × IsY згiдно з визначенням (див., наприклад, [6]) дiє на множинi {1, . . . ,m} × Y , яка,
як вже було сказано, природним чином ототожнюється з множиною точок розшарування
(m,a)Y . А тому достатньо переконатися, що кожне перетворення ϕ = (g1, g2) ∈ Sm × IsY
зберiгає метрику d розшарування. Нехай (l, yi) i (k, yj) — деякi двi точки простору (m,a)Y .
20 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №6
Оскiльки g1 ∈ Sm, то рiвнiсть lg1 = kg1 буде справедливою тодi i тiльки тодi, коли l = k.
Крiм того, оскiльки g2 ∈ IsY , то
dY (y
g2
i , y
g2
j ) = dY (yi, yj).
Розглянемо два випадки.
a) k = l. Тодi
d(ϕ(l, yi), ϕ(k, yj)) = d(ϕ(l, yi), ϕ(l, yj)) = d((lg1 , yg2i ), (lg1 , yg2j )) = dY (y
g2
i , y
g2
j ) =
= dY (yi, yj) = d((l, yi), (k, yj)).
b) k 6= l. У цьому випадку маємо ланцюг рiвностей:
d(ϕ(l, yi), ϕ(k, yj)) = d((lg1 , yg2i ), (kg1 , yg2j )) = dY (y
g2
i , y
g2
j ) + a = dY (yi, yj) + a =
= d((l, yi), (k, yj)).
Отже, вiдображення ϕ є iзометрiєю простору (m,a)Y , звiдки i випливає перша частина
твердження теореми.
2. Для доведення другої частини теореми достатньо показати, що за вказаного обмеже-
ння на a для довiльної iзометрiї ϕ простору (m,a)Y iснують (g1, g2) ∈ Sm × IsY такi, що ϕ
дiє на просторi (m,a)Y як пара (g1, g2).
Нехай ϕ((k, yi)) = (l, yj). Оскiльки a не належить множинi значень метрики d,
а d((k, yi), (q, yi)) = a, q 6= k, то образом точки (q, yi) при вiдображеннi ϕ буде точка (q′, yj).
Тобто при вiдображеннi ϕ точки вигляду (∗, yi) будуть переходити у точки вигляду (∗, yj).
Крiм того, при вiдображеннi ϕ рiзнi iзометричнi копiї простору Y будуть переходити
одна в одну.
Таким чином, вiдображення ϕ дiє на множинi {1, . . . ,m} × Y як пара (g1, g2), що на
кожну точку простору (m,a)Y дiє за правилом
(x1, y1)
(g1,g2) = (xg11 , y
g2
1 ),
а отже, ϕ можна розглядати як елемент групи Sm × IsY .
Робота частково пiдтримана Мiжнародним благодiйним фондом вiдродження Києво-Моги-
лянської академiї.
1. Деза М.М., Лоран М. Геометрия разрезов и метрик. – Москва: МЦНМО, 2001. – 736 с.
2. Avgustinovich S., Fon-Der-Flaass D. Cartesian products of graphs and metric spaces // Europ. J. Combi-
natorics. – 2000. – 21. – P. 847–851.
3. Берлов С.Л. Соотношения между кликовым числом, хроматическим числом и степенью для некото-
рых видов графов // Моделирование и анализ информ. систем. – 2008. – 15, № 4. – С. 10–22.
4. Benecke S., Mynhardt C.M. Domination of generalized Cartesian products // Discrete Math. – 2010. –
310, No 8. – P. 1392–1397.
5. Sabidussi G. Graph multiplication // Math. Z. – 1960. – 72. – P. 446–457.
6. Сущанський В. I., Сiкора В. С. Операцiї на групах пiдстановок. Теорiя та застосування. – Чернiвцi:
Рута, 2003. – 255 с.
Надiйшло до редакцiї 15.09.2010Нацiональний унiверситет “Києво-Могилянська академiя”
Сiлезький технiчний унiверситет, Глiвiце, Польща
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №6 21
B.V. Oliynyk, V. I. Sushchansky
Combinatorics of homogeneous bundles of finite metric spaces
The construction and some properties of homogeneous bundles of finite metric spaces are consi-
dered. The matriсes of distances, neighborhood graphs, and isometry groups of these bundles are
described.
22 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №6
|