Калькулятор графов

[Andrew22]

Здравствуйте.

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

[dgwuqtj]

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

[Andrew22]

Да, конечно, Вы правы. Но нет никакой программы, ни с какими условиями, я не нашёл.

[tolstopuz]

https://en.wikipedia.org/wiki/Havel%E2% ... _algorithm

[пианист]

Можно еще в 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 

[Andrew22]

tolstopuz в сообщении #1677829 писал(а):

https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm

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

[Andrew22]

ТЕМА ЗАКРЫТА.
Спасибо всем кто отвечал на вопрос.

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