图论碎碎念（2.2）

本文作者：云屿

狗子们开学（上班）快乐！有没有期待这一期的图论碎碎念呢？在本期开始之前，首先我们用数学语言把2.1的内容总结一下。

上节提到：图至少由节点和边组成

G={v_1,v_2,…和e_1,e_2,… }

简记为G=（V(G),E(G)）;也就是:

V={v_1,v_2,…,v_n}; E={e_1,e_2,…,e_n}

那如何比较两个图是否一样呢？这个问题咱们还来举个栗子：比如说喝铁观音，稍微讲究一点的人就会去洗。洗茶过后比起没洗过，第一泡和第二泡的味道都有不同。喝毛尖的也知道，好的毛尖形如扁鸭嘴，色如绿豆汤。第一泡的时候明显不可能这样。

所以区别在哪呢？这也就可以看成是茶和水之间的关系不一样，可能是他们的紧密程度不同，或者耦合性不同。还有现在像一些人工智能（AI）领域里面的一些研究比较深的，会涉及到元认知（Meta Cognition）的问题，即怎么才能教计算机像人一样学习思考。从人的角度，元认知就可以说对如何建立联系的认知。怎样把你要学的东西和你已经有的东西联系在一起。比如说同样是讨论，但是不同学科背景的人，看到图论之后，想到的东西就不一样。

（以下都是Specific了的联系）

如果是计算机的可能就会想到网络拓扑图，如果要是地学一些同学，他可能就会想到简易的一些反演图，那学美术的，那他可能会想的就是构图。这些都是一些已经具体化的联系。联系可以有很多种，判断图是否同构就是要判断图的节点是否一样，每个节点之间的联系是否一样。那有的狗子就说了：一个一个对比太麻烦了，你要数节点数，还要一个一个看边，如果要是有n个点又是有向图的话，那他们两两节点之间的关系数就是

所以当当当！是时候展示真正的技术了！这就是之前我们为什么要先介绍矩阵：通过关系矩阵我们就可以判断两个图是否同构。首先推荐一款简单的软件:Ucinet,只要有关系矩阵，Ucinet 就可以画出关系图来（虽然贼丑）其次，以邻接矩阵为例，介绍判断图是否同构的两种想法：

（A）如果两个图同构，则一定可以通过对其中一个图的有限次 拉扯移动中得到另外一个图。从矩阵角度来说，就是：

1 ）两个矩阵尺寸相同（意味着节点相同）

2）假定两个矩阵为同一个图上的两种关系（则问题转化为，比较相同数量的节点之间的两种关系是否相同？）

3）问题转化为，两个矩阵是否可以通过有限次线性变换得到？

如果明白了，那再换一种想法：

（B）

1）两个图

2）两个图节点相同（则问题转化为两个关系是否相同）

3）两个关系是否相同的判断转化为两个矩阵的判断。

之前看到过一种算法，即抓住两图中对应点的关系来一次次改换点的编号。这听起来有点像好玩的拼图游戏，不过考虑到复杂度的问题，不建议使用这种算法。简言之，将复杂问题抽象成矩阵一顿操作才是MATLAB的风格。

这里我们用MATLAB和PYTHON的networkx包来演示对图同构的判断。同时，Networkx建议和Matplotlib配合使用不需要二狗解释了吧。好了，狗子们！是时候拿出你们的青轴茶轴黑轴一起敲上些代码了！

首先Python画出上节2.1中无向点粽子图。不要怂，很（就）简（是）单（干），掏出我的PyCharm就是一顿操作：

# code UTF-8
# 图论基础（2.2）
# Author: PinkScorpian
import networkx as nx  # 给networkx起个小名,nx
import matplotlib.pyplot as plt  # 给matplotlib包里的pyplot起个小名,plt

def main():
  G=nx.Graph() # 建立一个图论容器

  G.add_node('li') # 这一块添加节点
  G.add_node('zh')
  G.add_node('wang')

  G.add_edge('li', 'zh')  # 添加边
  G.add_edge('zh', 'wang')

  nx.draw(G,with_labels=True,arrows=True)  # 画图设置
  plt.show()  # 显示在画布上
  print('ok')  # 调试用，不会用debugger的狗子试一试


if __name__ == "__main__":  # python 国际惯例写法
  main()

其次，我们用MATLAB来试着构建一个判别两个邻接矩阵是否成线性关系的函数。此函数输入的是两个邻接矩阵，输出结果为两个矩阵是否经过行变换得到对方。（怎么有种恋爱的酸臭味？？）使用这个函数的前提是：同构的图具有的顶点数、（顶点度、节点数、回路数会在章小节里总结）相同。

% 仅从行变换角度作邻接矩阵判断
function E=judge_m(A,B)
[m,n]=size(A);
t=1:n;
D=perms(t);
[a1, a]=size(D);

for i=1:a1
    C=eye(n);
    E=C(:,D(i,:));
    if E*A==B % 在这个循环中，找到A,B的线性行变换矩阵E使E*A=B
        disp('find the linear transformation matrix in row');
        break; % 找到就跳出循环，找不到就是最后一个
    end
end

P=E*A-B;  % 若找到，则后续循环中E不会重置

for i =1:n
    for t=1:n
        if P(i,t)~=0
            E=zeros(n); % 若没找到，则为最后一行E 不能使 E*A=B，则E会被重置为零
            break;
        end
    end
end

例子很简单，大家一起来合奏吧~~图的同构作为一个NP问题，在算力方面也是个老大难。听说用Hadoop+Spark可以进行更大型子图的同构判断？有兴趣的狗子可以尝试一下。

本系列推文脉络参考《详解Matlab在最优化计算中的应用》；matlab代码参考https://wenku.baidu.com/view/bb04a627af45b307e8719776.html