Pré-ordem

Este artigo é sobre Relação Binária. Para Depth-first search, ver Pré-ordem (desambiguação).

Em matemática, uma pré-ordem é uma relação binária reflexiva e transitiva. Toda ordem parcial ou relação de equivalência é também uma pré-ordem.

Para toda pré-ordem há um grafo direto relacionado, com elementos do conjunto de vértices e com a relação de ordem dos pares de elementos correspondendo à direção dos arcos.

Definição Formal

Seja A um conjunto e R uma relação binária sobre A (ou seja, R subconjunto de AxA). Então, R é uma pré-ordem se, e somente se, R é reflexiva e transitiva. Isto é:

$\forall a\in A(aRa)$ (propriedade reflexiva)

$\forall (a,b)\in AxA(aRb\ \land bRc\ \ \Rightarrow aRc)$ (propriedade transitiva)

Exemplos

• Sobre os arcos de um grafo orientado (também conhecido por digrafo), a relação ser acessível por é uma pr[e-ordem. Se o digrafo é acíclico, essa relação vira uma ordem.
• Em um anel comutativo, a relação divide é uma pré-ordem.

Ver também

• Relação de ordem - pré-ordem que é também anti-simétrica.
• Relação de equivalência - pré-ordem que é também uma relação simétrica.
• Ordem total - pré-ordem que é também total e anti-simétrica.
• Lema de Newman