4.1: Preludio a Sistemas de Representantes Distintos

Última actualización
Guardar como PDF

Page ID: 117116

\( \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}}\)

Supongamos que los clubes estudiantiles de un colegio envían cada uno un representante al gobierno estudiantil de entre los miembros del club. Ninguna persona podrá representar a más de un club; ¿es esto posible? Ciertamente es posible a veces, por ejemplo cuando ningún estudiante pertenece a dos clubes. No es difícil ver que podría ser imposible. Entonces la primera pregunta sustantiva es: ¿hay algo útil o interesante que podamos decir sobre en qué condiciones es posible elegir a dichos representantes?

Convertimos esto en una situación más matemática:

Definición\(\PageIndex{1}\): System of Distinct Representatives (SDR)

Supongamos que\(A_1,A_2,\ldots,A_n\) son conjuntos, a los que nos referimos como un sistema de conjuntos. Un sistema (completo) de representantes distintos es un conjunto\(\{x_1, x_2, \ldots x_n\}\) tal que\(x_i\in A_i\) para todos\(i\), y ninguno de los dos\(x_i\) son iguales. Un sistema (parcial) de distintos representantes es un conjunto de elementos distintos\(\{x_1, x_2, \ldots x_k\}\) tales que\(x_i\in A_{j_i}\), donde\(j_1,j_2,\ldots,j_k\) son enteros distintos en\([n]\).

En el uso estándar, “sistema de representantes distintos” significa “sistema completo de representantes distintos”, pero será conveniente dejar que “sistema de representantes distintos” signifique un sistema completo o parcial de representantes distintos dependiendo del contexto. Por lo general abreviamos “sistema de representantes distintos” como sdr.

Analizaremos este problema de dos maneras: combinatorialmente y usando teoría gráfica.

Colaboradores y Atribuciones

Template:ContribGuichard