Является ли граф 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 21:03

[PORTUGAL]

Я ничего не шарю в дискретке и в графах, поэтому возник вопрос, что нужно заносить в массив a? Какие данные?

[Altair]

методы задания графов
см. матрица смежности + читай теорию графов.
+ faq графы
посмотри там программу, там есть процедура ввода вывода матрицы смежности.

[klem4]

Интересно, а как быть если бы вопрос стоял "свободным от n-уголников" ?

[Altair]

Тогда задача сводиться к решению задачи о поиске циклов в графе. ;)

[PORTUGAL]

Короче получилось вот что:

Код

Type
Graph = array[1..100,1..100] of longint;
Var
a:graph;
b:boolean;
i,j,n,k:integer;
BEGIN
write('n= ');
readln(n);
For i:=1 to n do
For j:=1 to n do
  begin
    write('G',i,',',j,'= ');
    readln(a[i,j]);
  end;
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[i,j]>0) and (a[j,k]>0) and (i<>j) and (j<>k)
   then b:=true;
if b then writeln('Svoboden!!!')
else writeln('Ne svoboden!!!');
readln;
end.

Вроде работает! Всем спасибо за помощь!