8.7. Ответы на задачи

Задача 8.1: То, что не будет циклов, видимо, можно доказывать многими способами. Приведу идею самого простого из пришедших мне сейчас в голову доказательств. Пронумеруем все вершины в том порядке, в котором мы их находили. В дереве поиска в глубину из каждой вершины \(u\) выходим несколько (ноль или больше) рёбер в её «сыновья» — вершины, которые мы нашли из \(u\), значит, их номера больше, чем у \(u\), — а также ровно одно ребро в «предка» — вершину, из которой мы нашли \(u\) (такие ребра есть у всех вершин, кроме корня) — номер этой вершины меньше, чем у \(u\). Пусть есть цикл. Рассмотрим в нем вершину с наибольшим номером. В неё входят два ребра, принадлежащие этому циклу, и потому идущие и вершин с меньшими номерами, чем у нашей. Противоречие.

В случае связного графа это всегда будет остовное дерево графа, т.е. покрывающее все вершины. Но в случае несвязного графа это будет или остовное дерево одной компоненты связности — если запускаем просто \(find(i)\), — или остовный лес, покрывающий все вершины — если запускаем вторым из перечисленных в разделе Как вызывать процедуру способом.

Задача 8.2: Ясно, что, если в текущей компоненте связности некоторые элементы массива \(was\) изначально были ненулевыми, то в эти вершины мы не войдём. Скорее всего, это немного не то, что мы хотели (хотя, конечно, все зависит от задачи. Могут быть задачи, хотя я таких с ходу не припомню, в которых нам именно это и надо).

Задача 8.3: Да, конечно, количество решений равно \(2^k\), где \(k\) — количество компонент связности графа. В пределах одной компоненты есть два способа раскраски, отличающиеся инвертацией всех вершин.

Вообще, есть элементарная неоднозначность: можно инвертировать все вершины сразу и получить новое решение — значит, решение всегда неоднозначно. Но даже если решения, отличающиеся инвертацией всех вершин, считать одинаковыми, то все равно в несвязных графах решение неоднозначно.

Контрольный вопрос 8.4: Конечно, на вопрос «является ли данный граф двудольным».

Задача 8.5: Ну что-нибудь в следующем стиле (конечно, поиск в ширину я реализую очередью)

var q:array[1..n] of integer;
    was:array[1..n] of integer;
    l,r:integer;
    cur:integer;
    j:integer;
...
fillchar(was,sizeof(was),0);
l:=1;r:=1;
q[1]:=1;
was[1]:=1;
while l<=r do begin
      cur:=q[l];
      inc(l);
      for j:=1 to n do
          if (gr[cur,j]<>0)and(was[j]=0) then begin
             was[j]:=3-was[cur];
             inc(r);
             q[r]:=j;
          end;
end;

Массив \(q\) — очередь, массив \(was\) — номера доли. Это работает для связного графа, в противном случае ещё нужен внешний цикл с проверкой \(was\). Надеюсь, тут ошибок немного.

Задача 8.6: Ну понятно, почему :) Для двудольности, покрасив одну вершину, мы тут же знаем, как красить соседние с ней, т.к. есть всего два варианта, а один из них уже занят. В трехдольности так не получится.

Задача 8.7: Собственно, в подсказке я уже сказал, как надо все делать. Осталось привести пример программы.

procedure find(i,p:integer);
begin
if was[i]<>0 then begin
   не дерево!
   exit;
end;
was[i]:=1;
for i:=1 to n do
    if (gr[i,j]=1)and(j<>p) then
       find(j,i);
end;

Дополнительный параметр \(p\) здесь — номер вершины-предка. Вызываем эту процедуру из главной программы, конечно, передавая в качестве вершины-предка номер несуществующей вершины, например, ноль, если нумеруем вершины с единицы.

Да, ещё не забудьте, что для проверки, является ли граф деревом, надо запустить \(find(1)\) и проверить, что вы побывали во всех вершинах, а для проверки, является ли граф лесом, надо пробежаться по всем вершинам и запускать \(find\) оттуда, где ещё не бывали.

Задача 8.8: Окончательный критерий — если в графе степени всех вершин чётны плюс все компоненты связности, кроме, может быть, одной, состоят из одной вершины (т.е. это связный граф и ещё несколько изолированных вершин).

Задача 8.9: Ну что тут писать-то? Все сказано в абзаце перед задачей.

Задача 8.10: Критерий такой: ровно одна вершина с исходящей степенью на единицу больше входящей, и ровно одна — со входящей, на единицу большей исходящей; у остальных эти степени должны быть равны. Ну и обычные условия на связность. Пишется так же, как и эйлеров цикл в орграфе, только сначала надо найти ту самую вершину, где входящая на единицу больше исходящей (именно так, т.к. мы пойдём по инвертированным рёбрам!)

Контрольный вопрос 8.11: Ясно, что могут быть ациклические графы — не деревья. Например, три вершины и ребра \(1\to 2\), \(1\to 3\) и \(2\to 3\). Если снимем ориентацию с рёбер, то могут появиться циклы, которых раньше не было из-за того, что ребра были ориентированы.

Задача 8.12: Приведу код, только сначала несколько комментариев про хранение графа списком смежных вершин. Буду использовать настоящие списки, т.е. [2]

type tv=record
          v:integer;
          next:pv;
       end;
     pv=^tv;
var gr:array[1..maxN] of pv;

Здесь \(tv\) — очередной элемент списка, хранящий одно ребро (т.е. одну смежную вершину):. \(v\) — номер этой вершины, \(pv\) — указатель на следующее ребро (на следующий элемент типа \(tv\)), или \(nil\), если такого ребра нет. \(gr\) хранит граф: для каждой вершины — указатель на первое ребро, входящее в эту вершины (или \(nil\), если таких рёбер нет).

В данной задаче мы будем хранить только входящие ребра, т.к. исходящие нам не нужны (я говорил об этом в подсказке). В других случаях для ориентированного графа могут понадобиться два массива отдельно для входящих и исходящих рёбер; для неориентированного графа, конечно, нужен один массив.

Алгоритм:

...
var st:array[1..maxN] of integer;
    nst:integer;
    d:array[1..maxN] of integer;
    u,v:integer;
    n,m:integer;
    nv:pv;
    ans:array[1..maxN] of integer;
    pos:integer;

begin
...
fllchar(gr,sizeof(gr),0);
fillchat(d,sizeof(d),0);
read(f,n,m);
for i:=1 to m do begin
    read(f,u,v);
    new(nv);
    nv^.v:=u;
    nv^.next:=gr[v];
    gr[v]:=nv;
    inc(d[u]);
end;
nst:=0;
for i:=1 to n do
    if d[i]=0 then begin
       inc(nst);
       st[nst]:=i;
    end;
pos:=n;
for i:=1 to n do begin
    {должно быть nst>0}
    v:=st[nst];
    dec(nst);
    ans[pos]:=v;
    dec(pos);
    nv:=gr[v];
    while nv<>nil do begin
          dec(d[nv^.v]);
          if d[nv^.v]=0 then begin
             inc(nst);
             st[nst]:=nv^.v;
          end;
          nv:=nv^.next;
    end;
end;

\(st\) — массив (стек) стоков; \(nst\) — количество элементов в нем (т.е. количество стоков в текущем графе). \(d\) — массив исходящих степеней (т.е. \(d[i]\) — исходящая степень \(i\)-ой вершины). \(ans\) — массив-ответ, \(pos\) — позиция в этом массиве, куда мы должны будем поставить очередную вершину.

Сначала считываем граф. Я специально привожу этот текст, чтобы вы видели, как хранить граф списком смежных вершин. Считаем, что граф задан списком рёбер: т.е. во входном файле сначала количества вершин (\(n\)) и рёбер (\(m\)), а потом по два числа на строке, задающие две вершины — откуда и куда идёт ребро. Поэтому считываем сначала эти количества, а потом сами ребра. Каждое ребро \(u\to v\) надо добавить в список рёбер, входящих в вершину \(v\), т.е. в список \(gr[v]\). Посмотрите, как это делается. Тут небольшая путаница с тем, что ребро идёт из вершины \(u\), поэтому приходится писать \(nv.v:=u\), но это мелочи. Может быть, можно было придумать более хорошие имена полям и переменным. Обратите внимание, что, как всегда при вставке в список, мы вставляем в его начало, а не в конец. Заодно параллельно считаем в массиве \(d\) исходящие степени.

После этого формируем начальный список стоков \(st\), пробегаясь по массиву \(d\) и ища там нули.

Далее основная часть. Мы должны \(n\) раз подряд взять сток, поставить его в выходной массив и удалить его из графа. Каждый раз сток точно найдётся, т.к. граф ациклический, поэтому все время должно быть \(nst>0\). Берём очередной сток (конечно, последний из массива \(st\) — его проще удалять, чем первый), удаляем его из массива \(st\) (командой \(dec(nst)\) просто), ставим в выходной массив и пробегаемся по входящим рёбрам, обратите внимание как. Для каждого ребра просто уменьшаем на единицу исходящую степень соответствующей вершины и, если она стала стоком, заносим её в массив \(st\). Частая ошибка здесь — забыть написать nv:=nv^.next, чтобы перейти к следующему ребру. Это вам не for, который переменную цикла автоматически увеличивает.

[2]Замечу, что это очень синтаксически странная конструкция: я использую идентификатор \(pv\) до того, как объяснил, что он значит. Паскаль такое допускает при выполнении двух условий: во-первых, все должно быть в одной «секции» type, во-вторых, должен быть определённый порядок: то ли сначала определён \(tv\), потом \(pv\), то ли наоборот, я сейчас точно не помню. Если этот код не компилится, поменяйте их местами.

Задача 8.13: Например, граф с двумя вершинами и одним ребром \(2\to 1\) связен, но при запуске поиска в глубину \(find(1)\) во вторую вершину мы не попадём.

Задача 8.14: Три вершины, три ребра: \(1\to 2\), \(1\to 3\), \(2\to 3\): запустившись \(find(1)\), мы два раза попробуем попасть в третью вершину.

Задача 8.15: Напрямую заменить нельзя, т.к. алгоритм Кнута не всегда даст какую-то последовательность вершин. Но наоборот: он даст какую-то последовательность вершин тогда и только тогда, когда граф ациклический. Т.е. приспособить алгоритм Кнута можно следующим образом: запускаем его и, если он нормально завершается, то граф ациклический, иначе нет. А что значит нормально завершается? Единственное, что ему может помешать — может оказаться, что в очередной момент \(nst=0\), т.е. в текущем графе нет стоков. Несложно понять, что это будет тогда и только тогда, когда граф не ациклический. Таким образом, может в алгоритм Кнута добавить одну проверку внутрь цикла и получить алгоритм проверки графа на ацикличность (а массив \(ans\) тогда, конечно, не нужен будет).

Задача 8.16: Рассмотрим тот граф, который приведён в подсказке: три вершины, два ребра: \(1\to 2\) и \(3\to 2\). В соответствии с нашим определением «компонент слабой связности» вершины 1 и 2 должны лежать в одной компоненте, 2 и 3 тоже, а 1 и 3 нет (т.к. ни от 1 до 3, ни от 3 до 1 добраться нельзя). Поэтом такое определение бессмысленно в том смысле, что вершины не получается разбить на компоненты слабой связности. Ясно, что проблема именно в том, что нарушается требование транзитивности. На самом деле, пусть про некоторые пары вершин (или вообще любых объектов), сказано, что эти пары «хорошие». Тогда, чтобы вершины можно было разбить на «компоненты хорошести», т.е. на группы такие, что в пределах каждой группы все пары хорошие, а между группами — нет, необходимо и достаточно выполнения трёх условия: рефлексивности (что каждая вершина сама с собой образует хорошую пару), симметричности (что если \(u\) и \(v\) хорошая пара, то и \(v\) и \(u\) тоже), и транзитивности (если \(u\) и \(v\) хорошая пара, и \(v\) и \(w\) тоже, то и \(u\) и \(w\) тоже).

Задача 8.17: Пример графа, для которого такой алгоритм не работает: три вершины, ребра \(1\to 3\), \(3\to 1\) и \(1\to 2\). Если запустим первый поиск в глубину из вершины 1, то результат «топсорта» будет именно порядок 1, 2, 3, и, пойдя в неинвертированном графе справа налево, запустившись первым же запуском \(find(3)\), мы посетим все три вершины, что неправильно. Как «на пальцах» объяснить, чем таким этот алгоритм отличается от верного, я не знаю.

Задача 8.18: Пусть в конденсации есть цикл. Но тогда возьмём две вершины этого цикла — пусть это вершины 1 и 2. В конденсации по этому циклу можно дойти и из 1 в 2, и из 2 в 1. Тогда возьмём в изначальном графе две вершины \(1'\) и \(2'\) из компонент сильной связности, соответствующих вершинам 1 и 2 конденсации. Несложно показать, что тогда и из \(1'\) в \(2'\) и в обратную сторону можно дойти в начальном графе, что противоречит тому, что они лежат в разных компонентах сильной связности.

Задача 8.19: Несложно видеть, что топсорт как раз и сортирует вершины по времени выхода, только в порядке убывания. Он ведь на последнее место в выходном массиве ставит вершину, из которой мы вышли первой, и т.д. Поэтому сортировать вершины по времени выхода надо аналогично топсорту. По времени входа сортировать тоже аналогично, только ставить вершину в выходной массив надо в начале процедуры \(find\). Это чем-то аналогично сортировке подсчётом.

Задача 8.20: Для мостов можно. Для точек сочленения нет, т.к. может оказаться, что при удалении вершины старая компонента связности распадается сразу на три или ещё больше. Обратите также внимание, что нельзя говорить «мост — это такое ребро, при удалении которой граф распадётся на две компоненты связности» и аналогично для точек сочленения, т.к. не понятно, что это значит для несвязных графов, и в наиболее логичной трактовке для несвязных графов это неверно.

Задача 8.21: Я такой связи не знаю. а) нет, т.к. конец моста может оказаться висящей вершиной. Вообще, например, в графе с двумя вершинами и одним ребром (1–2) один мост, но ни одной точки сочленения. б) Очевидно, нет, и несложно придумать контрпример.

Задача 8.22: Пусть есть такое ребро. Рассмотрим тот конец его, в который мы попали раньше — пусть это вершина \(u\). К моменту, когда мы попали в него, во второй конец (\(v\)) мы ещё на заходили. Мы будем просматривать соседей вершины \(u\) и наткнёмся на \(v\). Если к этому моменту мы все ещё не были в \(v\), то мы в неё пойдём, \(v\) станет сыном и потому потомком \(u\) и ребро не будет перекрёстным. В противном случае мы успели побывать в вершине \(v\), пока обрабатывали других соседей вершины \(u\), значит, \(v\) — потомок \(u\) и ребро все равно не перекрёстное.

Контрольный вопрос 8.23: Ну понятно, переменная внешнего цикла, в котором мы запускаем поиск в глубину. См. раздел Как вызывать процедуру .

Задача 8.24: Приводить алгоритм тут не буду, пишите сами :)

Задача 8.25: Аналогично предыдущему. Мне кажется, что, если вы хорошо освоились с поиском в глубину, то придумать и написать этот алгоритм труда не должно составить.