14. Relaciones de orden parcial

14.1 Introducción

En muchos problemas necesitamos ordenar elementos, pero no siempre todos pueden compararse entre sí. Por ejemplo, dos tareas pueden depender de una tercera, pero no tener una relación directa entre ellas.

Para esos casos usamos una relación de orden parcial. Esta relación establece una estructura de comparación sin exigir que cada par de elementos sea comparable.

14.2 Definición

Una relación R sobre un conjunto A es una relación de orden parcial si cumple tres propiedades:

• Reflexiva: todo elemento está relacionado consigo mismo.
• Antisimétrica: no hay ida y vuelta entre elementos distintos.
• Transitiva: si un elemento se relaciona con un segundo y el segundo con un tercero, entonces el primero se relaciona con el tercero.

14.3 Ejemplo con menor o igual

La relación ≤ sobre números es un orden parcial. De hecho, también es un orden total, pero cumple todas las condiciones de orden parcial.

14.4 Ejemplo con subconjuntos

La relación “ser subconjunto de” también es un orden parcial. Si tenemos varios conjuntos, algunos pueden compararse por inclusión y otros no.

Los conjuntos {1} y {2} no son comparables por inclusión: ninguno contiene al otro.

14.5 Elementos comparables e incomparables

En un orden parcial, dos elementos a y b son comparables si se cumple a R b o b R a. Si no se cumple ninguna de las dos, son incomparables.

14.6 Ejemplo con dependencias de tareas

Una relación de precedencia entre tareas puede ser un orden parcial. Si una tarea debe realizarse antes que otra, se establece una comparación.

Documentación puede ser independiente de Interfaz. En ese caso, no todas las tareas son comparables entre sí.

14.7 Orden parcial en JavaScript

Podemos representar una relación de orden parcial con una lista de pares ordenados. El siguiente ejemplo usa tareas y precedencia.

const tareas = ["Diseño", "API", "Interfaz"];

const precedeOIgual = [
  ["Diseño", "Diseño"],
  ["API", "API"],
  ["Interfaz", "Interfaz"],
  ["Diseño", "API"],
  ["API", "Interfaz"],
  ["Diseño", "Interfaz"]
];

console.log(precedeOIgual);

Incluimos los pares reflexivos porque un orden parcial debe ser reflexivo.

14.8 Verificar si una relación es orden parcial

Para verificar un orden parcial debemos comprobar reflexividad, antisimetría y transitividad.

function contienePar(relacion, a, b) {
  return relacion.some(([x, y]) => x === a && y === b);
}

function esReflexiva(conjunto, relacion) {
  return conjunto.every(a => contienePar(relacion, a, a));
}

function esAntisimetrica(relacion) {
  return relacion.every(([a, b]) => {
    return a === b || !contienePar(relacion, b, a);
  });
}

function esTransitiva(relacion) {
  for (const [a, b] of relacion) {
    for (const [c, d] of relacion) {
      if (b === c && !contienePar(relacion, a, d)) {
        return false;
      }
    }
  }
  return true;
}

function esOrdenParcial(conjunto, relacion) {
  return esReflexiva(conjunto, relacion)
    && esAntisimetrica(relacion)
    && esTransitiva(relacion);
}

14.9 Comprobar el ejemplo

Usamos las funciones anteriores para comprobar que la relación de precedencia cumple las propiedades de orden parcial.

const tareas = ["Diseño", "API", "Interfaz"];

const relacion = [
  ["Diseño", "Diseño"],
  ["API", "API"],
  ["Interfaz", "Interfaz"],
  ["Diseño", "API"],
  ["API", "Interfaz"],
  ["Diseño", "Interfaz"]
];

function contienePar(relacion, a, b) {
  return relacion.some(([x, y]) => x === a && y === b);
}

function esOrdenParcial(conjunto, relacion) {
  const reflexiva = conjunto.every(a => contienePar(relacion, a, a));
  const antisimetrica = relacion.every(([a, b]) => a === b || !contienePar(relacion, b, a));

  let transitiva = true;
  for (const [a, b] of relacion) {
    for (const [c, d] of relacion) {
      if (b === c && !contienePar(relacion, a, d)) {
        transitiva = false;
      }
    }
  }

  return reflexiva && antisimetrica && transitiva;
}

console.log(esOrdenParcial(tareas, relacion));

14.10 Diferencia con equivalencia

Una relación de equivalencia agrupa elementos. Una relación de orden parcial compara elementos. Por eso sus propiedades son distintas.

14.11 Aplicaciones en programación

• Ordenar tareas con dependencias.
• Modelar jerarquías de tipos o permisos.
• Representar inclusión entre conjuntos de características.
• Analizar dependencias entre módulos de software.
• Definir prioridades donde algunos elementos no son comparables.
• Preparar estructuras para diagramas de Hasse y ordenamientos topológicos.

14.12 Errores comunes

• Creer que un orden parcial debe comparar todos los elementos.
• Olvidar los pares reflexivos.
• Confundir antisimetría con asimetría.
• Omitir pares transitivos necesarios.
• Usar una relación con ciclos entre elementos distintos y llamarla orden parcial.

14.13 Qué debes recordar de este tema

• Un orden parcial debe ser reflexivo, antisimétrico y transitivo.
• En un orden parcial, no todos los elementos tienen que ser comparables.
• Los pares reflexivos son obligatorios.
• La antisimetría evita ciclos de ida y vuelta entre elementos distintos.
• La transitividad exige que las comparaciones encadenadas tengan su comparación directa.
• Los órdenes parciales son útiles para dependencias, jerarquías y subconjuntos.

14.14 Conclusión

Las relaciones de orden parcial permiten representar comparaciones incompletas pero coherentes. Son esenciales cuando algunos elementos pueden ordenarse y otros no tienen relación directa.

En el próximo tema veremos relaciones de orden total, donde todos los pares de elementos sí deben ser comparables.