Построение гамильтонова пути в графах перестановочных многогранников
Розглянуто проблему розв’язання екстремальних задач на множині переставлень для лінійної функції. Побудовано граф многогранника допустимих значень цієї функції на переставленнях. Доведено, що цей граф частково-упорядкований відносно транспозиції двох елементів переставлення. Запропоновано спосіб, як...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2010 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/45121 |
| 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: | Построение гамильтонова пути в графах перестановочных многогранников / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2010. — № 1. — С. 10–16. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862610329423314944 |
|---|---|
| author | Донец, Г.А. Колечкина, Л.Н. |
| author_facet | Донец, Г.А. Колечкина, Л.Н. |
| citation_txt | Построение гамильтонова пути в графах перестановочных многогранников / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2010. — № 1. — С. 10–16. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто проблему розв’язання екстремальних задач на множині переставлень для лінійної функції. Побудовано граф многогранника допустимих значень цієї функції на переставленнях. Доведено, що цей граф частково-упорядкований відносно транспозиції двох елементів переставлення. Запропоновано спосіб, який використовує цю властивість побудови гамільтонового шляху в графі, що відповідає множині переставлень для n = 4.
The problem of finding an extremum of a linear function on a set of permutations is considered. The polyhedron of admissible values on the permutation set is constructed. The constructed graph is shown to be partially ordered with respect to the transposition of two elements of a permutation. Based on this property, a method is proposed for the construction of a Hamiltonian path on the graph corresponding to the set of permutations for n = 4.
|
| first_indexed | 2025-11-28T23:05:45Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-45121 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-28T23:05:45Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Колечкина, Л.Н. 2013-06-07T19:02:00Z 2013-06-07T19:02:00Z 2010 Построение гамильтонова пути в графах перестановочных многогранников / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2010. — № 1. — С. 10–16. — Бібліогр.: 13 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45121 519.1 Розглянуто проблему розв’язання екстремальних задач на множині переставлень для лінійної функції. Побудовано граф многогранника допустимих значень цієї функції на переставленнях. Доведено, що цей граф частково-упорядкований відносно транспозиції двох елементів переставлення. Запропоновано спосіб, який використовує цю властивість побудови гамільтонового шляху в графі, що відповідає множині переставлень для n = 4. The problem of finding an extremum of a linear function on a set of permutations is considered. The polyhedron of admissible values on the permutation set is constructed. The constructed graph is shown to be partially ordered with respect to the transposition of two elements of a permutation. Based on this property, a method is proposed for the construction of a Hamiltonian path on the graph corresponding to the set of permutations for n = 4. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Построение гамильтонова пути в графах перестановочных многогранников Побудова гамільтонового шляху в графах переставного многогранника Construction of Hamiltonian paths in graphs of permutation polyhedrons Article published earlier |
| spellingShingle | Построение гамильтонова пути в графах перестановочных многогранников Донец, Г.А. Колечкина, Л.Н. Кибернетика |
| title | Построение гамильтонова пути в графах перестановочных многогранников |
| title_alt | Побудова гамільтонового шляху в графах переставного многогранника Construction of Hamiltonian paths in graphs of permutation polyhedrons |
| title_full | Построение гамильтонова пути в графах перестановочных многогранников |
| title_fullStr | Построение гамильтонова пути в графах перестановочных многогранников |
| title_full_unstemmed | Построение гамильтонова пути в графах перестановочных многогранников |
| title_short | Построение гамильтонова пути в графах перестановочных многогранников |
| title_sort | построение гамильтонова пути в графах перестановочных многогранников |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45121 |
| work_keys_str_mv | AT donecga postroeniegamilʹtonovaputivgrafahperestanovočnyhmnogogrannikov AT kolečkinaln postroeniegamilʹtonovaputivgrafahperestanovočnyhmnogogrannikov AT donecga pobudovagamílʹtonovogošlâhuvgrafahperestavnogomnogogrannika AT kolečkinaln pobudovagamílʹtonovogošlâhuvgrafahperestavnogomnogogrannika AT donecga constructionofhamiltonianpathsingraphsofpermutationpolyhedrons AT kolečkinaln constructionofhamiltonianpathsingraphsofpermutationpolyhedrons |