[recovery mode] Графы и программирование Что положить в основу классификации графов, какие их признаки и свойства? Единственного правильного ответа на вопрос нет. Естественная классификация пока не открыта поэтому пользуемся искусственной, которая создается конкретным автором для решения конкретного круга задач. Полезными признаками часто оказываются такие как количество вершин, ребер, распределение степеней вершин и др. Важно, что удается разделить все множество графов на классы и дальше работать с ограниченным множеством, не рискуя потерять оптимальный объект.
Характеристика связности графов часто описывается достижимостью из некоторой вершины графа всех других, а очевидное средство такой достижимости – проложенный между парой вершин путь. Наличие множества путей, покрывающих вершины и\или ребра (дуги) графа, обеспечивает часто решение целевых задач таких, например, как минимизация контрольных точек или тестирование программ. Затрагиваются вопросы и цикломатической сложности графа.
Вопросы синтеза и исследования управляющих графов программ остаются пожалуй самым надежным средством отладки и совершенствования программ для ЭВМ. Третья статья цикла освещает кратко эту актуальную тему. Параллельно для внешних программ реализуется процедура выявления программных закладок и своевременно не удаленных контрольных точек.
Читать далее