基于每个节点上的连接数随机生成图形

Question

我正在尝试根据我的一些数据生成图形。

该图应具有生成的，其中每个节点的边的数量等于随机数生成的码，其中k是节点的“索引”（大多是任意的）。

我的问题是，是否有实际方法来做这件事？我认为我需要更多的数据来确定浓度或另一种连接程度（n1-> n2-> n3），但我并不完全确定。

Answer 1

基本上想要以某种程度的序列（你想要随机的序列生成图形，但这不是相关）;这被称为图形实现问题这是如此解决了。由 havel-hakimi算法在算法将返回的意义上（如果可能的话）（这种序列称为图形），则具有所需度序列的（简单）图。请注意，不是 $ \ mathbb n $ 的所有有限序列都是图形的。任何序列，其成员和奇数的序列都不能由握手引理（哪个指出图中的所有度数的总和等于图中边缘数的2倍，因此即使是）。 此外，解决方案一般不唯一：学位序列<跨度=“数学容器”> $（2,2,2,2,2,2）$ 可以通过Cycle Graph $ c_6 $ size $ 6 $ 或不相交的联合 $ c_3 \ mathop {\ dot \ cup} c_3 $ 两个循环图 $ c_3 $ size 每次3美元。

用于编程语言的许多图形库具有此问题的算法的实现，例如Python库 networkx 。