در نظریه مجموعه ها دو مجموعهٔ A {\displaystyle A} و B {\displaystyle B} مجموعه های مجزا (به انگلیسی: Disjoint sets) هستند، دارای هیچ عضو مشترکی نباشند. چند مجموعه به صورت زوج مجزا هستند اگر هر جفت دوتایی از آن ها دارای عضو مشترک نباشد.
مجموعه های A = { 1 , 2 , 3 } {\displaystyle A=\{1,2,3\}} و B = { 7 , 8 , 11 } {\displaystyle B=\{7,8,11\}} مجزایند، چون هیچ عضو مشترکی ندارد.
مجموعه های A = { 1 , 2 , 7 } {\displaystyle A=\{1,2,7\}} و B = { 6 , 7 , 8 , 11 } {\displaystyle B=\{6,7,8,11\}} مجزا نیستند، چون دارای عضو مشترک 7 {\displaystyle 7} هستند.
سه مجموعهٔ A = { 1 , 2 , 3 } {\displaystyle A=\{1,2,3\}} ، B = { 4 , 5 } {\displaystyle B=\{4,5\}} و C = { 5 , 6 , 7 } {\displaystyle C=\{5,6,7\}} به صورت جفت مجزا نیستند، چون حداقل یکی از اشتراک های آن ها ( B ∩ C {\displaystyle B\cap C} ) مجموعهٔ غیرتهی است.
مجموعه های A {\displaystyle A} و B {\displaystyle B} مجزا هستند، زمانی که اشتراک آن ها مجموعهٔ تهی باشد، در این صورت داریم:
یک خانواده ( M i ) i ∈ I {\displaystyle (M_{i})_{i\in I}} (مجموعه ای از مجموعه ها) زمانی مجزا است که تمامی اعضای آن جفت-جفت مجزا باشند، در این صورت داریم:
اگر اجتماع این مجموعه ها را در نظر بگیریم، آنگاه اجتماع مجموعه های مجزا به دست می آید که به شکل زیر است:
مجموعه های A = { 1 , 2 , 3 } {\displaystyle A=\{1,2,3\}} و B = { 7 , 8 , 11 } {\displaystyle B=\{7,8,11\}} مجزایند، چون هیچ عضو مشترکی ندارد.
مجموعه های A = { 1 , 2 , 7 } {\displaystyle A=\{1,2,7\}} و B = { 6 , 7 , 8 , 11 } {\displaystyle B=\{6,7,8,11\}} مجزا نیستند، چون دارای عضو مشترک 7 {\displaystyle 7} هستند.
سه مجموعهٔ A = { 1 , 2 , 3 } {\displaystyle A=\{1,2,3\}} ، B = { 4 , 5 } {\displaystyle B=\{4,5\}} و C = { 5 , 6 , 7 } {\displaystyle C=\{5,6,7\}} به صورت جفت مجزا نیستند، چون حداقل یکی از اشتراک های آن ها ( B ∩ C {\displaystyle B\cap C} ) مجموعهٔ غیرتهی است.
مجموعه های A {\displaystyle A} و B {\displaystyle B} مجزا هستند، زمانی که اشتراک آن ها مجموعهٔ تهی باشد، در این صورت داریم:
یک خانواده ( M i ) i ∈ I {\displaystyle (M_{i})_{i\in I}} (مجموعه ای از مجموعه ها) زمانی مجزا است که تمامی اعضای آن جفت-جفت مجزا باشند، در این صورت داریم:
اگر اجتماع این مجموعه ها را در نظر بگیریم، آنگاه اجتماع مجموعه های مجزا به دست می آید که به شکل زیر است:
wiki: افراز کنیم. داده ساختار مجموعه های مجزا، داده ساختاری است که این کار را انجام می دهد. یک الگوریتم جستجو-ادغام، الگوریتمی است که دو عمل زیر را روی این داده ساختار انجام می دهد:
جستجو: مشخص می کند که یک عنصر در کدام مجموعه قرار دارد. همچنین می تواند مشخص کند که آیا دو عنصر در یک مجموعه قرار دارند یا نه.
ادغام: دو مجموعه را با هم ادغام می کند و یک مجموعه جدید می سازد.
عملیات مهم دیگری هم که روی این داده ساختار انجام می شود، ایجاد مجموعه است که یک مجموعه جدید شامل یک عضو داده شده را ایجاد می کند که عموماً بسیار ساده است.با در اختیار داشتن این ۳ عمل، می توان بسیاری از مسائل تقسیم بندی را حل کرد.برای این که این ۳ عمل را با دقت تعریف کنیم، روشی برای مشخص کردن مجموعه ها لازم است. یک روش معمول برای این کار این است که برای هر مجموعه، یک عضو مشخص از آن را انتخاب کنیم و آن را نماینده این مجموعه بنامیم. در این صورت، تابع جستجو برای یک عضو، نماینده مجموعه ای که این عضو در آن قرار دارد را برمی گرداند و تابع ادغام نماینده دو مجموعه را به عنوان ورودی می گیرد.
یک روش ساده برای ساختن این داده ساختار به این شکل است که برای هر مجموعه، یک لیست پیوندی تشکیل دهیم و عنصر ابتدای هر لیست را به عنوان نماینده آن مجموعه انتخاب کینم.تابع ایجاد مجموعه، یک لیست جدید با یک عنصر را می سازد. تابع ادغام، لیست دو مجموعه را به هم پیوند می دهد، که زمان ثابتی می گیرد. مشکل این روش پیاده سازی در تابع جستجو است که به زمان (Ωنماد O بزرگ|]](n]] احتیاج دارد. می توان با اضافه کردن یک اشاره گر به هر گره در لیست ها که به ابتدای آن لیست اشاره می کند، این مشکل را رفع کرد. اما حالا تابع ادغام باید این اشاره گر تمام گره های یک لیست که به لیست دیگری چسبانده می شود را به روز کند، پس این تابع به زمان (Ω(n احتیاج دارد.اگر طول هر لیست را نگه داریم، و در هر مرحله لیست کوچکتر را به لیست بزرگتر بچسبانیم، می توان زمان را بهبود داد. در این صورت اگر از m تابع جستجو، ادغام و ایجاد مجموعه روی n عضو اعمال شوند، زمان(O(m + n log n مصرف می شود.
در این پیاده سازی هر مجموعه به وسیله یک درخت نشان داده می شود که هر گره در آن یک اشاره گر به پدرش دارد. این پیاده سازی ابتدا توسط برنارد ای. گالر و مایکل جی. فیشر در سال ۱۹۶۴ پیشنهاد شد، البته تحلیل زمانی دقیق آن تا مدت ها طول کشید.در این روش، نماینده هر مجموعه، ریشه درخت آن مجموعه انتخاب می شود. تابع جستجو، پدران یک راس را تا جایی دنبال می کند که به ریشه درخت برسد و تابع ادغام، ریشه یک درخت را به ریشه درخت دیگر متصل می کند تا یک درخت به وجود بیاید. یکی از روش های پیاده سازی می تواند به شکل زیر باشد:
جستجو: مشخص می کند که یک عنصر در کدام مجموعه قرار دارد. همچنین می تواند مشخص کند که آیا دو عنصر در یک مجموعه قرار دارند یا نه.
ادغام: دو مجموعه را با هم ادغام می کند و یک مجموعه جدید می سازد.
عملیات مهم دیگری هم که روی این داده ساختار انجام می شود، ایجاد مجموعه است که یک مجموعه جدید شامل یک عضو داده شده را ایجاد می کند که عموماً بسیار ساده است.با در اختیار داشتن این ۳ عمل، می توان بسیاری از مسائل تقسیم بندی را حل کرد.برای این که این ۳ عمل را با دقت تعریف کنیم، روشی برای مشخص کردن مجموعه ها لازم است. یک روش معمول برای این کار این است که برای هر مجموعه، یک عضو مشخص از آن را انتخاب کنیم و آن را نماینده این مجموعه بنامیم. در این صورت، تابع جستجو برای یک عضو، نماینده مجموعه ای که این عضو در آن قرار دارد را برمی گرداند و تابع ادغام نماینده دو مجموعه را به عنوان ورودی می گیرد.
یک روش ساده برای ساختن این داده ساختار به این شکل است که برای هر مجموعه، یک لیست پیوندی تشکیل دهیم و عنصر ابتدای هر لیست را به عنوان نماینده آن مجموعه انتخاب کینم.تابع ایجاد مجموعه، یک لیست جدید با یک عنصر را می سازد. تابع ادغام، لیست دو مجموعه را به هم پیوند می دهد، که زمان ثابتی می گیرد. مشکل این روش پیاده سازی در تابع جستجو است که به زمان (Ωنماد O بزرگ|]](n]] احتیاج دارد. می توان با اضافه کردن یک اشاره گر به هر گره در لیست ها که به ابتدای آن لیست اشاره می کند، این مشکل را رفع کرد. اما حالا تابع ادغام باید این اشاره گر تمام گره های یک لیست که به لیست دیگری چسبانده می شود را به روز کند، پس این تابع به زمان (Ω(n احتیاج دارد.اگر طول هر لیست را نگه داریم، و در هر مرحله لیست کوچکتر را به لیست بزرگتر بچسبانیم، می توان زمان را بهبود داد. در این صورت اگر از m تابع جستجو، ادغام و ایجاد مجموعه روی n عضو اعمال شوند، زمان(O(m + n log n مصرف می شود.
در این پیاده سازی هر مجموعه به وسیله یک درخت نشان داده می شود که هر گره در آن یک اشاره گر به پدرش دارد. این پیاده سازی ابتدا توسط برنارد ای. گالر و مایکل جی. فیشر در سال ۱۹۶۴ پیشنهاد شد، البته تحلیل زمانی دقیق آن تا مدت ها طول کشید.در این روش، نماینده هر مجموعه، ریشه درخت آن مجموعه انتخاب می شود. تابع جستجو، پدران یک راس را تا جایی دنبال می کند که به ریشه درخت برسد و تابع ادغام، ریشه یک درخت را به ریشه درخت دیگر متصل می کند تا یک درخت به وجود بیاید. یکی از روش های پیاده سازی می تواند به شکل زیر باشد: