数域K上的l维向量空间V中余维数为1的仿射子空间称为超平面，超平面的有限集即为超平面构形，记作A={H1, H2, …, Hn}，简称构形[1]。若
Falk等[2]对由Tutte多项式决定的图和拟阵进行了研究；初丽丽等[3]和李爱民等[4]研究了一些特殊图构形的Tutte多项式，Amanda等[5]计算出圈、重边、完全图、扇形图及曲轮图的Tutte多项式；Duan等[6]证明了曲轮图和双半轮图的Tutte多项式的唯一性。以上文献主要研究普通图的Tutte多项式的计算，但关于带号图构形的Tutte多项式方面还未见报道。因此本文对带号曲轮和带号双半轮的Tutte多项式进行研究，找到了几种有规律的基本图形(基图)，得出这些基本图形的Tutte多项式的递推公式后，再利用计算机辅助给出这类带号图的Tutte多项式，进而得到特征多项式，最后得到了这类带号图构形的OS代数维数。
1 带号图构形及其Tutte多项式定义1 设x1, x2, …, xl是数域K上l维向量空间V的对偶空间V*的基，给定普通图Γ=(V, E)，则对任一边{i, j}∈E，都在V中对应一个以xi-xj为定义多项式的超平面，继而有一个构形A(Γ)={ker (xi-xj)|{i, j}∈ε}与之对应，此构形A(Γ)就称为图构形。
定义2 设Σ=(Γ, σ)=(V, E, σ)是一个有限简单带号图，其中Γ是一个普通图，σ是符号函数，E是图Γ的边集。将E中每个元素σ:e→{+, -}中带正号的边用实线表示，带负号的边用虚线表示。那么Σ中的任一边eij在向量空间V中对应一个以xi-σ(eij)xj为定义多项式的超平面，由此有一个带号图构形A(Σ)={ker(xi-σ(eij)xj)|eij∈ε}与之对应。
定义3 对于带号图Σ，存在一个符号转换函数ζ:ν→{+, -}，使得转换后边e的符号为σζ(e)=ζ(ν)σ(e)ζ(w)，其中v和w为边e的端点。设转换后的带号图为Σζ=(|Σ|, σζ)，那么称用ζ转换Σ，注意且有Σζ=Σ-ζ。
定义4[7] 超平面构形A的Tutte多项式为
定义5 图Γ=(V, E)的Tutte多项式为
| $ {T_\mathit{\Gamma }}\left( {x,y} \right) = \sum\limits_{A \subseteq E} {{{\left( {x - 1} \right)}^{r\left( E \right) - r\left( A \right)}}{{\left( {y - 1} \right)}^{\left| A \right| - r\left( A \right)}}} $ |
定义6 带号图Σ=(V, E, σ)的Tutte多项式为TΣ(x, y, z)=
特别地，有(x-1)-u(E)TΣ(x, y, (x-1)(y-1))=TΓ(x, y)。
因为图构形AΣ的拟阵是图Σ的圈拟阵[2]，所以带号图Σ的Tutte多项式等价于其对应带号图构形AΣ的Tutte多项式。
对于带号图Σ的Tutte多项式TΣ(x, y, z)，令x=1-t、y=0、z=0，可得其着色多项式χ(Σ, t)，即χ(Σ, t)=(-1)r(E)tk(Σ)TΣ(1-t, 0, 0)。而图的着色多项式等价于其所对应图构形的特征多项式[1]，即χ(Σ, t)=χ(A, t)。
本文主要运用如下定理和性质来计算一类图构形的Tutte多项式。
性质1
(1)(删除-收缩)若e不是环，也不是桥，则
| $ {T_\mathit{\Sigma }}\left( {x,y,z} \right) = {T_{\mathit{\Sigma \backslash e}}}\left( {x,y,z} \right) + {T_{\mathit{\Sigma /e}}}\left( {x,y,z} \right); $ |
(2) 若e是一个桥，则TΣ(x, y, z)=xTΣ\e(x, y, z)；
(3) 若e是一个正环，则TΣ(x, y, z)=yTΣ/e(x, y, z)；
(4) 若e是一个负环，则TΣ(x, y, z)=TΣ/e(x, y, z)。
性质2 给定2个图G和H，G∪H表示2个图的并，G*H表示2个图的1点连，则有T(G∪H)=T(G)T(H)，T(G*H)=T(G)T(H)。
2 一类带号图的定义本文研究的带号曲轮图和带号双半轮图的定义如图 1所示。
|
图 1 带号曲轮图Wk1, k2和带号双半轮图W′k1, k2 Fig.1 Signed twisted wheels and signed double half-wheels |
定理1 当k2≥k1≥3时，带号曲轮图Wk1, k2的Tutte多项式基图为Vk1, k2、Mk1, k2、Nk1, k2、N0, k2和M0, k2(图 2)，且带号图对应图构形的Tutte多项式为
|
图 2 Wk1, k2的基图 Fig.2 Basic graphs of Wk1, k2 |
| $ \begin{array}{l} T\left( {{W_{{k_1},{k_2}}}} \right) = (x + 1)\sum\limits_{i = 0}^{{k_1} - 2} T \left( {{V_{i,{k_2}}}} \right) + y\sum\limits_{i = 0}^{{k_1} - 3} T \\ \left( {{V_{i,{k_2}}}} \right) + {y^2}\sum\limits_{i = 0}^{{k_1} - 4} T \left( {{V_{i,{k_2}}}} \right) + {y^3}\sum\limits_{i = 0}^{{k_1} - 5} T \left( {{V_{i,{k_2}}}} \right) + \cdots + \\ {y^{{k_1} - 3}}\left[ {T\left( {{V_{0,{k_2}}}} \right) + T\left( {{V_{1,{k_2}}}} \right)} \right] + {y^{{k_1} - 2}}T\left( {{V_{0,{k_2}}}} \right) + \\ yx\sum\limits_{i = 0}^{{k_1} - 4} T \left( {{M_{i,{k_2}}}} \right) + y{x^2}\sum\limits_{i = 0}^{{k_1} - 5} T \left( {{M_{i,{k_2}}}} \right) + \cdots + y{x^{{k_1} - 4}}[T\\ \left. {\left( {{M_{0,{k_2}}}} \right) + T\left( {{M_{1,{k_2}}}} \right)} \right] + y{x^{{k_1} - 3}}T\left( {{M_{0,{k_2}}}} \right) + (y + \\ {y^2})\sum\limits_{i = 0}^{{k_1} - 3} T \left( {{M_{i,{k_2}}}} \right) + \left( {y + yx + y{x^2} + y{x^3} + \cdots + y{x^{{k_1} - 2}}} \right)\\ T\left( {{N_{0,{k_2}}}} \right) + T\left( {{W_{1,{k_2}}}} \right) \end{array} $ | (1) |
图 2(a)为带号曲轮图关于某条边缘上边的删除，记为Vk1, k2，其中k1、k2分别表示右侧、左侧的三角形个数；图 2(b)N0, k2是(k2+1)-秩轮图边缘上有一条负边的图；B′k2+2是(k2+2)-秩轮图Ak2+2关于某条边缘上边的删除，图 2(c)是B′k2+2的边缘上有一条负边的图；Mk1, k2、Nk1, k2(图 2(d)、(e))的带边为负边。
Vk1, k2的基图为V0, k2、V1, k2(图 3)，两个基图都有k2+1个三角形，且都为正边，因此它们的Tutte多项式可用普通图的删除-限制算法[2]来计算。
|
图 3 Vk1, k2的基图 Fig.3 Basic graphs of Vk1, k2 |
以下5个引理给出了计算定理1中几个基图的Tutte多项式的递推公式。
引理1 当k1=0时，初始图V0, k2的Tutte多项式为
| $ \begin{array}{l} T\left( {{V_{0,{k_2}}}} \right) = xT\left( {{B_{{k_2}}}} \right) + xyT\left( {{B_{{k_2} - 1}}} \right) + x{y^2}T\left( {{B_{{k_2} - 2}}} \right) + \\ \cdots + x{y^{{k_2} - 1}}T\left( {{B_1}} \right) + x{y^{{k_2}}}(x + y) + T\left( {B_{{k_2} + 2}^\prime } \right) \end{array} $ |
当k1=1时，初始图V1, k2的Tutte多项式为
| $ T\left(V_{1, k_{2}}\right)=x^{2} T\left(B_{k_{2}}\right)+x T\left(A_{k_{2}+1}\right)+T\left(V_{0, k_{2}}\right) $ |
当k2≥k1≥3时，基图Vk1, k2的Tutte多项式为
| $ \begin{array}{c}{T\left(V_{k_{1}, k_{2}}\right)=(x+1) T\left(V_{k_{1}-1, k_{2}}\right)+y T\left(V_{k_{1}-2, k_{2}}\right)+} \\ {y^{2} T\left(V_{k_{1}-3, k_{2}}\right)+\cdots+y^{k_{1}-2} T\left(V_{1, k_{2}}\right)+y^{k_{1}-1} T\left(V_{0, k_{2}}\right)}\end{array} $ | (2) |
N0, k2的基图Pk2中含有k2+2条负边，且每个三角形都有2条负边和1条正边(除重边)，如图 4所示。
|
图 4 N0, k2的基图Pk2 Fig.4 Basic graphs of N0, k2 |
引理2 当k1=0时，N0, k2的基图为Pk2，且有
| $ T\left( {{P_{{k_2}}}} \right) = T\left( {{B_{{k_2}}}} \right) + yT\left( {{B_{{k_2} - 1}}} \right) + \cdots + {y^{{k_2} - 1}}T\left( {{B_1}} \right) + T\left( {{P_{{k_2} - }}1} \right) $ |
因N0, k2的初始图N0, 2含有1条负边，通过计算可得N0, 2的Tutte多项式分别为
| $ T\left(N_{0,2}\right)=x^{3}+2 x^{2}+2 x y+x+2 y+y^{2}+z^{2}+3 z+3 $ |
当k2≥3时，N0, k2的Tutte多项式为
| $ T\left(N_{0, k_{2}}\right)=T\left(B_{k_{2}}\right)+T\left(P_{k_{2}-2}\right)+T\left(N_{0, k_{2}-1}\right) $ | (3) |
引理3 当k2≥3时，M0, k2的Tutte多项式为
| $ T\left(M_{0, k_{2}}\right)=y T\left(P_{k_{2}-1}\right)+T\left(N_{0, k_{2}}\right) $ | (4) |
引理4 当k2≥k1≥3时，Nk1-1, k2的Tutte多项式为
| $ \begin{array}{l} T\left( {{N_{{k_1} - 1,{k_2}}}} \right) = {x^{{k_1} - 1}}T\left( {{N_{0,{k_2}}}} \right) + {x^{{k_1} - 2}}T\left( {{M_{0,{k_2}}}} \right) + \\ {x^{{k_1} - 3}}T\left( {{M_{1,{k_2}}}} \right) + \cdots + xT\left( {{M_{{k_1} - 3,{k_2}}}} \right) + T\left( {{M_{{k_1} - 2,{k_2}}}} \right) \end{array} $ | (5) |
引理5 当k2≥k1≥3时，Mk1-1, k2的Tutte多项式为
| $ \begin{array}{l} T\left( {{M_{{k_1} - 1,{k_2}}}} \right) = {x^{{k_1} - 1}}T\left( {{N_{0,{k_2}}}} \right) + {x^{{k_1} - 2}}T\left( {{M_{0,{k_2}}}} \right) + \\ {x^{{k_1} - 3}}T\left( {{M_{1,{k_2}}}} \right) + \cdots + xT\left( {{M_{{k_1} - 3,{k_2}}}} \right) + T\left( {{M_{{k_1} - 2,{k_2}}}} \right) + yT\\ \left( {{M_{{k_1} - 2,{k_2}}}} \right) \end{array} $ | (6) |
将公式(1)~(6)联立，计算得出当k1=3，k2=3、4时带号图Wk1, k2的Tutte多项式分别为
| $ \begin{array}{l} T\left( {{W_{3,3}}} \right) = {x^7} + 7{x^6} + 7{x^5}y + 22{x^5} + 6{x^4}{y^2} + 34{x^4}y + \\ \begin{array}{*{20}{l}} {41{x^4} + 5{x^3}{y^3} + 34{x^3}{y^2} + 73{x^3}y + 49{x^3} + 4{x^2}{y^4} + }\\ {25{x^2}{y^3} + 70{x^2}{y^2} + 86{x^2}y + {x^2}{z^2} + 3{x^2}z + 39{x^2} + x{y^5} + } \end{array}\\ \begin{array}{*{20}{l}} {11x{y^4} + 41x{y^3} + 68x{y^2} + xy{z^2} + 3xyz + 57xy + 3x{z^2} + 9xz + }\\ {21x + 3{y^5} + 13{y^4} + 27{y^3} + {y^2}{z^2} + 3{y^2}z + 33{y^2} + 3y{z^2} + } \end{array}\\ 9yz + 24y + 3{z^2} + 9z + 9 \end{array} $ |
| $ \begin{array}{l} T\left( {{W_{3,4}}} \right) = {x^8} + 8{x^7} + 8{x^6}y + 29{x^6} + 7{x^5}{y^2} + 47{x^5}y + \\ 64{x^5} + 6{x^4}{y^3} + 51{x^4}{y^2} + 125{x^4}y + 97{x^4} + 5{x^3}{y^4} + \\ \begin{array}{*{20}{l}} {46{x^3}{y^3} + 142{x^3}{y^2} + 198{x^3}y + 103{x^3} + 4{x^2}{y^5} + 32{x^2}{y^4} + }\\ {115{x^2}{y^3} + 209{x^2}{y^2} + 196{x^2}y + {x^2}{z^2} + 3{x^2}z + 73{x^2} + x{y^6} + } \end{array}\\ \begin{array}{*{20}{l}} {14x{y^5} + 62x{y^4} + 133x{y^3} + 166x{y^2} + xy{z^2} + 3xyz + }\\ {111xy + 3x{z^2} + 9xz + 31x + 4{y^6} + 19{y^5} + 46{y^4} + 68{y^3} + } \end{array}\\ {y^2}{z^2} + 3{y^2}z + 63{y^2} + 3y{z^2} + 9yz + 34y + 3{z^2} + 9z + 9 \end{array} $ |
结果发现含z的项和常数项的系数固定。
由χ(A(Σ), t)=χ(Σ, t)=(-1)r(E)tk(Σ)TΣ(1-t, 0, 0)，得到当k1=3，k2=3、4时Wk1, k2对应图构形的特征多项式分别为
| $ \begin{array}{l} \chi \left( {{W_{3,3}},t} \right) = {t^8} - 14{t^7} + 85{t^6} - 291{t^5} + 608{t^4} - \\ 778{t^3} + 569{t^2} - 189t \end{array} $ |
| $ \begin{array}{l} \chi \left( {{W_{3,4}},t} \right) = {t^9} - 16{t^8} + 113{t^7} - 462{t^6} + 1202{t^5} - \\ 2047{t^4} + 2235{t^3} - 1432{t^2} + 415t \end{array} $ |
进而，因超平面构形OS代数的i(i=1, 2, …)次子代数的维数等于特征多项式系数的绝对值[1]，由此可知曲轮图构形OS代数的i(i=1, 2, …, 9)次子代数维数如表 1所示。
|
下载CSV 表 1 k1=3，k2=3、4时Wk1, k2对应图构形的OS代数维数 Table 1 Dimensions of the OS algebra of graphic arrangements Wk1, k2 for k1=3, k2=3、4 |
定理2 当k2≥k1≥3时，设带号双半轮图W′k1, k2的Tutte多项式基图为Kk1, k2、V′k1, k2、Hk1-2, k2、Uk1-1, k2和V″2, k2，且带号双半轮图对应图构形的Tutte多项式为
| $ \begin{array}{l} T\left( {W_{{k_1},{k_2}}^\prime } \right) = (x + 1)T\left( {V_{{k_1} - 1,{k_2}}^\prime } \right) + yT\left( {V_{{k_1} - 2,{k_2}}^\prime } \right) + \\ {y^2}T\left( {V_{{k_1} - 3,{k_2}}^\prime } \right) + \cdots + {y^{{k_1} - 3}}T\left( {V_{2,{k_2}}^\prime } \right) + {y^{{k_1} - 2}}T\left( {V_{2,{k_2}}^\prime /e} \right) + \\ \begin{array}{*{20}{l}} {y\left[ {T\left( {{H_{1,{k_2}}}} \right) + T\left( {{H_{2,{k_2}}}} \right) + \cdots + T\left( {{H_{{k_1} - 2,{k_2}}}} \right)} \right] + [T}\\ {\left( {{U_{2,{k_2}}}} \right) + T\left( {{U_{3,{k_2}}}} \right) + \cdots + T\left( {{U_{{k_1} - 1,{k_2}}}} \right)] + T\left( {V_{2,{k_2}}^{\prime \prime }} \right)} \end{array} \end{array} $ | (7) |
带号双半轮图W′k1, k2的Tutte多项式基图如图 5所示。带号双半轮图关于带边的删除记为Kk1, k2，它有k1+k2个三角形；Hk1-2, k2含有2条负边；Uk1-1, k2是(k2+2)-秩轮图Ak2+2的导出图；V″2, k2是(k2+2)-秩轮图Ak2+2上加了1条负边；V′k1, k2是带有k1+k2个三角形的简单图。
|
图 5 W′k1, k2的基图 Fig.5 Basic graphs of W′k1, k2 |
V′k1, k2的基图如图 6所示。V′1, k2、V′2, k2均是带有正边的图，因此它们的Tutte多项式可用普通图的删除-限制算法来计算。Kk1, k2的基图K2, k2/e是带有1条负边的图(图 7)。
|
图 6 V′k1, k2的基图 Fig.6 Basic graphs of V′k1, k2 |
|
图 7 Kk1, k2的基图 Fig.7 Basic graphs of Kk1, k2 |
以下4个引理主要给出了计算定理2中几个基图Tutte多项式的递推公式。
引理6 当k1=1时，初始图V′1, k2的Tutte多项式为
| $ \begin{aligned} & T\left(V_{1, k_{2}}^{\prime}\right)=T\left(B_{k_{2}+1}\right)+y T\left(B_{k_{2}}\right)+y^{2} T\left(B_{k_{2}-1}\right)+\\ \cdots+y^{k_{2}} T\left(B_{1}\right) &+y^{k_{2}+1}(x+y) \end{aligned} $ |
当k1=2时，初始图V′2, k2的Tutte多项式为
| $ T\left(V_{2, k_{2}}^{\prime}\right)=x T\left(B_{k_{2}+1}\right)+T\left(V_{1, k_{2}}^{\prime}\right) $ |
当k2≥k1≥3时，基图V′k1, k2的Tutte多项式为
| $ \begin{array}{c}{T\left(V_{k_{1}, k_{2}}^{\prime}\right)=(x+1) T\left(V_{k_{1}-1, k_{2}}^{\prime}\right)+y T\left(V_{k_{1}-2, k_{2}}^{\prime}\right)+} \\ {y^{2} T\left(V_{k_{1}-3, k_{2}}^{\prime}\right)+\cdots+y^{k_{1}-3} T\left(V_{2, k_{2}}^{\prime}\right)+y^{k_{1}-2} T\left(V_{1, k_{2}}^{\prime}\right)}\end{array} $ | (8) |
当k1=2时，初始图K2, k2/e的Tutte多项式为
| $ \begin{array}{l} T\left( {{K_{2,{k_2}}}/e} \right) = T\left( {{B_{{k_2} + 1}}} \right) + yT\left( {{B_{{k_2}}}} \right) + {y^2}T\left( {{B_{{k_2} - 1}}} \right) + \\ \cdots + {y^{{k_2}}}T\left( {{B_1}} \right) + {y^{{k_2} + 1}}(z + 1) \end{array} $ |
当k2≥k1≥3时，带号图Kk1, k2的Tutte多项式为
| $ \begin{array}{c}{T\left(K_{k_{1}, k_{2}}\right)=(x+1) T\left(V_{k_{1}-1, k_{2}}^{\prime}\right)+T\left(V_{k_{1}-2, k_{2}}^{\prime}\right)+} \\ {T\left(V_{k_{1}-3, k_{2}}^{\prime}\right)+\cdots+T\left(V_{3, k_{2}}^{\prime}\right)+T\left(V_{1, k_{2}}^{\prime}\right)+T\left(K_{2, k_{2}} / e\right)}\end{array} $ | (9) |
Hk1-2, k2的基图如图 8所示，H1, k2含有两条负边、k2+1个三角形。首先将图H1, k2右边的重边e进行删除-收缩，在后期计算过程中需要将其中的负边符号转换为正边之后，再进行普通图的删除-收缩操作。
|
图 8 Hk1-2, k2的基图 Fig.8 Basic graphs of Hk1-2, k2 |
引理7 当k1=3时，图Hk1-2, k2的Tutte多项式的基图为H1, k2，且
| $ \begin{array}{l} T\left( {{H_{1,{k_2}}}} \right) = T\left( {{A_{{k_2} + 1}}} \right) + yT\left( {{A_{{k_2}}}} \right) + T\left( {{P_{{k_2} - 1}}} \right) + \\ 2yT\left( {{P_{{k_2} - 2}}} \right) \end{array} $ |
当k2≥k1≥3时，基图Hk1-2, k2的Tutte多项式为
| $ \begin{array}{l} T\left( {{H_{{k_1} - 2,{k_2}}}} \right) = {x^{{k_1} - 3}}T\left( {B_{{k_2} + 2}^\prime } \right) + {x^{{k_1} - 4}}T\left( {{H_{1,{k_2}}}} \right) + \\ {x^{{k_1} - 5}}T\left( {{H_{2,{k_2}}}} \right) + \cdots + {x^2}T\left( {{H_{{k_1} - 5,{k_2}}}} \right) + xT\left( {{H_{{k_1} - 4,{k_2}}}} \right) + T\\ \left( {{H_{{k_1} - 3,{k_2}}}} \right) \end{array} $ | (10) |
Uk1-1, k2的基图如图 9所示。U2, k2、U2, k2/e亦均是带有正边的图，可直接利用普通图的删除-收缩算法进行Tutte多项式计算。
|
图 9 Uk1-1, k2的基图 Fig.9 Basic graphs of Uk1-1, k2 |
引理8 当k1=2时，图Uk1-1, k2Tutte多项式的基图为U2, k2，U2, k2/e，且
| $ \left\{ {\begin{array}{*{20}{l}} {T\left( {{U_{2,{k_2}}}} \right) = (x + 1)T\left( {{A_{{k_2} + 2}}} \right) + yT\left( {B_{{k_2} + 2}^\prime } \right)}\\ {T\left( {{U_{2,{k_2}}}/e} \right) = T\left( {{A_{{k_2} + 2}}} \right) + yT\left( {B_{{k_2} + 2}^\prime } \right)} \end{array}} \right. $ |
当k2≥k1≥3时，基图Uk1-1, k2的Tutte多项式为
| $ \begin{array}{l} T\left( {{U_{{k_1} - 1,{k_2}}}} \right) = (x + 1)T\left( {{U_{{k_1} - 2,{k_2}}}} \right) + yT\left( {{U_{{k_1} - 3,{k_2}}}} \right) + \\ {y^2}T\left( {{U_{{k_1} - 4,{k_2}}}} \right) + \cdots + {y^{{k_1} - 4}}T\left( {{U_{2,{k_2}}}} \right) + {y^{{k_1} - 3}}T\left( {{U_{2,{k_2}}}/e} \right) \end{array} $ | (11) |
图V″2, k2的基图如图 10所示。Ik2含有1条负边和k2个三角形，考虑将其边缘上的边进行删除-收缩后得到公式(12)；Gk2-1可直接运用普通图的删除-收缩操作得到公式(13)；Lk2-3的Tutte多项式计算过程中需要将负边符号转换为正边之后再进行普通图的删除-收缩操作。
|
图 10 V″2, k2的基图 Fig.10 Basic graphs of V″2, k2 |
引理9 当k1=2时，图V″2, k2Tutte多项式的基图为Gk2-1、Ik2、Lk2-3和V″2, 1，且有
| $ \begin{array}{l} T\left( {{I_{{k_2}}}} \right) = (x + 1)T\left( {{I_{{k_2} - 1}}} \right) + yT\left( {{I_{{k_2} - 2}}} \right) + \cdots + \\ {y^{{k_2} - 3}}T\left( {{I_2}} \right) + {y^{{k_2} - 2}}T\left( {{H_2}} \right) \end{array} $ | (12) |
| $ \begin{array}{l} T\left( {{G_{{k_2} - 2}}} \right) = {x^{{k_2} - 2}}(x + y) + {x^{{k_2} - 3}}\left( {x + y + {y^2}} \right) + \\ {x^{{k_2} - 4}}T\left( {{G_2}} \right) + \cdots + xT\left( {{G_{{k_2} - 4}}} \right) + (1 + y)T\left( {{G_{{k_2} - 3}}} \right) \end{array} $ | (13) |
Ik2的基图H2、I2如图 11所示。
|
图 11 Ik2的基图 Fig.11 Basic graphs of Ik2 |
经过计算，可知有
| $ \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {T\left( {{H_2}} \right) = T\left( {{N_{0,2}}} \right) + y(x + y)(z + 1) + }\\ {y\left( {z + 1 + y + {y^2}} \right)} \end{array}\\ T\left( {V_{2,1}^{\prime \prime }} \right) = T\left( {{N_{0,2}}} \right) + {(x + y)^2} + x + y + {y^2} + {y^3}\\ T\left( {{I_2}} \right) = xT\left( {{N_{0,2}}} \right) + T\left( {{H_2}} \right)\\ T\left( {{L_{00}}} \right) = x(x + y) + y\\ T\left( {{L_0}} \right) = y{(z + y + 1)^2} \end{array} \right. $ |
则当k2≥3时，基图V″2, k2的Tutte多项式为
| $ \begin{array}{l} \begin{array}{*{20}{c}} {T\left( {V_{2,{k_2}}^{\prime \prime }} \right) = T\left( {{I_{{k_2}}}} \right) + T\left( {{I_{{k_2} - 1}}} \right) + \cdots + T\left( {{I_2}} \right) + y[T}\\ {\left( {{G_{{k_2} - 1}}} \right) + T\left( {{G_{{k_2} - 2}}} \right) + \cdots + T\left( {{G_1}} \right)] + T\left( {{L_{{k_2} - 3}}} \right) + T} \end{array}\\ \left( {{L_{{k_2} - 4}}} \right) + \cdots + T\left( {{L_0}} \right) + T\left( {{L_{00}}} \right) + T\left( {V_{2,1}^{\prime \prime }} \right) \end{array} $ | (14) |
将公式(7)~(14)联立，计算得到当k1=3，k2=3、4时，带号图W′k1, k2的Tutte多项式为
| $ \begin{array}{l} T\left( {W_{3,3}^\prime } \right) = {x^7} + 7{x^6} + 6{x^5}y + 22{x^5} + 5{x^4}{y^2} + 32{x^4}y + \\ 40{x^4} + 4{x^3}{y^3} + 32{x^3}{y^2} + 74{x^3}y + 45{x^3} + 3{x^2}{y^4} + \\ \begin{array}{*{20}{l}} {28{x^2}{y^3} + 76{x^2}{y^2} + {x^2}yz + 94{x^2}y + {x^2}{z^2} + 3{x^2}z + 33{x^2} + }\\ {3x{y^5} + 21x{y^4} + 59x{y^3} + 2x{y^2}z + 91x{y^2} + 3xyz + 61xy + } \end{array}\\ \begin{array}{*{20}{l}} {3x{z^2} + 9xz + 18x + 4{y^6} + 12{y^5} + 32{y^4} + {y^3}z + {y^2}{z^2} + 50{y^3} + }\\ {5{y^2}z + 43{y^2} + 2y{z^2} + 7yz + 19y + 3{z^2} + 9z + 9} \end{array} \end{array} $ |
| $ \begin{array}{l} T\left( {W_{3,4}^\prime } \right) = {x^8} + 8{x^7} + 7{x^6}y + 29{x^6} + 6{x^5}{y^2} + 44{x^5}y + \\ 63{x^5} + 5{x^4}{y^3} + 49{x^4}{y^2} + 122{x^4}y + 90{x^4} + 4{x^3}{y^4} + \\ \begin{array}{*{20}{l}} {46{x^3}{y^3} + 149{x^3}{y^2} + 197{x^3}y + 85{x^3} + 4{x^2}{y^5} + 40{x^2}{y^4} + }\\ {137{x^2}{y^3} + 234{x^2}{y^2} + {x^2}yz + 195{x^2}y + {x^2}{z^2} + 3{x^2}z + 52{x^2} + } \end{array}\\ \begin{array}{*{20}{l}} {8x{y^6} + 30x{y^5} + 97x{y^4} + 183x{y^3} + 2x{y^2}z + 199x{y^2} + }\\ {3xyz + 103xy + 3x{z^2} + 9xz + 22x + 4{y^7} + 18{y^6} + 45{y^5} + } \end{array}\\ \begin{array}{*{20}{l}} {87{y^4} + 104{y^3} + {y^3}z + 5{y^2}z + 69{y^2} + 2y{z^2} + 7yz + 23y + }\\ {3{z^2} + 9z + 9} \end{array} \end{array} $ |
结果发现含z的项和常数项的系数固定，对于其他项的系数规律还待进一步探讨。
由χ(A(Σ), t)=χ(Σ, t)=(-1)r(E)tk(Σ)TΣ(1-t, 0, 0)得到，当k1=3，k2=3、4时W′k1, k2对应图构形的特征多项式如下
| $ \begin{array}{c}{\chi\left(W_{3,3}^{\prime}, t\right)=t^{8}-14 t^{7}+85 t^{6}-290 t^{5}+600 t^{4}-} \\ {754 t^{3}+538 t^{2}-175 t}\end{array} $ |
| $ \begin{array}{c}{\chi\left(W_{3,4}^{\prime}, t\right)=t^{9}-16 t^{8}+113 t^{7}-461 t^{6}+1190 t^{5}-} \\ {1991 t^{4}+2108 t^{3}-1294 t^{2}+359 t}\end{array} $ |
进而，因超平面构形OS代数的i(i=1, 2, …)次子代数的维数等于特征多项式系数的绝对值，由此可知曲轮图构形OS代数的i(i=1, 2, …, 9)次子代数维数如表 2所示。
|
|
下载CSV 表 2 k1=3，k2=3、4时W′k1, k2对应图构形OS代数的维数 Table 2 Dimensions of the OS algebra of graphic arrangements W′k1, k2 for k1=3, k2=3、4 |
双吸泵广泛应用于各种输送液体的场合，由于其功率和流量大，对效率和设计性能要求较高。而图构形的Tutte多项式可用于研究其内部结构形式，通过全流道数值模拟分析导流板对排水性能的影响。由于双吸泵模型复杂，将其划分为混合网格，计算模型共有约180万个网络单元，如图 12所示。
|
图 12 计算区域及网格 Fig.12 Computational domain and unstructured mesh |
将双吸泵内部结构转化成平面图，如图 13中W1、W2、W3所示，分流板为平面扇叶中的辐条，实线表示有分流板，虚线表示无分流板。
|
图 13 半螺旋双吸泵平面图 Fig.13 Planar graph of a double suction pump with a semi-volute |
应用带号曲轮图Tutte多项式的计算公式(1)，得到有1条虚线、2条虚线和3条虚线3种不同内部结构的半螺旋双吸泵的Tutte多项式如式(15)~(17)所示。
| $ \begin{array}{l} {T_1} = {x^9} + 9{x^8} + 9{x^7}y + 37{x^7} + 8{x^6}{y^2} + 62{x^6}y + 93{x^6} + \\ 7{x^5}{y^3} + 71{x^5}{y^2} + 194{x^5}y + 162{x^5} + 6{x^4}{y^4} + 69{x^4}{y^3} + \\ \begin{array}{*{20}{l}} {244{x^4}{y^2} + 368{x^4}y + 208{x^4} + 5{x^3}{y^5} + 58{x^3}{y^4} + 232{x^3}{y^3} + }\\ {461{x^3}{y^2} + 468{x^3}y + 195{x^3} + 4{x^2}{y^6} + 39{x^2}{y^5} + } \end{array}\\ \begin{array}{*{20}{l}} {170{x^2}{y^4} + 393{x^2}{y^3} + 531{x^2}{y^2} + 395{x^2}y + {x^2}{z^2} + 3{x^2}z + }\\ {123{x^2} + x{y^7} + 17x{y^6} + 87x{y^5} + 223x{y^4} + 356x{y^3} + } \end{array}\\ \begin{array}{*{20}{l}} {352x{y^2} + xy{z^2} + 3xyz + 194xy + 3x{z^2} + 9xz + 44x + 5{y^7} + }\\ {26{y^6} + 71{y^5} + 125{y^4} + 146{y^3} + {y^2}{z^2} + 3{y^2}z + 109{y^2} + } \end{array}\\ 3y{z^2} + 9yz + 47y + 3{z^2} + 9z + 9 \end{array} $ | (15) |
| $ \begin{array}{l} \begin{array}{*{20}{c}} {{T_2} = {x^9} + 9{x^8} + 8{x^7}y + 37{x^7} + 7{x^6}{y^2} + 59{x^6}y + 92{x^6} + }\\ {5{x^5}{y^3} + 67{x^5}{y^2} + 196{x^5}y + 154{x^5} + 4{x^4}{y^4} + 64{x^4}{y^3} + } \end{array}\\ \begin{array}{*{20}{l}} {252{x^4}{y^2} + 382{x^4}y + 180{x^4} + 4{x^3}{y^5} + 61{x^3}{y^4} + 258{x^3}{y^3} + }\\ {508{x^3}{y^2} + 470{x^3}y + 144{x^3} + 7{x^2}{y^6} + 58{x^2}{y^5} + } \end{array}\\ \begin{array}{*{20}{l}} {228{x^2}{y^4} + 491{x^2}{y^3} + 595{x^2}{y^2} + 351{x^2}y + 72{x^2} + 72{x^2} + }\\ {10x{y^7} + 56x{y^6} + 179x{y^5} + 352x{y^4} + 462x{y^3} + 369x{y^2} + } \end{array}\\ 141xy + 17x + 8{y^8} + 45{y^7} + 104{y^6} + 166{y^5} + 198{y^4} + \\ 172{y^3} + 86{y^2} + 17y \end{array} $ | (16) |
| $ \begin{array}{l} {T_3} = {x^9} + 9{x^8} + 8{x^7}y + 37{x^7} + 7{x^6}{y^2} + 58{x^6}y + 92{x^6} + \\ 6{x^5}{y^3} + 67{x^5}{y^2} + 188{x^5}y + 154{x^5} + 5{x^4}{y^4} + 68{x^4}{y^3} + \\ \begin{array}{*{20}{l}} {246{x^4}{y^2} + 360{x^4}y + 180{x^4} + 5{x^3}{y^5} + 62{x^3}{y^4} + 256{x^3}{y^3} + }\\ {485{x^3}{y^2} + 446{x^3}y + 144{x^3} + 9{x^2}{y^6} + 53{x^2}{y^5} + 217{x^2}{y^4} + } \end{array}\\ \begin{array}{*{20}{l}} {466{x^2}{y^3} + 568{x^2}{y^2} + {x^2}yz + 352{x^2}y + {x^2}{z^2} + 3{x^2}z + }\\ {75{x^2} + 8x{y^7} + 47x{y^6} + 143x{y^5} + 320x{y^4} + 447x{y^3} + } \end{array}\\ \begin{array}{*{20}{l}} {2x{y^2}z + 370x{y^2} + 3xy{z^2} + 3xyz + 152xy + 3x{z^2} + 9xz + }\\ {26x + 22{y^8} + 22{y^7} + 65{y^6} + 133{y^5} + 196{y^4} + {y^3}z + } \end{array}\\ 184{y^3} + 5{y^2}z + 99{y^2} + 2y{z^2} + 7yz + 27y + 3{z^2} + 9z + 9 \end{array} $ | (17) |
进而得到W1、W2、W3对应图构形的特征多项式如式(18)~(20)所示。
| $ \begin{array}{l} \chi \left( {{W_1},t} \right) = {t^{10}} - 18{t^9} + 145{t^8} - 688{t^7} + 2127{t^6} - \\ 4464{t^5} + 6390{t^4} - 6036{t^3} + 3415{t^2} - 881t \end{array} $ | (18) |
| $ \begin{array}{l} \chi \left( {{W_2},t} \right) = {t^{10}} - 18{t^9} + 145{t^8} - 687{t^7} + 2113{t^6} - \\ 4381{t^5} + 6127{t^4} - 5569{t^3} + 2975{t^2} - 706t \end{array} $ | (19) |
| $ \begin{array}{l} \chi \left( {{W_3},t} \right) = {t^{10}} - 18{t^9} + 145{t^8} - 687{t^7} + 2113{t^6} - \\ 4381{t^5} + 6127{t^4} - 5572{t^3} + 2990{t^2} - 727t \end{array} $ | (20) |
本文研究了带号曲轮图构形和带号双半轮图构形的Tutte多项式，给出计算结果，发现这两种轮式图的Tutte多项式不相同，由此说明这两种图是不同构的。本文开始动机是寻找这类图的Tutte多项式的一般表达式，但由于其计算的复杂度和时间问题，尚待以后进一步探讨。
| [1] |
ORLIK P, TERAO H. Arrangements of hyperplanes[M]. Berlin: Springer-Verlag, 1991.
|
| [2] |
ESCHENBRENNER C J, FALK M J. Graphs and matroids determined by their Tutte polynomails[J]. J Alg Comb, 2003, 10(2): 189-199. |
| [3] |
初丽丽, 姜广峰. 一类图构形的Orlic-Solomon代数及Tutte多项式[J]. 北京化工大学学报(自然科学版), 2009, 36(5): 116-120. CHU L L, JIANG G F. Orlik-Solomon algebras and Tutte polynomials[J]. Journal of Beijing University of Chemical Technology(Natural Science), 2009, 36(5): 116-120. (in Chinese) DOI:10.3969/j.issn.1671-4628.2009.05.026 |
| [4] |
李爱民, 姜广峰. 一类碳纳米管状图的Tutte多项式[J]. 北京化工大学学报(自然科学版), 2011, 38(1): 130-135. LI A M, JIANG G F. Tutte polynomials of a class of carbon nanotube-like graph[J]. Journal of Beijing University of Chemical Technology(Natural Science), 2011, 38(1): 130-135. (in Chinese) DOI:10.3969/j.issn.1671-4628.2011.01.027 |
| [5] |
AMAND H. The Tutte polynomial formula for the class of twisted wheel graphs[D]. Oxford: The University of Mississippi, 2014.
|
| [6] |
DUAN Y H, WU H D, YU Q L. On Tutte polynomial uniqueness of twisted wheels[J]. Discrete Mathematics, 2009, 309: 926-936. DOI:10.1016/j.disc.2008.01.039 |
| [7] |
ARDILA F. Computing the Tutte polynomial of a hyperplane arrangement[J]. Pacific J Math, 2007, 230(1): 1-26. |