高斯消元

Published: June 16, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 算法流程

算法流程

随便找一本代数的书，都可以找到算法流程。

题目1：给定$n$个顶点的一个无向图，要求将顶点分成两个子图，跨越子图的边统统删去。要求使得最后拥有偶数度数的顶点最多。问如何分组。其中$1\leq n\leq 2000$，保证无自环。

提供一道问题。

首先我们考虑有$n$个未知数$x_1,\ldots,x_n$，其中$x_i=0$表示将$i$分到第一组，$x_i=1$表示分到第二组。

现在我们尝试使所有顶点都变成偶数度数。这时候一条边$(u,v)$的对顶点$u$和$v$的度数会产生相同的贡献：$x_u+x_v+1$。我们从而可以得到一个方程组$Ax=b$。可以发现$A$是一个对称矩阵，且$b_i=A_{i,i}$。这里所有的运算都发生在$\mathbb{Z}_2$上。

之后我们证明我们的方程组始终是有解的。假设无解，即存在一个行的线性组合，使得左边为$0$，右边非$0$。考虑选择的行为$r_1,\ldots,r_k$。这时候左边第$j$列的和$A_{r_1,j}+A_{r_2,j}+\ldots+A_{r_k,j}=0$，故我们同样可以得到$\sum_{i=1}^k\sum_{j=1}^kA_{r_i,r_j}=0$，考虑到$A$是对称的，因此可以化简为$\sum_{i=1}^kA_{r_i,r_i}=\sum_{i=1}^kb_i=0$，这和我们之前提到的右边和非$0$相悖，因此可以证明方程组始终有解。

这里由于是$\mathbb{Z}_2$上的运算，因此我们可以用bitset来加速，时间复杂度为$O(\frac{n^3}{32})$。