18.5: Gráfica para una relación de equivalencia

Última actualización
Guardar como PDF

Page ID: 118276

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Dada una relación de equivalencia sobre un conjunto finito\(A\text{,}\) ¿qué observaremos si dibujamos la gráfica de la relación?

Dado que una relación de equivalencia es reflexiva, también podríamos omitir los bucles en cada nodo.
Dado que una relación de equivalencia es simétrica, también podríamos reemplazar los pares de flechas entre cada par de nodos relacionados con un solo borde, convirtiendo la gráfica dirigida en una gráfica ordinaria.
Dado que una relación de equivalencia divide un conjunto en una unión disjunta de clases de equivalencia (Teorema 18.3.1), se desconectará la gráfica de una relación de equivalencia, representando cada componente conectado una clase de equivalencia específica.
Dado que cada elemento en una clase de equivalencia es equivalente a cualquier otro elemento de la clase (Declaración 2 de la Proposición 18.3.1), cada componente conectado en la gráfica estará completo.

Ejemplo\(\PageIndex{1}\): Graph of the “same cardinality” equivalence relation.

Dejar\(A = \{a,b,c,d\}\text{,}\) y dejar\(\mathord{\equiv}\) ser la relación de equivalencia en\(\mathscr{P}(A)\) definida por\(B \equiv B'\) si Es\(\vert B \vert = \vert B' \vert \text{.}\) decir, dos subconjuntos de se\(A\) considerarán equivalentes si contienen el mismo número de elementos. La figura\(\PageIndex{1}\) contiene la gráfica para\(\mathord{\equiv}\text{,}\) con bucles reflexivos y flechas bidireccionales simétricas omitidas.

Figura\(\PageIndex{1}\): Gráfica de equivalencia de cardinalidad en un conjunto de potencias.