Является ли граф G, свободным от треугольников... Опции

[PORTUGAL]

Написать программу, которая давала бы ответ на вопрос, является ли поданный на ее вход граф G, свободным от треугольников или нет.

Может у кого ест исходник такой проги, если нет то пожалуйста подскажите хотя бы алгоритм решения.

[Altair]

Все просто.

b:=false;
for i:=1 to n do 
   for j:=1 to n do
       for k:=1 to n do
           if (a[i,j]>0) and (a[i,k]>0) and (a[j,k]>0) and (i<>j) and (j<>k) then b:=true;

a - матрица смежности.
b - содержит ответ.

только перебор еще можно сократить...
i:=1 to n-2
j:=i+1 to n-1
k:=j+1 to n
тогда не надо проверять что i j k разные..

Сообщение отредактировано: Altair - 12.02.2006 17:03