【三维匹配问题】
给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合T⊆X×Y×ZT \subseteq X \times Y \times ZT⊆X×Y×Z,集合T的大小为m。
问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。
三维匹配问题其实是集合覆盖和集合包装问题的特例。
三维匹配问题是NP完全的
首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT≤p\leq_p≤p三维匹配证明。
【3-SAT≤p\leq_p≤p三维匹配证明】
2021-12-05 14:57:33
289KB
tip
三元组
1