О поиске кратчайших путей в числовых графах
Рассматриваются натуральные модульные графы. Исследуется проблема нахождения путей между вершинами связного графа. Предлагаются алгоритмы решения данной задачи....
Gespeichert in:
| Datum: | 2012 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/85014 |
| 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: | О поиске кратчайших путей в числовых графах / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 42-46. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85014 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-850142015-07-19T03:02:19Z О поиске кратчайших путей в числовых графах Шулинок, Г.А. Рассматриваются натуральные модульные графы. Исследуется проблема нахождения путей между вершинами связного графа. Предлагаются алгоритмы решения данной задачи. Розглядаються натуральні модульні графи. Досліджується проблема знаходження шляхів у таких графах. Пропонуються алгоритми, що розв'язують дану задачу. Natural Modular Graphs are considered. A problem to find paths in such graphs is investigated. Algorithms to solve this problem are proposed. 2012 Article О поиске кратчайших путей в числовых графах / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 42-46. — Бібліогр.: 4 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85014 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассматриваются натуральные модульные графы. Исследуется проблема нахождения путей между вершинами связного графа. Предлагаются алгоритмы решения данной задачи. |
| format |
Article |
| author |
Шулинок, Г.А. |
| spellingShingle |
Шулинок, Г.А. О поиске кратчайших путей в числовых графах Теорія оптимальних рішень |
| author_facet |
Шулинок, Г.А. |
| author_sort |
Шулинок, Г.А. |
| title |
О поиске кратчайших путей в числовых графах |
| title_short |
О поиске кратчайших путей в числовых графах |
| title_full |
О поиске кратчайших путей в числовых графах |
| title_fullStr |
О поиске кратчайших путей в числовых графах |
| title_full_unstemmed |
О поиске кратчайших путей в числовых графах |
| title_sort |
о поиске кратчайших путей в числовых графах |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85014 |
| citation_txt |
О поиске кратчайших путей в числовых графах / Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 42-46. — Бібліогр.: 4 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT šulinokga opoiskekratčajšihputejvčislovyhgrafah |
| first_indexed |
2025-07-06T12:09:50Z |
| last_indexed |
2025-07-06T12:09:50Z |
| _version_ |
1836899417702006784 |
| fulltext |
42 Теорія оптимальних рішень, 2012
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются натуральные
модульные графы. Исследуется
проблема нахождения путей
между вершинами связного гра-
фа. Предлагаются алгоритмы ре-
шения данной задачи.
Г.А. Шулинок, 2012
ÓÄÊ 519.8
ÓÄÊ 519.8
Ã.À. ØÓËÈÍÎÊ
Î ÏÎÈÑÊÅ ÊÐÀÒ×ÀÉØÈÕ ÏÓÒÅÉ Â
×ÈÑËÎÂÛÕ ÃÐÀÔÀÕ
Введение. Известно [1], что алгоритмы на
числовых графах могут быть намного эффек-
тивнее, чем для обычных графов, заданных
матрицами или списками связности. И если
экономия на памяти является очевидной (ли-
нейная память вместо квадратичной), то с
вычислительной сложностью все далеко не
так очевидно. В [2] была высказана гипотеза,
что для всех NP-полных задач на графах
найдется полиномиальный алгоритм на чи-
словых графах. И данная работа вносит опре-
делённый вклад в этом направлении.
Целью данной работы было найти аналог
алгоритма Дейкстры [3] для натуральных мо-
дульных графов. Алгоритм Дейкстры ис-
пользуется достаточно широко, и в многих
случаях на графах, которые могли быть
представлены в виде модульных или арифме-
тических.
Определение. Числовым графом назовем
такой граф ),,( fUXG , в котором X –
множество вершин, U – множество обра-
зующих, а f – функция связности, заданная
на множестве вершин, т.е. любые вершины
Xyx ∈, будут соединяться ребром лишь
тогда, когда Uyxf ∈),( . Если nX N= , то
граф называют натуральным. А если
yxyxf −=),( , то такой граф называют
модульным.
Рассмотрим сначала натуральный модуль-
ный граф (NM-граф) с двумя образующими.
Обозначим такой граф ),(NM 21 uun , где n –
число вершин графа, а множество об-
разующих },{ 21 uuU = .
О ПОИСКЕ КРАТЧАЙШИХ ПУТЕЙ В ЧИСЛОВЫХ ГРАФАХ
Теорія оптимальних рішень, 2012 43
Пусть вершины yx, соединены путём. Обозначим ),( YXP – путь,
соединяющий вершины x и y .
Пусть вершины, через которые проходит путь P , будут иметь коды
),,,( 21 yxxxx
P
k
PP == K . В таком случае, из определения графа вытекает, что
Uxx
PP ∈− 21 , Uxx
PP ∈− 32 , …, Uxx
P
k
P
k ∈−−1 т.е. 11 uxx
P
i
P
i =− + или
21 uxx
P
i
P
i =− + , ki <<0 . Таким образом можно предложить простой способ
нахождения пути в связном NM-графе.
Алгоритм 1. Нахождение пути в связном графе ),(NM 21 uun .
Исходные данные: NM-граф ),(NM 21 uun , 21 uu < . Необходимо найти путь
из вершины x в y , nyx ≤<<0 .
Шаг 1. Определим xyd −= .
Шаг 2. Если 0)(mod 1 ≡ud или 0)(mod 2 ≡ud , то стоп. Путь найден. Иначе
– переходим на следующий шаг.
Шаг 3. Если 0>d , то перейти к вершине 2uxx += , иначе – к вершине
1uxx −= . Перейти на шаг 1.
Докажем, что данный алгоритм 1 позволяет найти путь в графе.
Пусть вершины x и y соединены ребром. В таком случае алгоритм 1
остановится на шаге 2. Действительно, из того, что x и y соединены ребром
вытекает, что 1ud = или 2ud = , а значит, выполняется либо условие
0)(mod 1 ≡ud , либо 0)(mod 2 ≡ud .
Подобным образом, если вершины x и y соединены рёбрами,
порождёнными только одной из образующих, то условие на шаге 2 тоже будет
выполняться. Более того, из связности графа [4] вытекает, что 1),(НОД 21 =uu , а
значит, путь будет кратчайшим. Исключением будет случай когда 21 uud ⋅= , в
этом случае следует выбрать большую образующую.
Пусть вершины x и y соединены двумя рёбрами, причём эти ребра
порождены двумя разными образующими. В этом случае можно сказать, что
yuux =±± 21 . Исходя из того, что yx < и 21 uu < , имеет место равенство
yuux =−+ 12 , что соответствует итерации алгоритма 1.
В случае, когда между вершинами x и y более 2 рёбер, применяем
индукцию по вершинам, и, очевидно, что алгоритм 1 обеспечивает построение
пути. В то же время нельзя сказать, что все пути, полученные в результате
работы алгоритма 1, будут кратчайшими.
Рассмотрим диофантово уравнение
dsuru =+ 21 . (1)
Г.А. ШУЛИНОК
44 Теорія оптимальних рішень, 2012
Кратчайший путь из вершины x в y отвечает условию
min→+ sr . (2)
В самом деле, путь из x в y исходя из алгоритма 1 можно представить в
виде ),( ba− , где a – количество рёбер, порождённых образующей 1u , а b –
рёбер, порождённых образующей 2u . Поскольку произвольный путь из
вершины x в y y будет удовлетворять уравнению (1), то для найденного пути
),( ba− можно предложить такое соотношение:
( )kubkua 12 , −+− , Z∈k . (3)
Из соотношения (3) становится очевидным обоснованность алгоритма 1. В
то же время можно построить алгоритм, который будет находить кратчайший
путь в графе.
Рассмотрим граф )5,3(NM12 .
Найдем путь из вершины 1 в вершину 9. Такие пути можно построить сле-
дующим образом:
1) 1→6→9;
2) 1→4→9;
3) 1→6→11→8→5→2→7→12→9
4) 1→4→7→10→5→8→3→6→9 и т.д.
Исходя из первого пути и применив формулу (3) имеем:
( )kk 31,51 −+ , Z∈k . (4)
Из соотношения (4) видно, что пути (1) и (2) эквивалентны, путь (3) получа-
ется при 1−=k , а (4) при 1=k . Из линейности соотношений (3) вытекает, что
минимум соотношения (2) достигается в данном случае при 0=k , т. е. крат-
чайший путь, соединяющий вершины 1 и 9, состоит из двух рёбер.
Если в графе найти путь из вершины 1 в 2, то получится следующее реше-
ние уравнения: 153 =+ sr , решения которого по алгоритму 1 можно записать
так: ( )kk 32,53 −+− , Z∈k .
И как результат, при 1=k длина пути будет 3, при 0=k – 5, а при 2=k –
11. Итак, из частного решения, которое мы получаем из алгоритма 1, можно по-
лучить минимальное решение.
Заметим, что образующие входят в кратчайший путь с разными знаками, в
отличие от алгоритма 1, где образующая 1u всегда со знаком «-», а образующая
2u – со знаком «+». Построим итеративную процедуру, при которой выбирается
подходящая образующая и её знак на каждый элемент пути.
Рассмотрим путь из вершины 1 в 8. В этом случае кратчайший путь будет
иметь вид (-1,2) или 1→6→3→8. Определим разности 7181 =−=d ,
2682 =−=d , 5383 =−=d . Как видно, 21 ud > , 12 ud < , а 23 ud = . Таким об-
разом видно следующий подход: если 21 ud > , то имеет смысл использовать об-
О ПОИСКЕ КРАТЧАЙШИХ ПУТЕЙ В ЧИСЛОВЫХ ГРАФАХ
Теорія оптимальних рішень, 2012 45
разующую 2u до тех пор, пока это условие выполняется. Иначе говоря, пока
22 )(mod0 uud << . В самом деле, если 0)(mod 2 ≡ud , то путь представляет со-
бой
2u
d
рёбер, порождённых образующей 2u , а в противоположном случае –
2ud < . С другой стороны, если 10 ud << , то кратчайший путь состоит из по-
следовательности применения обеих образующих, при этом образующая 1u
входит со знаком «+», а образующая 2u в – со знаком «–». Если 21 udu << , то
кратчайший путь состоит из ряда применений обеих образующих с разными
знаками. Так для графа )5,3(NM12 возможны такие пути длины 4 из 1 в 5
( )53( << d ):
1) 1→4→7→10→5 (+3,+3,+3,-5);
2) 1→4→7→2→5 (+3,+3,-5,+3);
3) 1→6→11→8→5 (+5,+5,-3,-3);
4) 1→6→3→8→5 (+5,-3,+5,-3).
Таким образом, возможны различные кратчайшие пути. Однако обнаружи-
вается следующее свойство: если 2)2(mod ≡d , то образующая 1u входит в
кратчайший путь со знаком «+», а если 1)2(mod ≡d , то со знаком «–». Также
особый случай )( 12 uud −= , когда выбирается образующая 1u со знаком «–» и
при этом чётность d не играет роли.
Например, при нахождении кратчайшего пути из 1 в 2 по такому варианту
будем иметь следующий сценарий:
11 1 ud <= . Выбираем образующую 3, переходим в вершину 4.
02422 <−=−=d . Меняем направление поиска: идём из 2 в 4.
12 2 ud <=′ , но 122 uu −= . Значит, имеем либо -3, либо +5. Образующая -3
не подходит (2-3 <1), значит, из вершины 2 в 7 идём с помощью 5.
13 47 ud =−= – поиск окончен.
Полученный путь (1, 4, 7, 2) является кратчайшим, что можно определить из
соотношения (3) полученного подстановкой частного решения (2, -1).
Таким образом, можно предложить алгоритм построения кратчайшего пути
между произвольными вершинами графа ),(NM 21 uun .
Алгоритм 2. Нахождение кратчайшего пути в графе ),(NM 21 uun .
Исходные данные: связный граф ),(NM 21 uun ; ищется кратчайший путь из
вершины x в y , nyx ≤<<0 .
Шаг 1. Вычислим xyd −= .
Шаг 2. Если 0)(mod 1 ≡ud или 0)(mod 2 ≡ud , то стоп – путь найден. Иначе
– перейти на следующий шаг.
Г.А. ШУЛИНОК
46 Теорія оптимальних рішень, 2012
Шаг 3. Если ( )( ) 0mod 12 ≡− uud , то путь найден, стоп. Иначе – перейти на
шаг 4.
Шаг 4. Если 0<d – изменить направление поиска, dd −=′ , yx =′ , xy =′ .
Шаг 5. Если 1ud < , то 1uxx += , иначе если 2ud > , то 2uxx += , иначе,
если 1)2(mod ≡d , то 2uxx += , иначе 1uxx += . Перейти на шаг 1.
Заметим, что вычислительная ёмкость алгоритма 2 не превышает ёмкости
алгоритма 1, а в среднем даже будет меньше, поскольку пути, получаемые с по-
мощью алгоритма 2 короче.
С другой стороны, легко увидеть, что в алгоритме 2 образующие входят в
путь только со знаком «+». Чтобы определиться с этим требуется учитывать
знак первой итерации.
Заключение. Полученные результаты показывают, что использование чи-
словых графов позволяет получить более эффективные алгоритмы, требующие
меньшего времени вычисления и памяти.
Развитие данной работы будет направлено на нахождение подобных алго-
ритмов и для других известных подклассов числовых графов.
І.Е. Шулінок, Г.О. Шулінок
ПРО НАЙКОРОТШІ ШЛЯХИ У ЧИСЛОВИХ ГРАФАХ
Розглядаються натуральні модульні графи. Досліджується проблема знаходження шляхів у
таких графах. Пропонуються алгоритми, що розв'язують дану задачу.
I.E. Shulinok, G.A. Shulinok
ABOUT SHORTEST PATHS IN NUMERICAL GRAPHS
Natural Modular Graphs are considered. A problem to find paths in such graphs is investigated.
Algorithms to solve this problem are proposed.
1. Донец Г.А.,Шулинок И.Э. О сложности алгоритмов поиска в глубину на модульных
графах // Теория оптимальных решений. – К.: Ин-т кибернетики им. В.М.Глушкова
НАН Украины, 2002. – С. 105–110 .
2. Донец Г.А.,Шулинок И.Э. Об оценке сложности алгоритмов для натуральных
модульных графов // Теория оптимальных решений. – К.: Ин-т кибернетики им.
В.М.Глушкова НАН Украины, 2001. – С. 61–68.
3. Харари Ф. Теория графов. – М.:Мир, 1973. – 301 с.
4. Шулинок И.Э. О связности натуральных модульных графов // Кибернетика и
системный анализ. – 1998. – № 5. – С. 50–53 .
Получено 14.05.2012
|