UFPE - CIn - Matemática Discreta - if670
Representando relações: matrizes
Representação usando matrizes
Matriz de bits;
Identificando as propriedades;
Operações de união, interseção e complemento;
Composição: MS◦R = MR MS (Produto booleano)
logo-ufpe
1/7
UFPE - CIn - Matemática Discreta - if670
Representando relações: matrizes
Representação usando matrizes
Matriz de bits;
Identificando as propriedades;
Operações de união, interseção e complemento;
Composição: MS◦R = MR MS (Produto booleano)
logo-ufpe
1/7
UFPE - CIn - Matemática Discreta - if670
Representando relações: matrizes
Representação usando matrizes
Matriz de bits;
Identificando as propriedades;
Operações de união, interseção e complemento;
Composição: MS◦R = MR MS (Produto booleano)
logo-ufpe
1/7
UFPE - CIn - Matemática Discreta - if670
Representando relações: matrizes
Representação usando matrizes
Matriz de bits;
Identificando as propriedades;
Operações de união, interseção e complemento;
Composição: MS◦R = MR MS (Produto booleano)
logo-ufpe
1/7
UFPE - CIn - Matemática Discreta - if670
Representando relações: grafos
Representação usando digrafos
Definição
Um grafo direcionado ou digrafo, consiste de um conjunto V de
vértices (ou nós ) juntamente com um conjunto E de pares
ordenados de elementos de V chamados de arestas (ou arcos
). O vértice a é chamado vértice inicial da aresta (a, b), e o
vértice b é chamado de vértice final ou terminal dessa aresta.
A aresta da forma (a, a) é chamada de loop.
Identificando as propriedades.
logo-ufpe
2/7
UFPE - CIn - Matemática Discreta - if670
Representando relações: grafos
Representação usando digrafos
Definição
Um grafo direcionado ou digrafo, consiste de um conjunto V de
vértices (ou nós ) juntamente com um conjunto E de pares
ordenados de elementos de V chamados de arestas (ou arcos
). O vértice a é chamado vértice inicial da aresta (a, b), e o
vértice b é chamado de vértice final ou terminal dessa aresta.
A aresta da forma (a, a) é chamada de loop.
Identificando as propriedades.
logo-ufpe
2/7
UFPE - CIn - Matemática Discreta - if670
Representando relações: grafos
Representação usando digrafos
Definição
Um grafo direcionado ou digrafo, consiste de um conjunto V de
vértices (ou nós ) juntamente com um conjunto E de pares
ordenados de elementos de V chamados de arestas (ou arcos
). O vértice a é chamado vértice inicial da aresta (a, b), e o
vértice b é chamado de vértice final ou terminal dessa aresta.
A aresta da forma (a, a) é chamada de loop.
Identificando as propriedades.
logo-ufpe
2/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Seja R uma relação em A
Fecho reflexivo de R = R ∪ ∆,
onde ∆ = {(a, a)|a ∈ A} (relação diagonal em A);
Fecho simétrico de R = R ∪ R −1
logo-ufpe
3/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Seja R uma relação em A
Fecho reflexivo de R = R ∪ ∆,
onde ∆ = {(a, a)|a ∈ A} (relação diagonal em A);
Fecho simétrico de R = R ∪ R −1
logo-ufpe
3/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Caminho em um digrafo
Definição
Um caminho de a para b em um digrafo G é uma sequência de
uma ou mais arestas (x0 , x1 ), (x1 , x2 ), . . . (xn−1 , xn ) em G, onde
x0 = a e xn = b, ou seja, existe uma sequência de arestas
onde i vértice final de uma aresta é o mesmo vértice inicial da
próxima aresta do caminho. Esse caminho é denotado por
x0 , x1 , . . . xn−1 , xn e possui tamanho n. Um caminho que
começa e termina no mesmo vértice é chamado de circuito ou
ciclo.
Caminho e Relação: existe um caminho de a para b em
uma relação R se existe uma sequência de elementos
a, x1 , x2 , . . . xn−1 , b com (a, x1 ) ∈ R, (x1 , x2 ) ∈ R, . . . , e
(xn−1 , b) ∈ R.
logo-ufpe
4/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Caminho em um digrafo
Definição
Um caminho de a para b em um digrafo G é uma sequência de
uma ou mais arestas (x0 , x1 ), (x1 , x2 ), . . . (xn−1 , xn ) em G, onde
x0 = a e xn = b, ou seja, existe uma sequência de arestas
onde i vértice final de uma aresta é o mesmo vértice inicial da
próxima aresta do caminho. Esse caminho é denotado por
x0 , x1 , . . . xn−1 , xn e possui tamanho n. Um caminho que
começa e termina no mesmo vértice é chamado de circuito ou
ciclo.
Caminho e Relação: existe um caminho de a para b em
uma relação R se existe uma sequência de elementos
a, x1 , x2 , . . . xn−1 , b com (a, x1 ) ∈ R, (x1 , x2 ) ∈ R, . . . , e
(xn−1 , b) ∈ R.
logo-ufpe
4/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
O seguinte teorema pode ser obtido da definição de um
caminho em uma relação.
Teorema
Seja R uma relação em um conjunto A. Existe um caminho de
tamanho n de a para b se e somente se (a, b) ∈ R n .
logo-ufpe
5/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Fecho transitivo
Definição
Seja R uma relação em um conjunto A. A relação de
conectividade R ∗ consiste dos pares (a, b) de forma que existe
um caminho de a para b em R.
Observe que R ∗ = R ∪ R 2 ∪ R 3 . . .
Teorema
O fecho transitivo de R é igual à relação de conectividade.
logo-ufpe
6/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Fecho transitivo
Definição
Seja R uma relação em um conjunto A. A relação de
conectividade R ∗ consiste dos pares (a, b) de forma que existe
um caminho de a para b em R.
Observe que R ∗ = R ∪ R 2 ∪ R 3 . . .
Teorema
O fecho transitivo de R é igual à relação de conectividade.
logo-ufpe
6/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Fecho transitivo
Definição
Seja R uma relação em um conjunto A. A relação de
conectividade R ∗ consiste dos pares (a, b) de forma que existe
um caminho de a para b em R.
Observe que R ∗ = R ∪ R 2 ∪ R 3 . . .
Teorema
O fecho transitivo de R é igual à relação de conectividade.
logo-ufpe
6/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Lema
Seja A um conjunto com n elementos, e seja R uma relação
em A. Se existe um caminho em R de a para b, então esse
caminho não é maior que n. Adicionalmente, quando a 6= b, se
existe um caminho em R de a para b, então o tamanho desse
caminho não é maior que n − 1.
Por esse lema, vemos que o fecho transitivo de R é igual a
R ∪ R2 ∪ R3 ∪ . . . ∪ Rn.
Teorema
Seja MR a matriz de bits que representa a relação R em um
conjunto com n elementos. Então, a matriz de bits do fecho
transitivo R ∗ de R é
MR ∗ = MR ∨ MR 2 ∨ MR 3 ∨ . . . ∨ MR n
logo-ufpe
7/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Lema
Seja A um conjunto com n elementos, e seja R uma relação
em A. Se existe um caminho em R de a para b, então esse
caminho não é maior que n. Adicionalmente, quando a 6= b, se
existe um caminho em R de a para b, então o tamanho desse
caminho não é maior que n − 1.
Por esse lema, vemos que o fecho transitivo de R é igual a
R ∪ R2 ∪ R3 ∪ . . . ∪ Rn.
Teorema
Seja MR a matriz de bits que representa a relação R em um
conjunto com n elementos. Então, a matriz de bits do fecho
transitivo R ∗ de R é
MR ∗ = MR ∨ MR 2 ∨ MR 3 ∨ . . . ∨ MR n
logo-ufpe
7/7
UFPE - CIn - Matemática Discreta - if670
Fechos de uma relação
Lema
Seja A um conjunto com n elementos, e seja R uma relação
em A. Se existe um caminho em R de a para b, então esse
caminho não é maior que n. Adicionalmente, quando a 6= b, se
existe um caminho em R de a para b, então o tamanho desse
caminho não é maior que n − 1.
Por esse lema, vemos que o fecho transitivo de R é igual a
R ∪ R2 ∪ R3 ∪ . . . ∪ Rn.
Teorema
Seja MR a matriz de bits que representa a relação R em um
conjunto com n elementos. Então, a matriz de bits do fecho
transitivo R ∗ de R é
MR ∗ = MR ∨ MR 2 ∨ MR 3 ∨ . . . ∨ MR n
logo-ufpe
7/7