определим так: каждая
определим так: каждая его вершина представляет множество вершин некоторой сильной компоненты графа G, дуга (i*, j*) cуществует в G* тогда и только тогда, когда в G существует дуга (i,j), такая, что i принадлежит компоненте, соответствующей вершине i*, а j - компоненте, соответствующей вершине j*. Граф G* называется конденсацией графа G.
Дополнения.
1. Доказать, что в конденсации графа не содержится циклов.
2. Доказать, что в ориентированном графе каждая вершина i может принадлежать только одной сильной компоненте.
3. В графе есть множество вершин P, из которых достижима любая вершина графа и которое является минимальным в том смысле, что не существует подмножества в P, обладающего таким свойством достижимости. Это множество вершин называется базой графа. Показать, что в P нет двух вершин, которые принадлежат одной и той же сильной компоненте графа G.
Показать, что любые две базы графа G имеют одно и то же число вершин.
Разработать программу нахождения базы графа. Схема
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
