图论研究的东西是点和线。点代表事物。线代表关系。地铁线路是一个图。每个车站是点。铁轨是线。社交网络是一个图。每个人是点。朋友关系是线。互联网是一个图。每台电脑是点。网线是线。图论研究这些点和线怎么连在一起。图论研究它们有什么共同特点。

研究生论文题目要小。题目要具体。不能太大。太大写不完。题目要有新东西。不能重复别人。找题目要看别人做了什么。看看还有什么没做。一个问题可能有很多角度。找一个自己能做的角度。数学基础要好。想法要清楚。

一个题目是社区发现。大网络里有很多小团体。一个小团体内部联系紧密。团体之间联系少。怎么找到这些小团体。算法要快。网络很大。几百万个点。几亿条线。慢的算法不好用。一个办法是看密度。一个团体里线很多。另一个办法是看信息流动。信息在小团体里传得快。出小团体传得慢。还可以用随机游走。一个人在网络里随机走。他容易在小团体里转圈。不容易走出去。这些方法都能用。要比较哪种方法好。好就是准而且快。

另一个题目是网络传播。消息怎么传开。病毒怎么感染。一个点感染了。它可能感染邻居。邻居又感染邻居。最后整个网络都感染了。研究什么东西影响传播。网络结构很重要。有些点很重要。它们是中心。它们连接很多点。它们感染了传播就快。可以研究怎么堵住传播。保护哪些点最有用。保护中心点有用。但中心点可能不好找。可以研究怎么找这些点。也可以研究传播阈值。一个病毒要有多厉害才能传开。网络密到一定程度病毒才能传开。这个程度叫阈值。计算阈值是个问题。还可以研究免疫策略。给一部分点打疫苗。打哪些点最有效。随机打可能效果不好。打邻居多的点效果好。打经常在路上走的点也有效。

还有一个题目是图着色。给地图上色。相邻国家颜色不同。最少用几种颜色。四种颜色一定够。这是四色定理。但实际用起来要算法。算法要快。国家很多时也要快。着色问题不只用在地图。排课表也是着色。一节课是一个点。两节课时间冲突就画一条线。一种颜色是一个时间。着色成功课表就排好。考试安排也是着色。还可以用在无线电网。相邻频道要用不同频率。着色问题有很多变种。点有权重。颜色有代价。目标是最小化总代价。这个问题难。要找好算法。

路径规划也是好题目。找最短路径。两个点之间怎么走最快。地图导航就用这个。但有时要考虑更多。路会堵车。堵车时时间变长。动态路径规划考虑这个。系统随时知道路况。随时调整路径。有时不只找一个最短路径。要找所有点两两之间的最短路径。这个计算量大。要想办法节省计算。有时路径有约束。不能走某些路。比如货车不能走小路。比如电动车要找充电站。问题就变复杂。算法要适应这些约束。

图匹配是另一个方向。比较两个图像不像。化学分子结构是图。原子是点。化学键是线。判断两个分子是不是一样就用图匹配。社交网络也可以比。看两个公司内部结构像不像。图匹配要算相似度。点要对得上。线也要对得上。完全一样很难。大部分时候是部分一样。要算匹配了多少。这个问题也难。大图匹配更慢。需要巧妙算法。

网络演化值得研究。网络不是固定的。网络在长大。新点加进来。新线加进来。旧线可能消失。研究网络怎么长大。一些网络长得快。一些网络长得慢。网络结构怎么变。开始可能随机连接。后来形成中心点。中心点吸引更多连接。这叫富人更富。研究演化模型。模拟网络生长。和真实网络对比。看模型好不好。还可以预测网络未来。预测哪里会长出新连接。预测哪些点会变重要。这对商业有用。可以提前投资重要点。

图神经网络现在很热。深度学习用在图上。传统深度学习处理图片和文字。图片是格子。文字是序列。图是不规则结构。图神经网络学习点的特征。考虑邻居的特征。一层一层传递信息。最后每个点都有新特征。这些特征可以分类点。可以分类整个图。可以预测缺失的线。比如社交网络里预测谁会成为朋友。图神经网络效果好。但需要很多计算。需要很多数据。解释性也不好。不知道它为什么学得好。改进图神经网络是个方向。让它更快。让它需要数据更少。让它更明白。

论文题目要能做实验。要有数据。社交网络数据很多。互联网数据很多。交通数据也很多。没有数据就做仿真。生成人工网络。在人工网络上测试算法。和真实数据对比。实验要设计好。要证明算法有用。要证明算法比别人好。好就是快或者准。要列出数字。画图说明。图要清楚。表要明白。

数学证明很重要。有些问题需要证明。证明算法一定对。证明算法最快用到什么程度。证明边界值。证明定理。证明要严谨。一步一步推理。不能有跳步。要检查有没有漏洞。证明难想。但证明出来就很有力。

写论文要清楚。问题是什么。方法是什么。结果是什么。贡献是什么。贡献要写明白。我的方法新在哪里。我解决了什么困难。我的工作别人怎么用。语言要简单。不要用难懂的词。图论有很多术语。术语要解释。让不是这个专业的人也能看懂大意。公式要必要才用。不能太多公式。太多公式难读。

研究生做图论要耐心。问题可能很难。要想很久。可能失败很多次。要想新办法。要读很多文章。要知道别人在做什么。要和人讨论。讨论能出想法。要动手实现算法。写代码调试。看到结果会高兴。论文写完就轻松了。但研究没有结束。总是有新问题。图论和生活联系紧。生活里有各种网络。研究图论就是研究世界怎么连接。这个研究有用。能帮我们设计更好网络。能帮我们理解复杂系统。能帮我们解决问题。