Отрывок: Т е о р е м а 2» Если граф G имеет гамильтонову цепь, то число ребер его минимального покрытия Р равно ]п/2Г» Д о к а з а т е л ь с т в о . Пусть граф Р имеет гамиль тонову цепь. С-уграф, состоящий из ребер этой цепи, имеет степени вершин, не превосходящие 2» Выбрав вершину суграфа графа О со степенью I и начав с нее, построим чередующуюся цепь [3]9 оп ределяющую максимальное паросочетание R . Если R покрывает все вершины г...
Название : | Применение теории графов для автоматизации синтеза вычислительных алгоритмов |
Авторы/Редакторы : | Дубина С. М. |
Дата публикации : | 1979 |
Библиографическое описание : | Дубина, С. М. Применение теории графов для автоматизации синтеза вычислительных алгоритмов. - Текст : электронный / С. М. Дубина // Автоматизация экспериментальных исследований : тр. Всесоюз. науч.-техн. конф. (5-7 июня 1978 г.). - Текст : электронный / М-во высш. и сред. спец. образования РСФСР, Куйбышев. авиац. ин-т им. С. П. Королева ; [редкол.: В. А. Виттих, А. И. Павлюк, В. П. Дерябкин, М. А. Кораблин, И. А. Будячевский, П. А. Соколов]. - 1979. - С. 106-110 |
Аннотация : | Приводится формулировка задачи поиска алгоритмической информации в терминах теории графов, а также доказывается ряд теорем, позволяющих решать сформулированную задачу методами дискретного программирования. |
URI (Унифицированный идентификатор ресурса) : | http://repo.ssau.ru/handle/Avtomatizaciya-eksperimentalnyh-issledovanii/Primenenie-teorii-grafov-dlya-avtomatizacii-sinteza-vychislitelnyh-algoritmov-95262 |
Другие идентификаторы : | RU\НТБ СГАУ\474069 |
Ключевые слова: | теория графов формализованное проектирование автоматизация систем проектирования методы дискретного программирования |
Располагается в коллекциях: | Автоматизация экспериментальных исследований |
Файлы этого ресурса:
Файл | Размер | Формат | |
---|---|---|---|
Стр.-106-110.pdf | 193.85 kB | Adobe PDF | Просмотреть/Открыть |
Показать полное описание ресурса
Просмотр статистики
Поделиться:
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.