Nesouvislé sady - Disjoint sets

Tento článek je o matematickém pojetí. Pro datovou strukturu viz Disjunktně nastavená datová struktura.
Dvě nesouvislé sady.

v matematika, dva sady se říká, že jsou disjunktní sady pokud nemají živel společné. Ekvivalentně dvě nesouvislé množiny jsou množiny, jejichž průsečík je prázdná sada.[1]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 nesouvislých množin lze rozšířit na a rodina sad : rodina je párově disjunktnínebo vzájemně disjunktní -li kdykoli . 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 mírně odlišným způsobem, a to tak, že jsou povoleny opakované identické členy: rodina je párově disjunktní, pokud kdykoli (každé dva odlišný množiny v rodině jsou disjunktní).[2] Například kolekce sad { {0,1,2}, {3,4,5}, {6,7,8}, ... } je disjunktní, stejně jako sada { {...,-2,0,2,4,...}, {...,-3,-1,1,3,5 }} ze 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řítomny pětkrát), ale je párově disjunktní podle této definice (protože jeden dostane pouze neprázdný průnik dvou členů, když jsou dva stejné třída).

Říká se, že jsou dvě sady téměř nesouvislé sady pokud je jejich průnik v určitém smyslu malý. Například dva nekonečné množiny jehož průsečík je a konečná množina lze říci, že jsou téměř disjunktní.[3]

v topologie, existují různé představy o oddělené sady s přísnějšími podmínkami než disjunktnost. Například dvě sady mohou být považovány za oddělené, když mají disjunkt uzávěry nebo disjunktní sousedství. Podobně v a metrický prostor, kladně oddělené množiny jsou sady oddělené nenulovou hodnotou vzdálenost.[4]

Křižovatky

Nesouvislost dvou sad nebo rodiny sad lze vyjádřit pomocí křižovatky párů z nich.

Dvě sady A a B jsou disjunktní, právě když jsou jejich průsečíky je prázdná sada.[1]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.[5]

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á.[2] Například tři sady { {1, 2}, {2, 3}, {1, 3} } mají prázdnou křižovatku, ale nejsou disjunktní. Ve skutečnosti v této kolekci nejsou žádné dvě nesouvislé sady. Také prázdná rodina sad je párově disjunktní.[6]

A Helly rodina je systém množin, ve kterých jsou jedinými podskupinami s prázdnými průsečíky ty, které jsou párově disjunktní. Například uzavřené intervaly z reálná čísla tvoří rodinu Helly: pokud má rodina uzavřených intervalů prázdný průnik a je minimální (tj. žádná podrodina rodiny nemá prázdný průnik), musí být párově disjunktní.[7]

Nespojené svazky a oddíly

A oddíl sady X je libovolná kolekce vzájemně nesouvislých neprázdných sad, jejichž unie je X.[8] Každý oddíl lze ekvivalentně popsat pomocí vztah ekvivalence, a binární relace který popisuje, zda dva prvky patří do stejné sady v oddílu.[8]Disjunktní datové struktury[9] a upřesnění oddílu[10] 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í upřesnění, které rozdělují jednu sadu na dvě.

A disjunktní unie může znamenat jednu ze dvou věcí. Nejjednodušší to může znamenat spojení množin, které jsou disjunktní.[11] Pokud ale dvě nebo více sad již nejsou disjunktní, jejich disjunktní spojení může být vytvořeno úpravou sad tak, aby byly disjunktní před vytvořením spojení upravených sad.[12] 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.[13]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.[14]

Viz také

Reference

  1. ^ A b Halmos, P. R. (1960), Naivní teorie množin, Pregraduální texty z matematiky, Springer, str. 15, ISBN  9780387900926.
  2. ^ A b Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), Přechod k pokročilé matematice, Cengage Learning, str. 95, ISBN  978-0-495-56202-3.
  3. ^ Halbeisen, Lorenz J. (2011), Kombinatorická teorie množin: S jemným úvodem do vynucování Springerovy monografie z matematiky, Springer, s. 184, ISBN  9781447121732.
  4. ^ Copson, Edward Thomas (1988), Metrické prostory „Cambridge Tracts in Mathematics“, 57, Cambridge University Press, str. 62, ISBN  9780521357326.
  5. ^ Oberste-Vorth, Ralph W .; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Most k abstraktní matematice Učebnice MAA, Mathematical Association of America, s. 59, ISBN  9780883857793.
  6. ^ Viz odpovědi na otázku „Je prázdná rodina sad párově disjunktní?“
  7. ^ Bollobás, Béla (1986), Kombinatorika: Setové systémy, hypergrafy, rodiny vektorů a kombinatorická pravděpodobnost, Cambridge University Press, str. 82, ISBN  9780521337038.
  8. ^ A b Halmos (1960), str. 28.
  9. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „Kapitola 21: Datové struktury pro disjunktní sady“, Úvod do algoritmů (Druhé vydání), MIT Press, str. 498–524, ISBN  0-262-03293-7.
  10. ^ Paige, Robert; Tarjan, Robert E. (1987), „Algoritmy tří vylepšení oddílu“, SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, PAN  0917035.
  11. ^ Ferland, Kevin (2008), Diskrétní matematika: Úvod do důkazů a kombinatoriky, Cengage Learning, str. 45, ISBN  9780618415380.
  12. ^ Arbib, Michael A .; Kfoury, A. J .; Moll, Robert N. (1981), Základ pro teoretickou informatiku„Série AKM v Teoretické informatice: Texty a monografie v informatice, Springer-Verlag, str. 9, ISBN  9783540905738.
  13. ^ Monin, Jean François; Hinchey, Michael Gerard (2003), Porozumění formálním metodám, Springer, str. 21, ISBN  9781852332471.
  14. ^ Lee, John M. (2010), Úvod do topologických potrubí, Postgraduální texty z matematiky, 202 (2. vyd.), Springer, str. 64, ISBN  9781441979407.

externí odkazy