基于线性代数的一般图匹配 中山市中山纪念中学 杨家齐
最后，我们不加证明地给出一个结论
定理 1.1. 以下四个问题的复杂度相等
1. 计算矩阵的行列式；
2. 将两个矩阵相乘；
3. 求矩阵的逆；
4. 对矩阵做高斯消元（LU 分解）。
我们设这四者的复杂度都是 O(n
ω
)
4
。
2 完美匹配的存在性
2.1 Tutte 定理
定义 2.1 (Tutte 矩阵). 对于一个无向图 G = (V, E), 定义 G 的 Tutte 矩阵为一个 n × n 的矩阵
˜
A(G), 其中
˜
A(G)
i, j
=
x
i, j
若 v
i
v
j
∈ E 并且 i < j
−x
j,i
若 v
i
v
j
∈ E 并且 i > j
0 其它情况
其中，x
i, j
是一个与边 v
i
v
j
相关联的独一无二的变量。
下面我们来看一个例子。
v
1
v
2
v
3
v
4
x
1,2
x
2,3
x
3,4
x
1,4
x
1,3
0 x
1,2
x
1,3
x
1,4
−x
1,2
0 x
2,3
0
−x
1,3
−x
2,3
0 x
3,4
−x
1,4
0 −x
3,4
0
图 1: 图 G 与它的 Tutte 矩阵
图 1 的左半 部分给出了一个图 G，右半部分给 出了图 G 所对应的 Tutte 矩阵
˜
A(G)。可
以看到，图 G 的每条边都对应着一个变量，因此
˜
A(G) 中总共会用到 |E| 个变量。
4
学术界一般认为 2 ≤ ω < 2.373。
14
剩余203页未读，继续阅读
iamxym
- 粉丝: 105
- 资源: 5
我的内容管理
展开
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测：静态代码分析与数据流方法
- 青苔数据CEO程永：技术生态与阿里云开放创新
- 制造业转型： HyperX引领企业上云策略
- 赵维五分享：航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器：设计与实现
- 猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
