Zestawy rozłączne - Disjoint sets

Dwa rozłączne zestawy.

W matematyce mówi się, że dwa zbiory są zbiorami rozłącznymi, jeśli nie mają wspólnego elementu . Równoważnie dwa rozłączne zbiory to zbiory, których przecięcie jest zbiorem pustym . Na przykład {1, 2, 3} i {4, 5, 6} są zbiorami rozłącznymi, podczas gdy {1, 2, 3} i {3, 4, 5} nie są rozłączne. Zbiór składający się z więcej niż dwóch zestawów jest nazywany rozłącznym, jeśli jakiekolwiek dwa różne zestawy zbioru są rozłączne.

Uogólnienia

Rozłączny zbiór zestawów

Ta definicja zbiorów rozłącznych może być rozszerzona na rodzinę zbiorów : rodzina jest parami rozłącznymi lub rozłącznymi, jeśli kiedykolwiek . Alternatywnie, niektórzy autorzy używają terminu rozłączny również w odniesieniu do tego pojęcia. ${\ Displaystyle (A_ {i}) _ {i \ w I}}$${\ Displaystyle A_ {i} \ czapka A_ {j} = \ varnothing}$${\displaystyle i\neqj}$

W przypadku rodzin pojęcie parami rozłączne lub wzajemnie rozłączne jest czasami definiowane w nieco inny sposób, w którym dozwolone są powtarzające się identyczne elementy: rodzina jest rozłączna parami, jeśli kiedykolwiek (każde dwa odrębne zbiory w rodzinie są rozłączne). Na przykład zbiór zbiorów {{0,1,2}, {3,4,5}, {6,7,8}, ... } jest rozłączny, podobnie jak zbiór {...−2 ,0,2,4,...}, {...−3,−1,1,3,5 }} dwóch klas parzystości liczb całkowitych; rodzina składająca się z 10 członków nie jest rozłączna (ponieważ klasy liczb parzystych i nieparzystych występują po pięć razy), ale zgodnie z tą definicją jest rozłączna parami (ponieważ jeden otrzymuje niepuste przecięcie dwóch członków tylko wtedy, gdy są one ta sama klasa). ${\ Displaystyle A_ {i} \ czapka A_ {j} = \ varnothing}$${\ Displaystyle A_ {i} \ neq A_ {j}}$${\ Displaystyle (\ {n + 2 k \ średni k \ w \ mathbb {Z} \}) _ {n \ w \ {0,1, \ ldots, 9 \}}}$

Mówi się, że dwa zbiory są zbiorami prawie rozłącznymi, jeśli ich przecięcie jest w pewnym sensie małe. Na przykład o dwóch zbiorach nieskończonych, których przecięcie jest zbiorem skończonym, można powiedzieć, że są prawie rozłączne.

W topologii istnieją różne pojęcia zbiorów rozdzielonych z bardziej ścisłymi warunkami niż rozłączność. Na przykład dwa zbiory można uznać za rozdzielone, jeśli mają rozłączne domknięcia lub rozłączne sąsiedztwo . Podobnie w przestrzeni metrycznej , korzystnie oddzielne zestawy są zestawy oddzielone niezerowej odległości .

Skrzyżowania

Rozłączność dwóch zbiorów lub rodziny zbiorów może być wyrażona jako przecięcia ich par.

Dwa zbiory A i B są rozłączne wtedy i tylko wtedy, gdy ich przecięcie jest zbiorem pustym . Z tej definicji wynika, że ​​każdy zbiór jest rozłączny od zbioru pustego i że zbiór pusty jest jedynym zbiorem rozłącznym od siebie. ${\ Displaystyle A \ czapka B}$

Jeśli kolekcja zawiera co najmniej dwa zestawy, warunek, że kolekcja jest rozłączna, oznacza, że ​​przecięcie całej kolekcji jest puste. Jednak zbiór zbiorów może mieć puste przecięcie, ale nie jest rozłączny. Dodatkowo, podczas gdy zbiór mniej niż dwóch zbiorów jest trywialnie rozłączny, ponieważ nie ma par do porównania, przecięcie zbioru jednego zbioru jest równe zbiorowi, który może być niepusty. Na przykład trzy zbiory { {1, 2}, {2, 3}, {1, 3} } mają puste przecięcie, ale nie są rozłączne. W rzeczywistości w tej kolekcji nie ma dwóch rozłącznych zestawów. Również pusta rodzina zbiorów jest parami rozłączna.

Rodzina Helly to system zbiorów, w którym jedynymi podrodzinami z pustymi przecięciami są te, które są parami rozłączne. Na przykład, zamknięte przedziały tych liczb rzeczywistych tworzą rodzinę Helly: jeśli rodzina zamkniętych przedziałach ma pusty przecięcia i jest minimalny (tj nie podrodziny rodziny posiada pusty przecięcia), musi on być parami rozłączne.

Rozłączne związki i przegrody

Rozbicie zbioru X oznacza dowolny zbiór wzajemnie rozłącznych niepusty zestawów których związek jest X . Każda partycja może być równoważnie opisać za pomocą relacji równoważności , o binarnej relacji , który opisuje, czy dwa elementy należą do tego samego zestawu w partycji. Struktury danych o rozłącznym zbiorze i udokładnianie partycji to dwie techniki w informatyce służące do efektywnego utrzymywania partycji zestawu, odpowiednio, w wyniku operacji łączenia, które łączą dwa zestawy lub operacji uszczegóławiania, które dzielą jeden zestaw na dwa.

Unia rozłączne może oznaczać jedną z dwóch rzeczy. Najprościej może to oznaczać połączenie zbiorów, które są rozłączne. Ale jeśli dwa lub więcej zbiorów nie jest już rozłącznych, ich rozłączną sumę można utworzyć poprzez modyfikację zbiorów, aby uczynić je rozłącznymi przed utworzeniem sumy zmodyfikowanych zbiorów. Na przykład dwa zestawy można rozłączyć przez zastąpienie każdego elementu uporządkowaną parą elementów i wartością binarną wskazującą, czy należy on do pierwszego, czy do drugiego zestawu. W przypadku rodzin składających się z więcej niż dwóch zestawów można podobnie zastąpić każdy element uporządkowaną parą elementu i indeksem zestawu, który go zawiera.

Zobacz też

• Twierdzenie o separacji hiperpłaszczyzn dla rozłącznych zbiorów wypukłych
• Zdarzeń wzajemnie wykluczających
• Względnie pierwsze , liczby z rozłącznymi zbiorami dzielników pierwszych
• Separoid
• Pakowanie zbiorów, problem znalezienia największej rozłącznej podrodziny rodziny zbiorów

Bibliografia

Linki zewnętrzne

• Weisstein, Eric W. „Zbiory rozłączne” . MatematykaŚwiat .