ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ НА ГРАФАХ
Keywords:
Независимые множества, клики, вершинные покрытия, паросочетания, оптимальные каркасы, алгоритм Прима.Abstract
В статье предложены основные факты, касающиеся экстремальных задач теории графов, приведены основные теоремы с доказательствами. Показана достижимость оптимальных решений этих задач в рамках фрагментарной модели. Предложены приближенные алгоритмы поиска решений методом Прима.
References
Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Алгоритмы.– Н.Новгород, ННГУ, 2005. 307 с.
Зыков А.А. Основы теории графов.– М.: Вузовская книга, 2004. 664 с.
Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение.– СПб.: БХВ-Петербург, 2003. 1104 с.
Галкина В. А Дискретная математика. Комбинаторная оптимизация на графах - М.: Издательство "Гелиос АРВ", 2003. — 232 с.
Extremal problems on graphs, directed graphs and hypergraphs. T.D.Townsend School of Mathematics The University of Birmingham, August 2015, 232 Р.
Downloads
Published
How to Cite
Issue
Section
License

This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles published in IQRO — Scientific Methodological Journal are licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
Authors retain copyright and grant the journal the right of first publication.
Users may read, download, copy, distribute, print, search, or link to the full texts of articles, provided that the original authors and the journal are properly cited.
Published materials may be used, distributed, and reproduced in any medium, provided that the original work is properly cited.



Uzbekistan
Türkiye
Kazakhstan
Kyrgyzstan
Turkmenistan
Azerbaijan
India
Republic of Korea
Japan
United States of America
Kosovo