分数图同构

在图论中，其邻接矩阵表示为A和B的图的分数同构是一个双随机矩阵D，使DA=BD。如果双随机矩阵是一个置换矩阵，那么它就构成了一个图的同构。

虽然图的同构问题不知道在多项式时间内可解，也不知道是NP-完全的，但分数图同构问题在多项式时间内是可解的，因为它是线性规划问题的一个特例，对它有一个有效的解决方案。

如果两个图有一个共同的最粗的公平分区，它们也是分数同构的。图的分区是一个成对不相交的顶点集的集合，其联盟是图的顶点集。如果对于分区中同一区块的任何一对顶点u和v以及分区中的任何区块B，u和v在B中都有相同数量的邻居，则该分区是公平的。

如果存在一个从P的区块到Q的区块的双投射f，那么两个最粗的公平分区P和Q是共同的，对于P中的任何区块B和C，B中任何顶点在C中的邻居数等于f(B)中任何顶点在f(C)中的邻居数。