Доказательство корректности алгоритма нахождения максимальной антицепи в ориентированном ацикличном графе

Правка ru1, от 163onmyneck, 2021-08-15 15:59:24

Здравствуйте! Я не знаю доказательство этого алгоритма(( Если кто-то знает, можете пожалуйста написать доказательство в комментариях.

Алгоритм: 1) Первым шагом строим Транзитивное замыкание графа (если из A был путь в B, то в этом графе будет ребро из A в B). 2) "Копируем граф". Теперь у каждой вершины будет копия. Если в графе (в том, который мы получили после предыдущего шага) было ребро из A в B, то теперь есть ребро из вершины A, которая находится в левой доле в вершину B, которая находится в правой доле. (По сути теперь у вершины A есть две вершины: AL и AR) 3) В получившемся графе ищем максимальное независимое множество. 4) Теперь если у вершины V и VR и VL лежат в независимом множестве, то мы берем эту вершину в антицепь.

Теги графы, паросочетания, антицепи

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru5 Русский 163onmyneck 2021-08-15 16:02:31 25
ru4 Русский 163onmyneck 2021-08-15 16:01:20 2 Мелкая правка: 'лгоритм:\n- 1) Пер' -> 'лгоритм:\n\n- 1) Пер'
ru3 Русский 163onmyneck 2021-08-15 16:01:04 6
ru2 Русский 163onmyneck 2021-08-15 16:00:40 8
ru1 Русский 163onmyneck 2021-08-15 15:59:24 852 Первая редакция (опубликовано)