Nesouvislé sady - Disjoint sets

Dvě nesouvislé sady.

V matematice se říká , že dvě sady jsou disjunktní množiny, pokud nemají žádný společný prvek . Ekvivalentně dvě nesouvislé množiny jsou množiny, jejichž průsečíkem je prázdná množina . Například {1, 2, 3} a {4, 5, 6} jsou disjunktní sady, zatímco {1, 2, 3} a {3, 4, 5} nejsou disjunktní. Kolekce více než dvou sad se nazývá disjunktní, pokud jsou dvě odlišné sady kolekce disjunktní.

Zobecnění

Nesouhlasná kolekce sad

Tuto definici disjunktních množin lze rozšířit na rodinu sad : rodina je párově disjunktní nebo vzájemně disjunktní , kdykoli je to možné . Alternativně někteří autoři také používají termín disjunktní pro označení tohoto pojmu.

Pro rodiny je pojem párově disjunktní nebo vzájemně disjunktní někdy definován jemně odlišným způsobem, a to tak, že jsou povoleny opakované identické členy: rodina je párově disjunktní, kdykoli (každé dvě odlišné sady v rodině jsou disjunktní). Například kolekce množin {{0,1,2}, {3,4,5}, {6,7,8}, ...} je nesouvislá, stejně jako množina {{... ... 2 , 0,2,4, ...}, {...− 3, −1,1,3,5 }} dvou paritních tříd celých čísel; rodina s 10 členy není disjunktní (protože třídy sudých a lichých čísel jsou vždy pětkrát), ale podle této definice je párová disjunkce (protože jeden dostane pouze neprázdný průnik dvou členů, když jsou dva stejné třídy).

O dvou množinách se říká, že jsou téměř nesouvislé množiny, pokud je jejich průnik v určitém smyslu malý. Například o dvou nekonečných množinách, jejichž průsečík je konečná množina, lze říci, že jsou téměř disjunktní.

V topologii existují různé představy o oddělených množinách s přísnějšími podmínkami než disjunktnost. Například dvě sady lze považovat za oddělené, pokud mají disjunktní uzávěry nebo disjunktní sousedství . Podobně v metrickém prostoru jsou kladně oddělené množiny množiny oddělené nenulovou vzdáleností .

Křižovatky

Nesouvislost dvou množin nebo rodiny množin může být vyjádřena jako průniky jejich dvojic.

Dvě sady a B jsou disjunktní tehdy a jen tehdy, pokud je jejich průsečík je prázdná množina . Z této definice vyplývá, že každá množina je disjunktní od prázdné množiny a že prázdná množina je jedinou množinou, která je disjunktní od sebe.

Pokud kolekce obsahuje alespoň dvě sady, podmínka, že kolekce je disjunktní, znamená, že průsečík celé kolekce je prázdný. Kolekce sad však může mít prázdnou křižovatku, aniž by byla disjunktní. Navíc, zatímco kolekce méně než dvou sad je triviálně disjunktní, protože neexistují žádné páry k porovnání, průsečík kolekce jedné sady se rovná té sadě, která může být neprázdná. Například tři sady {{1, 2}, {2, 3}, {1, 3}} mají prázdný průnik, ale nejsou disjunktní. Ve skutečnosti v této kolekci nejsou žádné dvě nesouvislé sady. Také prázdná rodina sad je párově disjunktní.

Helly Rodina je systém souborů, ve kterém jediné podskupiny s prázdnými křižovatkách jsou ty, které jsou po dvou disjunktní. Například, uzavřené intervaly jednotlivých reálných čísel tvoří rodinu Helly: pokud rodina uzavřených intervalů má prázdný průnik a je minimální (tj ne podčeleď rodiny má prázdný průnik), musí být po dvou disjunktní.

Nespojené odbory a oddíly

Oddíl nastavený X je jakákoliv kolekce vzájemně disjunktních neprázdných množin, jejichž sjednocení je X . Každý oddíl lze ekvivalentně popsat relací ekvivalence , binární relací, která popisuje, zda dva prvky patří do stejné sady v oddílu. Disjunktní datové struktury a zdokonalení oddílů jsou dvě techniky ve vědě o počítačích pro efektivní udržování oddílů množiny, které jsou předmětem operací sjednocení, které spojují dvě sady, nebo operací zdokonalení, které rozdělují jednu sadu na dvě.

Disjunktní sjednocení může znamenat jednu ze dvou věcí. Nejjednodušší to může znamenat spojení množin, které jsou disjunktní. Ale pokud dvě nebo více sad již nejsou disjunktní, jejich disjunktní sjednocení může být vytvořeno úpravou sad, aby byly disjunktní před vytvořením sjednocení upravených sad. Například dvě sady mohou být disjunktní nahrazením každého prvku uspořádanou dvojicí prvku a binární hodnotou označující, zda patří do první nebo druhé sady. U rodin s více než dvěma sadami může jeden podobně nahradit každý prvek uspořádanou dvojicí prvku a indexem sady, která jej obsahuje.

Viz také

Reference

externí odkazy