2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Калькулятор графов
Сообщение08.03.2025, 12:30 
Здравствуйте.

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

 
 
 
 Re: Калькулятор графов
Сообщение08.03.2025, 12:35 
Но ведь граф не однозначно задаётся количеством вершин и их степенями... Например, если у вас 6 вершин и степени всех вершин равны 2, то может быть как один цикл длины 6, так и два цикла длины 3 (это если граф простой).

 
 
 
 Re: Калькулятор графов
Сообщение08.03.2025, 13:14 
Да, конечно, Вы правы. Но нет никакой программы, ни с какими условиями, я не нашёл.

 
 
 
 Re: Калькулятор графов
Сообщение08.03.2025, 14:17 
https://en.wikipedia.org/wiki/Havel%E2% ... _algorithm

 
 
 
 Re: Калькулятор графов
Сообщение08.03.2025, 15:10 
Аватара пользователя
Можно еще в MIP посчитать:

(код (gmpl))

Код:
param num_nodes := 5;
param num_arcs := 5;

set nodes:= 1..num_nodes;
set arcs := 1..num_arcs;

var inc{n in nodes, a in arcs}, binary;

param deg{n in nodes};

s.t. arc_rule{a in arcs}: sum{n in nodes} inc[n, a] = 2;
s.t. degs{n in nodes}: sum{a in arcs} inc[n, a] = deg[n];

solve;

printf 'node; arc \n' > 'res.txt';
printf{n in nodes, a in arcs: inc[n, a] > 0} '%2d; %2d \n', n, a >> 'res.txt';

data;

param deg:=
1 2
2 2
3 2
4 2
5 2
;

Чего-то выдает:

(результат)

Код:
node; arc
1;  1
1;  2
2;  1
2;  2
3;  3
3;  5
4;  4
4;  5
5;  3
5;  4

 
 
 
 Re: Калькулятор графов
Сообщение08.03.2025, 15:35 
tolstopuz в сообщении #1677829 писал(а):
https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm

Большое спасибо за ответ, очень интересный алгоритм.

 
 
 
 Re: Калькулятор графов
Сообщение09.03.2025, 16:07 
ТЕМА ЗАКРЫТА.
Спасибо всем кто отвечал на вопрос.

На другом форуме хороший человек kitonum прислал исчерпывающий ответ:

Изображение

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group