Теория графов и комбинаторика

L'. ./«орядочить pedpa графа й в порядке "еубывания ввоон U. iis'iart о первого ребра, добавлять ребра к Т так, что<5ы 3.0 iiu 111.ПБ0ДПЛ0 к появ^тешд-и цикла в Т . 4 . Ис •'орягь п.З до тех гюр, когда IИСТ)!~У1~ i • b. По.чучвтюв дерево Т ЯЕ^1яатоя кратчайш?л оотавом граф?' С-. AjirojBTM Краокала хорош, когда чиоло ребор -•рафа 9 мато. Если i^paj (у являотся полни.!, т . е . <т=»Ки . то набор возможных ребер наибольший л / ) ( ' СКи ) | =и ( и - ' 1 ) /Д/ . Для таких олу- чаеп удобно применять алгоритм Прима. Лдготеигл Пгя1ма; ' 1 . агбратъ произвольную вершину и рассмотреть дерево =iVj!,,Xi), то Vf,- 'г. Для каздой верП!И!Ш ^ 7^ найти :,аршину 1^ <51'^ , такую, что и ирипиоатъ вершине V j мотку Если такой вершины нет, т . е . r C i ^ j n T ^ =• ^ , приписать вершнна 1^' м9ткуС £ ','=^1 3 . Шбратъ Ёериину liK' » такую, что ОбноЕить данные: V ^ s V ^ U i ' ^ » ! , Х4 i. 1 Н • Если •= i-i , то минимальное дерево найдено. Если / V.5 ( it и , то дэрейти к п . 4 . 4 . Для всех f i Т4, , таких, nrolTj ^TCt^n), изменить меткЕ оледуюишм образом: если > С (<^*j ) , то положить h и перейти к - .З; если |>j ^ CC^f/ij)' перейти к п.З. §12.7. A J / PHTH паокраски гшй о в Приведем некоторый эвристичоокий алго;7:1тм раокрашвания графов, позволяющей найти приближенное значение громатичеокого числа. Пуоть С~ 0 ^ ) Х ) - овязшс" ."•раф о И) вершинами. 1 . Воем вершинам г рафа ^ присвоить метку 1. Обозначить Дек], K »f, V) - множества варпшн, имеющих метку К . Половить А С О - V > * V!CK)=SJ0^^ , 2, П ОЛОЖИТЬ К Я'!. 76