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

@lunarkiller · Регистрация: 23.12.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте, у меня такая проблема ,по матрице смежности (7x7) со случайными числами я получил граф в котором присутствуют треугольники, не могли бы вы помочь , как вывести их количество.

@VSI · 02.09.2014, 23:51

Приведите свои попытки решения этой задачи...

@lunarkiller · 03.09.2014, 16:23 **[ТС]**

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

@tvoretsmira · 03.09.2014, 17:56

То есть вы сделали что-то такое:

Matlab M
1
2
3
Coordinates=rand(7,2)
A=randi([0,1],[7,7])
gplot(A,Coordinates,'-*')

Получили картинку:

и пытаетесь придумать програмку, которая сама бы посчитала, что на картинке 7 триугольников?

@lunarkiller · 03.09.2014, 18:53 **[ТС]**

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".

@lunarkiller · 03.09.2014, 20:13 **[ТС]**

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'));

@tvoretsmira · 04.09.2014, 00:13

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;

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .

@lunarkiller 0 / 0 / 0 Регистрация: 23.12.2011 Сообщений: 53

	Работа с графом 02.09.2014, 21:28. Показов 6658. Ответов 6 Метки нет (Все метки) Здравствуйте, у меня такая проблема ,по матрице смежности (7x7) со случайными числами я получил граф в котором присутствуют треугольники, не могли бы вы помочь , как вывести их количество. 0

@VSI Модератор $Эксперт по математике/физике$ 5291 / 4073 / 1392 Регистрация: 30.07.2012 Сообщений: 12,489
	02.09.2014, 23:51
	Приведите свои попытки решения этой задачи... 0

@lunarkiller 0 / 0 / 0 Регистрация: 23.12.2011 Сообщений: 53
	03.09.2014, 16:23 [ТС]
	Простите , я недавно начал осваивать матлаб, поэтому не очень хорошо разбираюсь в его синтаксисе. Я так понимаю, что мне надо построить условие которое бы, во-первых, искало бы две вершины не равные нулю и не равных между собой, проверяла бы чтобы третья вершина, имеющая в себе начальные и конечные координаты первой и второй, также была не равная нулю и все это в цикле пока матлаб не проверит все точки. 0

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

Решение