Форум программистов, компьютерный форум, киберфорум
Matlab
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.62/21: Рейтинг темы: голосов - 21, средняя оценка - 4.62
0 / 0 / 0
Регистрация: 23.12.2011
Сообщений: 52
1

Работа с графом

02.09.2014, 21:28. Просмотров 3919. Ответов 6
Метки нет (Все метки)


Здравствуйте, у меня такая проблема ,по матрице смежности (7x7) со случайными числами я получил граф в котором присутствуют треугольники, не могли бы вы помочь , как вывести их количество.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.09.2014, 21:28
Ответы с готовыми решениями:

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

Работа с неориентированным графом
Есть неориентированный граф 4х4, нужно составить алгоритм, который бы находил пути в которых...

Работа с Ориентированным графом
Дан орграф. После удаления произвольных вершин может произойти всё что угодно, вопрос таков: Для...

Работа с графом. Помощь в алгоритме
Помогите с подбором алгоритма для работы с данным заданием. Я рассматривал алгоритм...

__________________
Помогаю в написании курсовых работ и дипломов здесь.
6
Модератор
Эксперт по математике/физике
4722 / 3614 / 1225
Регистрация: 30.07.2012
Сообщений: 10,311
02.09.2014, 23:51 2
Приведите свои попытки решения этой задачи...
0
0 / 0 / 0
Регистрация: 23.12.2011
Сообщений: 52
03.09.2014, 16:23  [ТС] 3
Простите , я недавно начал осваивать матлаб, поэтому не очень хорошо разбираюсь в его синтаксисе. Я так понимаю, что мне надо построить условие которое бы, во-первых, искало бы две вершины не равные нулю и не равных между собой, проверяла бы чтобы третья вершина, имеющая в себе начальные и конечные координаты первой и второй, также была не равная нулю и все это в цикле пока матлаб не проверит все точки.
0
460 / 450 / 56
Регистрация: 28.05.2013
Сообщений: 699
03.09.2014, 17:56 4
То есть вы сделали что-то такое:
Matlab M
1
2
3
Coordinates=rand(7,2)
A=randi([0,1],[7,7])
gplot(A,Coordinates,'-*')
Получили картинку:
Работа с графом

и пытаетесь придумать програмку, которая сама бы посчитала, что на картинке 7 триугольников?
0
0 / 0 / 0
Регистрация: 23.12.2011
Сообщений: 52
03.09.2014, 18:53  [ТС] 5
tvoretsmira,
Я немножечко ошибся, матрицу смежности я задаю сам путем:
Matlab M
1
2
3
4
5
6
7
8
9
10
11
 Num = 7;
G = zeros(Num,Num);
 
G(1,2)= 1;
G(2,6)= 4;
G(3,1)= 3;
G(4,1)= 2;
G(5,4)= 2;
G(6,4)= 1;
G(7,3)= 4;
G(7,5)= 1;
а случайными являются ребра, которые я добавляю в матрицу смежности с помощью созданной функции, так чтобы появились треугольники.
Но в целом вы совершенно правы я пытаюсь сделать именно то, что вы описали.
правдо графически реализую граф при помощи "biograph".
0
0 / 0 / 0
Регистрация: 23.12.2011
Сообщений: 52
03.09.2014, 20:13  [ТС] 6
tvoretsmira, Если не использовать функцию создания ребер, а просто добавить ребра G(3,5)=3 и G (1,7)=6
то получится такой граф:
Matlab M
1
2
3
4
W = [1 4 1 2 2 3 4 1 3 6 ];
 GH = sparse([1 2 6 4 5 3 7 7 3 1],[2 6 4 1 4 1 3 5 5 7],W, 7, 7);
M = {'A','B','C','D','E','F','G'};
view(biograph(GH,M,'ShowWeights','on','ShowArrows', 'off'));
Работа с графом
0
460 / 450 / 56
Регистрация: 28.05.2013
Сообщений: 699
04.09.2014, 00:13 7
Лучший ответ Сообщение было отмечено lunarkiller как решение

Решение

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function TriCount=CalcTriangles(G)
% G = матрица смежности
GM=(G+G.')~=0; % и получается симметричная матрица
n=size(GM,1);
TriCount3=0;
for ik=1:n
  if sum(GM(ik,:))>1 % узел связан более чем с одним узлом
    ind=find(GM(ik,:)); % номера узлов с которыми связан
    c = nchoosek(ind,2); % комбинации этих номеров парами
    for ig=1:size(c,1) % перебор по парам
      if GM(c(ig,1),c(ig,2))||GM(c(ig,2),c(ig,1)) % проверка наличия связи в паре
        TriCount3=TriCount3+1; % раз связь есть, значит триугольник найден
        disp(['Триугольник имеет вершины: ',num2str(ik),'  ',num2str(c(ig,:))])
      end
    end
  end
end
TriCount=TriCount3/3;
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.09.2014, 00:13

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь или здесь.

API/MFC работа с графом
помогите пожалуйста найти ошибку или дописать недостающее. только недавно полез в апи и мфс,поэтому...

Работа с графом.Найти кратчайший маршрут между двумя вершинами.
Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень...

Работа с графом (Требуется по заявке клиента предложить способы обмена жилплощади)
В файле записаны предложения по обмену жилплощадью. Имеются варианты размена одной квартиры на две...

Задача с графом
program prog; uses SysUtils; const n0 = 30; var ves : array of integer; L : array of...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.