数图论

图的维纳指数：反映图的扩散性的拓扑不变量

字数统计: 1.9k字   |   阅读时长: 7分
, , ,

摘要: 图的维纳指数，反映图的扩散性的拓扑不变量，图算法计算

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

图的维纳指数最初引入是在化学领域，用于描述分子结构，这是一个图上的拓扑不变量，1947 年由 Harry Wiener 提出。此后，维纳指数页用于社会关系、社交网络等领域，用于描述网络的紧密程度，或者扩散性，了解图的结构特性。

维纳指数

对于连通图 $G = (V, E)$，记 $d(u, v)$ 表示图中的 $u, v$ 两点间的最短距离，图 $G$ 的维纳指数 $W(G)$ 定义为所有可到达的两个点之间的最短距离之和：

图上的拓扑指数

维纳指数是图的一种拓扑指数，也就是在图的同构变换下保持不变的量。

类似于图的大小这样拓扑指数，虽然简单，但不一定能反映图的扩散性，紧密程度等。因此我们希望找到更多的拓扑指数用于描述一个图。

现在人们已经掌握了图上的很多拓扑指数，下面是几个例子，都可以视为维纳指数的加权版本。

Szeged 指数

对于边 $e = ij$，记 $n_{e}(i)$ 为连通图 $G$ 中距离 $i$ 比距离 $j$ 更近的点的个数，$n_{e}(j)$ 为图 $G$ 中距离 $j$ 比距离 $i$ 更近的点的个数，Szeged 指数 $\mathrm{Sz}(G)$ 定义为：

第一类 Schultz 指数

对于连通图 $G$，第一类 Schultz 指数定义如下：

其中 $d(v)$ 表示 $v$ 的度。

第二类 Schultz 指数

对于连通图 $G$，第二类 Schultz 指数也称为 Gutman 指数，定义如下：

计算图中的拓扑指数

Wiener 指数

以下图为例，看一下在 networkx 中如何计算图的维纳指数。

手算

首先根据公式手算一下，各个顶点对之间的最短距离如下：

将上述最短距离加起来，得到 $W(G) = \sum\limits_{u,v\in V}d(u, v) = 14$。

用 Networkx 组件

下面是在 networkx 中计算维纳指数的代码，得出的结果也为 14。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import matplotlib.pyplot as plt
import networkx as nx
from networkx.drawing.nx_pydot import graphviz_layout

G = nx.Graph()

# 顶点
for u in range(1, 6):
    G.add_node(u)

# 边
edges = [[1, 2]
        ,[2, 3]
        ,[1, 3]
        ,[3, 4]
        ,[4, 5]
        ,[1, 5]
        ]
for u, v in edges:
    G.add_edge(u, v)

# 图的拓扑变量：维纳指数
wi = nx.wiener_index(G)
print("维纳指数: {}".format(wi))

# 布局
pos = graphviz_layout(G)

nx.draw(G, pos, with_labels=True, arrows=False)
plt.axis("off")
plt.show()

Szeged 指数

以下图为例，看一下如何实现 Szeged 指数的计算。

将原图顶点编号后画出

首先将上图的顶点编号，画出来，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import matplotlib.pyplot as plt
import networkx as nx
from networkx.drawing.nx_pydot import graphviz_layout

G = nx.Graph()

# 顶点
for u in range(1, 13):
    G.add_node(u)

# 边
edges = [[1, 2]
        ,[2, 3]
        ,[3, 4]
        ,[4, 5]
        ,[5, 6]
        ,[6, 7]
        ,[7, 8]
        ,[8, 9]
        ,[9, 10]
        ,[10, 11]
        ,[11, 12]
        ,[1, 12]
        ,[1, 7]
        ,[2, 8]
        ,[3, 5]
        ,[4, 6]
        ,[9, 11]
        ,[10, 12]
        ]
for u, v in edges:
    G.add_edge(u, v)

# 布局
pos = graphviz_layout(G)

nx.draw(G, pos, with_labels=True, arrows=False)
plt.axis("off")
plt.show()

用图算法实现计算公式

按照 Szeged 指数的定义，我们需要对每一条边 $ij$，枚举其他顶点 $v\in V, v\neq i, v\neq j$，其中 $d(i, v) < d(j, v)$ 的个数记为 $n_{e}(i)$，$d(i, v) > d(j, v)$ 的个数记为 $n_{e}(j)$。

step1：首先预处理所有顶点对之间的最短距离：

算法的原理参考 Floyd算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
INF = 1e10

edges = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7]
        ,[7, 8], [8, 9], [9, 10], [10, 11], [11, 12], [1, 12]
        ,[1, 7], [2, 8], [3, 5], [4, 6], [9, 11], [10, 12]
        ]
n = 12

d = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
for u in range(1, n + 1):
    d[u][u] = 0
for u, v in edges:
    d[u][v] = 1
    d[v][u] = 1
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

for row in d:
    print(row)

编号后的图以及所有顶点对之间的最短距离如下：

step2：按公式 $\mathrm{Sz}(G) = \sum\limits_{e=ij\in E}n_{e}(i)n_{e}(j)$ 计算 Szeged 指数：

枚举每条边 $ij \in E$，初始化 $n_{e}(i)=0, n_{e}(j)=0$，然后枚举所有顶点 $v\in V$，若 $d(i, v) < d(j, v)$，则 $n_{e}(i)$ 加 1，若 $d(i, v) < d(j, v)$，则 $n_{e}(j)$ 加 1。枚举完所有的 $v$ 后，将结果进行累加。

1
2
3
4
5
6
7
8
9
10
ans = 0
for i, j in edges:
    ne_i = ne_j = 0
    for v in range(1, 13):
        if d[i][v] < d[j][v]:
            ne_i += 1
        elif d[i][v] > d[j][v]:
            ne_j += 1
    ans += ne_i * ne_j
print("Szeged 指数: {}".format(ans))

最终结果为 466。

维纳指数的数学性质

下面这篇文章《Mathematical aspects of Wiener index》从数学视角讨论了维纳指数，可以参考：

本文主要探讨了图论中的维纳指数（Wiener index），这是一个在化学分子结构研究中非常重要的分子描述符。维纳指数定义为图中所有顶点对之间距离的总和。以下是文章的主要内容要点：

  1. 维纳指数的定义和应用：维纳指数最初用于预测烷烃的沸点，后来发现与化合物的化学性质有强相关性，现在用于药物分子的初步筛选和蛋白质-配体复合物的结合能量预测。
  2. 维纳指数的数学性质：文章总结了一些关于维纳指数的数学结果、猜想和问题，特别强调了作者参与的工作。
  3. 维纳指数的计算：对于树这类特殊的图，维纳指数可以通过边缘贡献进行分解计算。
  4. 逆维纳指数问题：探讨了对于给定整数 w，是否存在具有维纳指数 w 的树的问题。
  5. 具有规定最小/最大度数的图：研究了在具有特定度数限制的图中维纳指数的极值问题。
  6. 具有规定直径/半径的图：探讨了在具有特定直径或半径限制的图中维纳指数的最大值问题。
  7. 维纳指数的同余关系：研究了维纳指数与图的结构之间的关系，特别是同余关系。
  8. 线图操作与维纳指数：研究了图的线图（由原图的边构成的图，其中两条边相邻当且仅当原图中它们相邻）的维纳指数与原图维纳指数的关系。
  9. 维纳指数的进一步问题：提出了一些关于维纳指数的未解决问题，包括在特定类型的图（如有向图、具有奇数度数顶点的图）中维纳指数的性质。
  10. 维纳指数的计算方法：讨论了计算维纳指数的算法和效率问题。

文章中还提到了一些特定的图结构，如星形图、树、圈等，并探讨了这些结构的维纳指数特性。此外，文章还涉及了维纳指数在化学图理论中的应用，以及如何通过图论工具来理解和预测分子的化学性质。

Share