无向图的最大割问题。给定一个无向图G=(V，E)，设UVUV是G的顶点集。对任意(u，v)∈E，若有u∈U且v∈V-U，就称(u，v)为关于顶点集U的一条割边。顶点集U的所有割边构成图G的一个割。G的最大割是指G中所含边数最多的割。对于给定的无向图G，设计一个优先队列式分支限界法，计算G的最大割。
举一反三
- 设u,v是图G的两个不邻接的顶点， S是图G的顶点割集，且u,v是属于 的两个G-S不同的连通分支，称 S为一个uv分离集。设最小的uv分离集中所含顶点的个数为a ， 且G中从u 到v 内部不相交的路的最大条数为b ，则 a和 b满足的关系为______
- 无向连通图G中，点v是割点的充要条件为（ ） A: v是悬挂顶点 B: v是奇度顶点 C: 存在两个顶点u，w，使得顶点u和w每一条通路都通过v D: v不包含在G的任一回路中。
- _________指的是从有向图G=(V，E)中得到一个顶点的线性序列，满足如果G包含边(u，v)，则在该序列中，u就出现在v的前面。
- 无向图G中只有两个奇度数顶点u和v，则u与v必连通
- 给定图G=（V，E），若图G’=（V’，E’），其中V’ÍV，E’={uv|uv∈E，u，v∈v’}，则称G’是G的子图。