Relação binária: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m tradução de partes do artigo em inglês, checagem de fontes e inserção de novas fontes. |
Funcionalidade de sugestões de hiperligações: 3 hiperligações adicionadas. |
||
Linha 41:
=== Grafos ===
O '''grafo''' é um ramo importante da [[matemática discreta]] (ver [[Teoria dos grafos]]). Podemos observar os grafos de maneira clara a partir de endorrelações. Dessa maneira, toda relação R: A <math>\longrightarrow</math> A pode ser representada como um grafo com arestas ligando cada par ordenado '''(a,b)''' com origem em '''a''' destino em '''b'''. Assim:
* Cada elemento do conjunto A é representado por um vértice do grafo.
Linha 142:
Formalmente, a relação ''R'' é dita reflexiva se ''aRa'' para todo ''a'' ∈ ''A'', isto é, se (a,a) ∈ ''R'' para todo ''a'' ∈ ''A''.
Em um [[conjunto finito]] com ''n'' elementos existem 2<sup>n²</sup> relações binárias, das quais 2<sup>n²-n</sup> são reflexivas.
A matriz de uma relação reflexiva: a diagonal principal contém somente o valor verdadeiro (1). Grafo de uma relação reflexiva: em cada vértice do grafo deve haver um laço, Na matriz de uma relação irreflexiva a diagonal principal contém apenas o valor falso (0). Grafo de uma relação irreflexiva: em nenhum vértice do grafo pode haver um laço.
Linha 188:
A propriedade de transitividade também pode ser expressa em termos da composição de relações. Para uma relação ''R'' em ''A'', definimos ''R''² = ''R⋅R'' e, mais geralmente, ''R''<sup>n</sup> = ''R<sup>n-1</sup>⋅R''.
'''Teorema''': a relação ''R'' é transitiva [[se e somente se]] , ''R''<sup>n</sup> ⊆ ''R'' para ''n'' ≥ 1. Ou 1<n.
Uma matriz de uma relação transitiva: matricialmente não se verifica nenhuma estrutura específica. Grafo de uma relação transitiva: sempre que uma aresta ligar um vértice A a um vértice B e o vértice B a um vértice C, então deve haver uma aresta de A para C.
| |||