3-dimensional matching

Problemstellung:

Gegeben: Mengen $U,V,W$ mit $|U|=|V|=|W|$ und Teilmenge $T\subseteq V\times W\times U$. Entscheide: Gibt es eine Teilmenge $M \subseteq T$ mit $|M|=|U|$ mit der Eigenschaft: Für jede zwei unterschiedliche $(u,v,w),(v',v',w')\in M$ gilt $u\not=u',v\not=v'$ und $w\not=w'$?

Satz: 3-dimensional matching

CLIQUE ist NP-vollständig.

Beweis Idee: #TODO

1. 3-dimensional matching $\in NP$
2. $\textrm{SAT}\preceq$ 3-dimensional matching