×
Log in to StudySoup
Get Full Access to UVM - CS 064 - Class Notes - Week 10
Join StudySoup
Get Full Access to UVM - CS 064 - Class Notes - Week 10

Already have an account? Login here
×
Reset your password

UVM / Computer science / CS 064 / What is disjoint set?

What is disjoint set?

What is disjoint set?

Description

ul.lst-kix_zgwk5fnuwrt3-2{list-style-type:none}ul.lst-kix_zgwk5fnuwrt3-3{list-style-type:none}ul.lst-kix_zgwk5fnuwrt3-4{list-style-type:none}ul.lst-kix_zgwk5fnuwrt3-5{list-style-type:none}ul.lst-kix_zgwk5fnuwrt3-0{list-style-type:none}ul.lst-kix_zgwk5fnuwrt3-1{list-style-type:none}.lst-kix_tyi5x0ayu2wj-7 > li:before{content:"○ "}.lst-kix_tyi5x0ayu2wj-8 > li:before{content:"■ "}ul.lst-kix_zgwk5fnuwrt3-6{list-style-type:none}ul.lst-kix_zgwk5fnuwrt3-7{list-style-type:none}ul.lst-kix_zgwk5fnuwrt3-8{list-style-type:none}ul.lst-kix_tyi5x0ayu2wj-8{list-style-type:none}.lst-kix_bohk2wc46gpj-0 > li:before{content:"● "}.lst-kix_xyyr2jz3rjrn-6 > li:before{content:"● "}.lst-kix_xyyr2jz3rjrn-7 > li:before{content:"○ "}.lst-kix_bohk2wc46gpj-2 > li:before{content:"■ "}.lst-kix_xyyr2jz3rjrn-5 > li:before{content:"■ "}.lst-kix_bohk2wc46gpj-1 > li:before{content:"○ "}ul.lst-kix_tyi5x0ayu2wj-0{list-style-type:none}.lst-kix_bohk2wc46gpj-4 > li:before{content:"○ "}ul.lst-kix_tyi5x0ayu2wj-1{list-style-type:none}ul.lst-kix_tyi5x0ayu2wj-2{list-style-type:none}ul.lst-kix_tyi5x0ayu2wj-3{list-style-type:none}ul.lst-kix_tyi5x0ayu2wj-4{list-style-type:none}ul.lst-kix_tyi5x0ayu2wj-5{list-style-type:none}.lst-kix_xyyr2jz3rjrn-8 > li:before{content:"■ "}ul.lst-kix_tyi5x0ayu2wj-6{list-style-type:none}.lst-kix_bohk2wc46gpj-3 > li:before{content:"● "}ul.lst-kix_tyi5x0ayu2wj-7{list-style-type:none}.lst-kix_qsutgvxytovw-0 > li:before{content:"● "}.lst-kix_zgwk5fnuwrt3-0 > li:before{content:"● "}.lst-kix_zgwk5fnuwrt3-2 > li:before{content:"■ "}.lst-kix_xyyr2jz3rjrn-1 > li:before{content:"○ "}ul.lst-kix_bohk2wc46gpj-8{list-style-type:none}.lst-kix_zgwk5fnuwrt3-1 > li:before{content:"○ "}.lst-kix_zgwk5fnuwrt3-5 > li:before{content:"■ "}ul.lst-kix_bohk2wc46gpj-6{list-style-type:none}.lst-kix_xyyr2jz3rjrn-2 > li:before{content:"■ "}.lst-kix_xyyr2jz3rjrn-3 > li:before{content:"● "}ul.lst-kix_bohk2wc46gpj-7{list-style-type:none}ul.lst-kix_bohk2wc46gpj-4{list-style-type:none}.lst-kix_zgwk5fnuwrt3-4 > li:before{content:"○ "}ul.lst-kix_bohk2wc46gpj-5{list-style-type:none}ul.lst-kix_bohk2wc46gpj-2{list-style-type:none}.lst-kix_xyyr2jz3rjrn-4 > li:before{content:"○ "}ul.lst-kix_bohk2wc46gpj-3{list-style-type:none}ul.lst-kix_bohk2wc46gpj-0{list-style-type:none}.lst-kix_zgwk5fnuwrt3-3 > li:before{content:"● "}ul.lst-kix_bohk2wc46gpj-1{list-style-type:none}.lst-kix_zgwk5fnuwrt3-8 > li:before{content:"■ "}.lst-kix_zgwk5fnuwrt3-6 > li:before{content:"● "}.lst-kix_xyyr2jz3rjrn-0 > li:before{content:"● "}.lst-kix_zgwk5fnuwrt3-7 > li:before{content:"○ "}ul.lst-kix_xyyr2jz3rjrn-4{list-style-type:none}ul.lst-kix_qsutgvxytovw-4{list-style-type:none}ul.lst-kix_xyyr2jz3rjrn-5{list-style-type:none}ul.lst-kix_qsutgvxytovw-5{list-style-type:none}ul.lst-kix_xyyr2jz3rjrn-2{list-style-type:none}ul.lst-kix_qsutgvxytovw-6{list-style-type:none}ul.lst-kix_xyyr2jz3rjrn-3{list-style-type:none}ul.lst-kix_qsutgvxytovw-7{list-style-type:none}ul.lst-kix_xyyr2jz3rjrn-8{list-style-type:none}ul.lst-kix_qsutgvxytovw-8{list-style-type:none}ul.lst-kix_xyyr2jz3rjrn-6{list-style-type:none}ul.lst-kix_xyyr2jz3rjrn-7{list-style-type:none}ul.lst-kix_qsutgvxytovw-0{list-style-type:none}.lst-kix_qsutgvxytovw-2 > li:before{content:"■ "}ul.lst-kix_qsutgvxytovw-1{list-style-type:none}.lst-kix_qsutgvxytovw-1 > li:before{content:"○ "}ul.lst-kix_qsutgvxytovw-2{list-style-type:none}ul.lst-kix_qsutgvxytovw-3{list-style-type:none}.lst-kix_bohk2wc46gpj-8 > li:before{content:"■ "}.lst-kix_bohk2wc46gpj-6 > li:before{content:"● "}.lst-kix_bohk2wc46gpj-5 > li:before{content:"■ "}.lst-kix_qsutgvxytovw-3 > li:before{content:"● "}.lst-kix_qsutgvxytovw-4 > li:before{content:"○ "}.lst-kix_tyi5x0ayu2wj-0 > li:before{content:"● "}.lst-kix_bohk2wc46gpj-7 > li:before{content:"○ "}.lst-kix_qsutgvxytovw-5 > li:before{content:"■ "}.lst-kix_tyi5x0ayu2wj-2 > li:before{content:"■ "}.lst-kix_tyi5x0ayu2wj-1 > li:before{content:"○ "}.lst-kix_tyi5x0ayu2wj-3 > li:before{content:"● "}.lst-kix_qsutgvxytovw-6 > li:before{content:"● "}.lst-kix_qsutgvxytovw-8 > li:before{content:"■ "}.lst-kix_qsutgvxytovw-7 > li:before{content:"○ "}.lst-kix_tyi5x0ayu2wj-6 > li:before{content:"● "}.lst-kix_tyi5x0ayu2wj-5 > li:before{content:"■ "}.lst-kix_tyi5x0ayu2wj-4 > li:before{content:"○ "}ul.lst-kix_xyyr2jz3rjrn-0{list-style-type:none}ul.lst-kix_xyyr2jz3rjrn-1{list-style-type:none}

CS 064 If you want to learn more check out ming dong gu

Class Notes

Equivalence Class

Let R denote an equivalence relation on some set A.

Let a  A. We also discuss several other topics like ∙ How secure does legislator believe they are?

[a] : { x  A : x R a }

We also discuss several other topics like What are the factors affecting long productivity growth?

some times we may writt:

[a]R 

[a] is called an equivalence class.

Proposition 15.9 We also discuss several other topics like What are the three waves of feminism?

Let R denote an equivalence relation on set A.

Let a, b  A, with

[a] = { x  A : xRa } Don't forget about the age old question of cloth mother wire mother

Then, If you want to learn more check out What is the extent of ionization of a weak acid decreases in the presence of a strong electrolyte that shares a common ion?

a [a]

Then, (15.10)

a R b [a]  [a] = [b]

Then, (15.11)

Let a,x,y  [a] if x,y  [a] xRy

Then, 815.12)

[a][b]0, then [a] =[b]

Example ≡ mod2 

[0] = { x  Z : x = 0 (mod2)} 

[1] = { x  Z : x = 2 (mod2)}

Given an ER on set A we can construct a system of equivalence classes, call it E(, [a] ={X  A, X R a}

(ER= equivalence relation)

for which

  • every element of A belongs to an equivalence class
  • every equivalence class contains at least one element
  • every pair of enviralence classes is disjoint pairwise

Ex.         R: x ≡ y (mod 3)

xRy whenever x≡y (mod 3)

[0] = {xZ: x= 0 (mod 3)

[1] = {xZ: x= 1 (mod 3)}

[2] = {xZ: x = 2 (mod 3)

  • Disjoint set - a pair of equivalence classes that when intersected is the null set

ex. [O] [1] = 0

  • Partition - a partition of A is a set of nonempty, pairwise disjoint subsets of A whose union is A. (P)

  • ex. Facebook friends partitioned

ex. partitioned numbers

 = {P1, P2,Pn}

   𝜬

x if x, y P, where P

         𝜬                    𝜬

Ex 3  7, 7 3

  • partitions are reflexive, symmetric, and transitive

  • Every partition implicitly defines an equivalence relation; P is another way of creating an equivalence relation.
Page Expired
5off
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here