Помощь - Поиск - Пользователи - Календарь
Полная версия: Является ли граф G, свободным от треугольников...
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
PORTUGAL
12.02.2006 19:18
Написать программу, которая давала бы ответ на вопрос, является ли поданный на ее вход граф G, свободным от треугольников или нет.

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

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 разные..
PORTUGAL
12.02.2006 21:47
Я ничего не шарю в дискретке и в графах, поэтому возник вопрос, что нужно заносить в массив a? Какие данные?
Altair
12.02.2006 21:49
методы задания графов
см. матрица смежности + читай теорию графов.
+ faq графы
посмотри там программу, там есть процедура ввода вывода матрицы смежности.
klem4
12.02.2006 22:41
Интересно, а как быть если бы вопрос стоял "свободным от n-уголников" ?
Altair
12.02.2006 22:54
Тогда задача сводиться к решению задачи о поиске циклов в графе. ;)
PORTUGAL
13.02.2006 5:26
Короче получилось вот что:
Код

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.


Вроде работает! Всем спасибо за помощь!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.