效用图

效用问题提出三个房子和三个公用事业公司——例如，煤气、电力和水——并询问是否可以将每个公用事业公司连接到每个房子，而煤气/水/电线/管道不会跨越任何其他线路/管道。这等同于问题“是否可以从三个节点（‘房子’）中的每一个到另三个节点（‘公用事业公司’）中的每一个构建一个平面图？”这个问题最初由 H. E. Dudeney 于 1917 年以这种形式提出 (Gardner 1984, p. 92)。

答案是不存在这样的平面图，并且可以使用约旦曲线定理来证明，而包含这一结果的更一般的结果是库拉托夫斯基归约定理。效用图是显示上述关系的图，也称为汤姆森图（例如，Coxeter 1950），并且在更正式的图论术语中，被称为完全二分图 （并且也等同于循环图 ）。

它在 Wolfram 语言中实现为GraphData["UtilityGraph"].

效用图的图交叉数为 1，最小交叉嵌入如上图最右侧的图形所示。

效用图的非平面性的一个简单证明可以通过注意到该图由一个图环 组成，必须向其添加三条边 、 和 。现在，对于每条边，我们必须选择是将边绘制在图环内部还是外部，因此对于两条边，我们必须做出相同的选择。但是两条线不能在同一侧绘制而不交叉，因此该图不是平面的。

它可以使用 LCF 符号表示为 。效用图是一个积分图，其图谱为 。

上面的图显示了效用图的邻接矩阵、关联矩阵和图距离矩阵。

删除效用图的一条边会得到四面体图。

效用图的图亏格为 ，因此它可以无交叉地绘制在环面上，如上图所示 (M. Malak, 私人通讯，2006 年 2 月 15 日)。