图的同构

结点的位置不同，边的长短不同，不会影响这个图所代表的关系

设两个图，如果存在一个 双射 函数使得两个图一一对应，对于任意图中的边，点经过映射后产生的新边所连的结点度数一样，边 重数 相同，则这两个图同构

有以下不变量：

• 结点数
• 边数
• 度数相同的节点数
• ……

最小矩阵算法

---

含有 5 个结点，3 条边的不同构的 简单图 有多少个？

1. 一共有 6 度，排出来 度数序列
2. 按顺序（从大到小）考虑可行性
   • 不能自环，不能重边
   • 可以分离
3. 根据序列画出尽可能多的不同构的图
   • 这里是唯一的
4. 一共画出来四种