Об общем представлении числовых графов
Here we suggest a new approach to present major graphs of practical use as numerical. Examples of such representation are provided.
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2004 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2004
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84871 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Об общем представлении числовых графов / Г.А. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 11-18. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859636587892047872 |
|---|---|
| author | Донец, Г.А. Шулинок, И.Э. |
| author_facet | Донец, Г.А. Шулинок, И.Э. |
| citation_txt | Об общем представлении числовых графов / Г.А. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 11-18. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Here we suggest a new approach to present major graphs of practical use as numerical. Examples of such representation are provided.
|
| first_indexed | 2025-12-07T13:16:56Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2004, № 3 11
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются числовые гра-
фы и способы их представления.
Предлагается новый подход, по-
зволяющий многие графы, кото-
рые используются в практических
задачах, представлять как число-
вые. Приводятся примеры такого
представления.
Г.А. Донец, И.Э. Шулинок,
2004
ÓÄÊ 519.1
Ã.À. ÄÎÍÅÖ , È.Ý. ØÓËÈÍÎÊ
ÎÁ ÎÁÙÅÌ ÏÐÅÄÑÒÀÂËÅÍÈÈ
×ÈÑËÎÂÛÕ ÃÐÀÔÎÂ
Существует огромный перечень литературы,
в которой исследовались числовые графы
[1–5]. Из всех числовых графов натуральные
арифметические (NA-графы) и натуральные
модульные (NM-графы) по способу задания –
самые простые. Но уже обычные арифмети-
ческие (А-графы) и модульные (М-графы)
требуют задания способа (функции), по ко-
торому из натурального ряда чисел изыма-
ются те, которые соответствуют вершинам,
не принадлежащим множеству X В общем
случае, в зависимости от вида числового
графа, существуют два принципиально раз-
личных их задания.
Первый, наиболее общий способ, предла-
гается в данной работе.
Числовым графом ),,,( gFUXG = называ-
ется n-вершинный граф, представленный дв-
умя множествами nNnX == },,2,1{ K – мно-
жеством вершин и NU ∈ – множеством об-
разующих, функцией смежности ),( ji xxF и
функцией исключения )(xg . В нем вершина
Xxk ∉ , если 0)( =kxg , а вершины Xxx ji ∈,
смежны, если UxxF ji ∈),( .
Если jiji xxxxF +=),( , то такой числовой
граф называется арифметическим, если же
||),( jiji xxxxF −= , то соответственно – мо-
дульным. Относительно функции )(xg ника-
ких определенных свойств не предполагает-
ся, она может просто перечислять множест-
во вершин, не принадлежащих X .
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
12 Теорія оптимальних рішень. 2004, № 3
В большинстве случаев, когда заданный граф имеет определенную структу-
ру, имеющую несколько осей симметрии, или периодически повторяющиеся
части, задание функций ),( ji xxF и )(xg не представляет труда.
Применение теории графов в различных областях практической деятельно-
сти человека показало, что подавляющее большинство графов, которые при
этом использовались, носили именно такую специфическую структуру. Можно
перечислить множество солидных монографий из области распознавания обра-
зов, математического моделирования параллельных процессов, теоретических
основ создания информационных технологий и других, где рассматриваются
графы, ко- торые можно представить в виде числовых графов выше указанным
способом.
Рассмотрим в качестве примера [6, рис. 2. 4, с. 42], где сравнение распозна-
ваемой реализации сигнала ix с эталоном слова производилось с помощью гра-
фа, представленного (в уменьшенном виде) на рис.1.
( 0,0)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
l
k 1
l
k2
l
k3
l
k4 l
k5
РИС. 1. Часто используемый развернутый граф слова
ОБ ОБЩЕМ ПРЕДСТАВЛЕНИИ ЧИСЛОВЫХ ГРАФОВ
Теорія оптимальних рішень. 2004, № 3 13
По своей структуре это довольно простой граф, который можно представить
в виде числового графа следующим образом (рис.2).
0
1
2
3
4
5
6
7
15 23 31 39
8 3216 24
33
34
35
36
37
38
9 17 25
10 18 26
11 19 27
12 20 28
13 21 29
14 22 30
РИС. 2. Реализация предыдущего графа в виде числового
В результате получаем граф с числом вершин 39=n , т. е. }39,,2,1{ K=X ,
)8(mod0)(,),( ≡−= xgxxxxF ijji , а }9,8,1{=U . Таким образом, информация о
графе укладывается в 6 чисел. В работе [6] граф по размерам значительно боль-
ше, он по вертикали имеет 21 вершину, по горизонтали – 14 вершин, т. е. всего –
294 вершины. Числовой граф, (с учетом добавленных фиктивных вершин) будет
иметь 308=n вершин и будет представляться следующим образом:
}23,22,1{),22(mod0)(,),(},308,,2,1{ =≡−== UxgxxxxFX ijjiK .
Аналогичное представление допускает и граф, представленный на рис.3,
взятый из [6 , рис. 9. 6, с.185].
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
14 Теорія оптимальних рішень. 2004, № 3
...
0
1
2
3
4
5
6
s
T
min T
min
+1 T
max
РИС.3. Граф решения задачи о мгновенном периоде основного тона
Этот граф можно представить в виде числового графа с той же порождаю-
щей функцией, что и в предыдущем примере, т. е. ijji xxxxF −=),( , но с другим
множеством образующих. Этот граф представлен на рис.4.
ОБ ОБЩЕМ ПРЕДСТАВЛЕНИИ ЧИСЛОВЫХ ГРАФОВ
Теорія оптимальних рішень. 2004, № 3 15
1
2
3
4
5
6
7
0 9 18 27 36 45 54
10 19 28 37 46 55
11 20 29 38 47 56
12 21 30 39 48 57
13 22 31 40 49 58
14 23 32 41 48 59
15 24 33 42 51 60
16 25 34 43 52 61
8 17 26 35 44 53 62
РИС. 4. Реализация предыдущего графа в виде числового
Здесь на рис. 4 сохраняются все стрелки, что и на основном рис.3, но для
удобства они лишь обозначены. Сам граф представляется в виде 62=n , т. е.
}62,,2,1{ K=X , ijji xxxxF −=),( , }19,10,1,8,17{),9(mod0)( −−=≡ Uxg . Так как
),( ji xxF – функция несимметричная, то граф ориентирован. Если бы он не был
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
16 Теорія оптимальних рішень. 2004, № 3
ориентированным, то его можно было бы представить и другой функцией –
|1|),(1 −−= ijji xxxxF , а }18,9,0{=U .
Рассмотрим еще один пример из [6], где функция смежности уже не яв-
ляется элементарной (рис. 5)
0 1 2 3 4 5 6 7 8 9
9
8
7
6
5
4
3
2
1
РИС. 5. Граф для оценивания оператора настройки
Этот граф соответствует графу [6] на рис. 8.1, с. 159. На нем нанесены пунк-
тиром стрелки, которые соединяют вершины целочисленной решетки по прави-
лам:
а) вершину )0,0( с вершинами 81),,1( ≤≤ ii ;
б) вершину ),( ji с вершинами 18),,1( ≥≥≥+ jkki ;
в) вершины ),8( j , с вершиной )9,9( .
Чтобы реализовать этот граф в виде числового графа, рассмотрим следую-
щий граф из 80 вершин, который представляет собой 10 колонок по 8 вершин в
каждой. Нумерация вершин начинается с нуля до 79, идет снизу вверх. Верши-
ны }7,,2,1{ K и }78,,73,72{ K будут фиктивными. Вершина 0 соответствует вер-
шине )0,0( на рис.5, а вершина 79 – вершине )9,9( . Остальные связи легко пе-
реносятся на новый граф. В результате получаем граф на рис.6.
ОБ ОБЩЕМ ПРЕДСТАВЛЕНИИ ЧИСЛОВЫХ ГРАФОВ
Теорія оптимальних рішень. 2004, № 3 17
0 8 16 24 32 40 48 56 64 72
7 15 23 31 39 47 55 63 71 79
6 14 22 30 38 46 54 62 70 78
5 13 21 29 37 45 53 61 69 77
4 12 20 28 36 44 52 60 68 76
3 11 19 27 35 43 51 59 67 75
2 10 18 26 34 42 50 58 66 74
1 9 17 25 33 41 49 67 65 73
РИС.6. Числовой граф, эквивалентный графу на рис.5
Граф представляется следующим образом:
79=n , )(
88
),(},79,,1,0{ ij
ij
ji xx
xx
xxFX −
−
== K ,
}15,14,13,12,11,10,9,8{},78,,73,72;7,,2,1{)( == Uxg KK .
Покажем, что любой подобный граф, у которого stn = , можно реализовать в
виде числового графа со следующими параметрами:
1−= stn , }1,,1,0{ −= stX K , )(),( ij
ij
ji xx
s
x
s
x
xxF −
−
= ,
}1,,1)1(,)1(;1,,2,1{)( −+−−−= sttstssxg KK , }12,,1,{ −+= sssU K .
Действительно, U представляет собой образующие, которые связывают
вершины двух соседних столбцов, минимальная разность кодов которых есть s .
Номер каждого столбца, в котором находится вершина ix , равен
s
xi (номера
начинаются с нуля). Поэтому, если найдутся две вершины ix и jx , разность ко-
торых принадлежит U , но они находятся не в соседних столбцах, то множитель
Г.А. ДОНЕЦ, И.Э. ШУЛИНОК
18 Теорія оптимальних рішень. 2004, № 3
−
s
x
s
x
ij
будет больше 1, и тогда sxxF ij 2),( ≥ , то есть вершины графа ix и
jx будут несмежными.
Г.А. Донець, І.Е. Шулінок
ПРО ЗАГАЛЬНЕ ПРЕДСТАВЛЕННЯ ЧИСЛОВИХ ГРАФІВ
Розглядаються числові графи та способи їх представлення. Пропонується новий підхід, що
дозволяє багато графів, які використовуються у практичних задачах, представляти як числові.
Наводяться приклади такого представлення.
G.A. Donets, I.E. Shoolinock
ABOUT GENERAL REPRESENTATION OF NUMERICAL GRAPHS
Here we suggest a new approach to present major graphs of practical use as numerical. Examples
of such representation are provided.
1. Донец Г.А. О графах, задаваемых аналитическим способом // Теория оптимальных
решений.– Киев: Ин-т кибернетики им.В.М. Глушкова АН УССР, 1987. – С. 20 – 27.
2. Донец Г.А. Об оптимальном кодировании однородных деревьев в арифметических
графах // Методы решения экстремальных задач и смежные вопросы. – Киев: Ин-т
кибернетики им. В.М. Глушкова АН УССР, 1987. – С. 72 – 77.
3. Донець Г.О., Неженцев Ю.І. Арифметичні графи та їх представлення // Доп. АН
УРСР. Сер.А. – 1990. – № 11. – С. 5 – 8.
4. Шулинок И.Э. О связности натуральных модульных графов // Кибернетика и
системный анализ. – 1998 – № 5. – С. 50 – 53.
5. Шулинок И.Э. О связности и цикломатическом числе натуральных модульных
графов // Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М.
Глушкова НАН Украины. – 1999. – С. 51 – 57.
6. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. – Киев:
Наук. думка, 1987. – 264 с.
Получено 16.06.2004
|
| id | nasplib_isofts_kiev_ua-123456789-84871 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T13:16:56Z |
| publishDate | 2004 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Шулинок, И.Э. 2015-07-16T17:36:08Z 2015-07-16T17:36:08Z 2004 Об общем представлении числовых графов / Г.А. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 11-18. — Бібліогр.: 6 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84871 519.1 Here we suggest a new approach to present major graphs of practical use as numerical. Examples of such representation are provided. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об общем представлении числовых графов About general representation of numerical graphs Article published earlier |
| spellingShingle | Об общем представлении числовых графов Донец, Г.А. Шулинок, И.Э. |
| title | Об общем представлении числовых графов |
| title_alt | About general representation of numerical graphs |
| title_full | Об общем представлении числовых графов |
| title_fullStr | Об общем представлении числовых графов |
| title_full_unstemmed | Об общем представлении числовых графов |
| title_short | Об общем представлении числовых графов |
| title_sort | об общем представлении числовых графов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84871 |
| work_keys_str_mv | AT donecga obobŝempredstavleniičislovyhgrafov AT šulinokié obobŝempredstavleniičislovyhgrafov AT donecga aboutgeneralrepresentationofnumericalgraphs AT šulinokié aboutgeneralrepresentationofnumericalgraphs |