英文
bridge
简介
图论的一个重要概念.指图在空间中嵌入的一类开子集.若将图G视为在三维欧氏空间中的嵌入，则桥就是对于G的一个子图H，G-H的连通片.一般地，所谓桥是指H是一个圈C的情形.若B为G的对于圈C的桥，则[B]-B称为B在C上的触点，其中，[B]为B的闭包.在C上B的两个相继的触点之间的一段曲线称为B的桥际.若两桥B1和B2，其中之一所有触点全落在另一个的某一桥际中，则称B1和B2是相容的;否则称为相克的.这两个概念对于B1和B2是对称的.若G对于C的桥按照相容性至多可分为两类，则G是可平面的.反之，对于任何可平面图G，任取一个圈C，G的桥按相容性至多可分为两类.另外，若G是可平面的，则G1和G2是G的两个平面嵌入.G1与G2平面等价当且仅当在G中存在一个圈C使G1和G2对于C的内桥与内桥和外桥与外桥之间存在一一对应.第一位引入桥的概念的学者是塔特(Tutte，W.T.).不过，他当时用的是组合的语言，而不是用点集拓扑的语言.当然，此两者实质上是等价的.塔特基于对桥的结构分析建立了图的各种连通性的理论，使他首先发现任何4连通的可平面图有哈密顿圈，以及由此也可以直接地导出库拉托夫斯基定理等.