文件名称：Tutte定理-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:28
集训队论文集
2.1 Tutte定理 定义 2.1 (Tutte矩阵). 对于一个无向图 G = (V, E),定义 G 的 Tutte矩阵为一个 n × n的矩阵 Ã(G),其中 Ã(G)i, j = xi, j 若 viv j ∈ E并且 i < j −x j,i 若 viv j ∈ E并且 i > j 0 其它情况 其中，xi, j 是一个与边 viv j 相关联的独一无二的变量。 下面我们来看一个例子。 v1 v2 v3v4 x1,2 x2,3 x3,4 x1,4 x1,3 0 x1,2 x1,3 x1,4 −x1,2 0 x2,3 0 −x1,3 −x2,3 0 x3,4 −x1,4 0 −x3,4 0 图 1: 图 G与它的 Tutte矩阵 图 1的左半部分给出了一个图 G，右半部分给出了图 G 所对应的 Tutte矩阵 Ã(G)。可 以看到，图 G的每条边都对应着一个变量，因此 Ã(G)中总共会用到 |E|个变量。 4学术界一般认为 2 ≤ ω < 2.373。 14