μ§ν© μμ κ°μ κ³μ°κΈ° μ¬μ©λ²
μ§ν© μμ κ°μ κ³μ°κΈ°λ λ μ§ν© A, Bμ μμ μμ κ΅μ§ν© μμ μλ₯Ό μ λ ₯νλ©΄ ν©μ§ν©, μ°¨μ§ν©, μ¬μ§ν©μ μμ κ°μλ₯Ό μλμΌλ‘ κ³μ°ν©λλ€. μν κ΅κ³Όμμ μ§ν© λ¨μ λ¬Έμ νμ΄μ λ°λ‘ νμ©ν μ μμ΅λλ€.
μ£Όμ 곡μ
ν©μ§ν©(ν¬ν¨λ°°μ μ리): |AβͺB| = |A| + |B| β |Aβ©B|. μ°¨μ§ν©: |AβB| = |A| β |Aβ©B|, |BβA| = |B| β |Aβ©B|. μ¬μ§ν©(μ 체 μ§ν© νμ): |AαΆ| = |U| β |A|, |οΌAβͺBοΌαΆ| = |U| β |AβͺB|.
μ 체 μ§ν© Uμ μν
μ¬μ§ν©μ μ 체 μ§ν© Uμμ νΉμ μ§ν©μ μ μΈν λλ¨Έμ§μ λλ€. μ 체 μ§ν© μμ μλ₯Ό μ λ ₯νλ©΄ Aμ μ¬μ§ν©, Bμ μ¬μ§ν©, ν©μ§ν©μ μ¬μ§ν©κΉμ§ ν λ²μ κ³μ°λ©λλ€. μ 체 μ§ν© μμ΄λ ν©μ§ν©Β·μ°¨μ§ν©μ κ³μ° κ°λ₯ν©λλ€.
μ λ ₯ 쑰건
κ΅μ§ν© |Aβ©B|λ min(|A|, |B|)λ₯Ό μ΄κ³Όν μ μμ΅λλ€. μ 체 μ§ν© |U|λ ν©μ§ν© |AβͺB| μ΄μμ΄μ΄μΌ νλ©°, λͺ¨λ μμ μλ 0 μ΄μμ μ μλ₯Ό μ λ ₯νμΈμ.
μμ£Ό 묻λ μ§λ¬Έ
λ μ§ν©μ΄ μλ‘μ(disjoint)μ λλ€. ν©μ§ν© = |A| + |B|, μ°¨μ§ν© |AβB| = |A|, |BβA| = |B|κ° λ©λλ€.
ν©μ§ν©κ³Ό μ°¨μ§ν©μ μ 체 μ§ν© μμ΄λ κ³μ°λ©λλ€. μ¬μ§ν©λ§ μ 체 μ§ν© |U|κ° νμν©λλ€.
곡μ§ν©(μμ μ 0)λ μ ν¨ν©λλ€. μλ₯Ό λ€μ΄ |A| = 0μ΄λ©΄ κ΅μ§ν©λ 0μ΄μ΄μΌ ν©λλ€.