Relación conexa

En matemáticas, unha relación nun conxunto chámase conexa ou completa ou total se relaciona (ou "compara") todos os pares Modelo:Em de elementos do conxunto nunha dirección ou noutra, mentres que se chama fortemente conexa se relaciona Modelo:Em os pares de elementos. Como se describe a continuación na sección de terminoloxía, a terminoloxía destas propiedades non é uniforme.

A propiedade de conexa ocupa un lugar destacado na definición de ordes totais unha orde total (ou linear) é unha orde parcial na que dous elementos calquera son comparábeis; é dicir, a relación de orde é conexa. Do mesmo xeito, unha orde parcial estrita que é conexa é unha orde total estrita. Unha relación é unha orde total se e só se é unha orde parcial e a maiores é fortemente conexa. Unha relación é unha orde total estrita se, e só se, é unha orde parcial estrita e só conexa. Unha orde total estrita nunca pode ser fortemente conexa (agás nun dominio baleiro).

Esta noción de "relación total" debe distinguirse da propiedade de ser serial, que tamén se chama relación total.

Definición formal

Unha relación $R$ nun conxunto $X$ chámase Modelo:Em cando para todos os $x,y\in X,$

$\text{ se }x\ne y$ entón $xRy\text{ou}yRx,$

ou, de xeito equivalente, cando para todo $x,y\in X,$

$xRy\text{ou}yRx\text{ou}x=y.$

Unha relación coa propiedade que para todo $x,y\in X,$

$xRy\text{ou}yRx$

chámase Modelo:Em.

Terminoloxía

O uso principal da noción de relación conexa é no contexto das ordes, onde se usa para definir ordes totais ou lineares. Neste contexto, a propiedade moitas veces non se denomina especificamente. Pola contra, as ordes totais defínense como ordes parciais nas que dous elementos calquera son comparábeis. Así, Modelo:Em úsase de xeito máis xeral para relacións que son conexas ou fortemente conexas.

Porén, esta noción de "relación total" debe distinguirse da propiedade de ser serial, que tamén se chama total.

Seguindo con distintos nomes, ás veces as relacións conexas chámanse Modelo:Em, aínda que isto tamén pode levar a confusión: a relación universal tamén se denomina completa, e "completude" ten outros significados na teoría da orde.

As relacións conexas tamén se di que satisfán a Modelo:Em (aínda que a definición máis común de tricotomía é máis forte en que Modelo:Em das tres opcións $xRy,yRx,x=y$ debe cumprirse).

Cando as relacións consideradas non son ordes, ser conexo e ser fortemente conexo son propiedades moi diferentes. As fontes que definen ambas as dúas usan logo pares de termos como Modelo:Em e Modelo:Em, Modelo:Em e Modelo:Em, Modelo:Em e Modelo:Em, Modelo:Em e Modelo:Em, ou Modelo:Em e Modelo:Em, respectivamente, como nomes alternativos para as nocións de conexa e fortemente conexa como se definiu anteriormente.

Caracterizacións

Sexa $R$ unha relación homoxénea.

Para fórtemente conexa os seguintes enunciados son equivalentes:

• $R$ é fortemente conexa;
• $U\subseteq R\cup R^{\mathrm{\top }}$;
• $\bar{R}\subseteq R^{\mathrm{\top }}$;
• $\bar{R}$ é asimétrica,

onde $U$ é a relación universal e $R^{\mathrm{\top }}$ é a relación inversa de $R.$

Para só conexa os seguintes enunciados son equivalentes:

• $R$ é conexa;
• $\bar{I}\subseteq R\cup R^{\mathrm{\top }}$;
• $\bar{R}\subseteq R^{\mathrm{\top }}\cup I$;
• $\bar{R}$ é antisimétrica ,

onde $\bar{I}$ é a relación complementaria da relación identidade $I$ e $R^{\mathrm{\top }}$ é a relación inversa de $R.$

Propiedades

• A relación Modelo:Em $E$ dun grafo de torneo $G$ é sempre unha relación conexa no conxunto de vértices de $G$.
• Se unha relación fortemente conexa é simétrica, é a relación universal.
• Unha relación é fortemente conexa se, e só se, é conexa e reflexiva.
• Unha relación conexa nun conxunto $X$ non pode ser antitransitiva, sempre que $X$ ten polo menos 4 elementos. Nun conxunto de 3 elementos $\{a,b,c\},$ por exemplo, a relación $\{(a,b),(b,c),(c,a)\}$ ten as dúas propiedades.
• Se $R$ é unha relación conexa sobre $X,$ entón todos, ou todos menos un, os elementos de $X$ están no rango de $R.$ Do mesmo xeito, todos, ou todos menos un, os elementos de $X$ están no dominio de $R.$

Véxase tamén

Bibliografía

• Gunther Schmidt & Michael Winter (2018) Relational Topology
• C. Brink, W. Kahl, and G. Schmidt (1997) Relational Methods in Computer Science, Advances in Computer Science, page 5, Modelo:ISBN
• Gunther Schmidt & Thomas Strohlein (2012)[1987] Modelo:Google books

Outros artigos

• Orde total.
• Preorde.