Entenda a equivalência entre grafos, relações binárias e matrizes booleanas, e como analisar a acessibilidade entre nós.
1. Equivalência entre grafos direcionados, relações binárias e matrizes booleanas
Um grafo direcionado G = (V, A) sem arcos paralelos pode ser representado por uma relação de adjacência \(R \subseteq V \times V\) onde \( (v_i , v_j) \in R\) se e somente se existe um arco de v_i para v_j. Essa relação pode ser codificada em uma matriz booleana M de ordem \( |V| \):
0 1 1 0
0 0 0 0
0 0 1 0
1 1 1 0
Essa matriz contém apenas 0 e 1, portanto é booleana.
2. Propriedades de relações binárias e sua interpretação no grafo e na matriz
3. Acessibilidade e fecho transitivo
Um vértice v_j é acessível a partir de v_i se existe algum caminho (de qualquer comprimento) de v_i para v_j. A relação de acessibilidade é exatamente o fecho transitivo da relação de adjacência.
Para obter o fecho transitivo usando matrizes booleanas, calcula‑se \(M^{*}=M \lor M^{2} \lor \dots \lor M^{n}\), onde \(n=|V|\) e a soma é a operação OR (disjunção) entre matrizes. Cada potência \(M^{k}\) indica a existência de caminhos de comprimento k.
Exemplo de cálculo
Considere a matriz de adjacência acima (M). Calculamos \(M^{2}\) usando multiplicação booleana (AND + OR). O resultado mostra novos pares de vértices conectados por caminhos de comprimento 2. Repetindo até M^{4 (n=4) e fazendo a OR de todas as potências, obtemos a matriz de acessibilidade R:
1 1 1 0
0 0 0 0
0 0 1 0
1 1 1 0
Assim, 2 não alcança nenhum outro vértice, enquanto 1 alcança 1,2,3.
Dicas
1. Equivalência entre grafos direcionados, relações binárias e matrizes booleanas
• Cada arco corresponde a um par ordenado da relação; a matriz booleana registra esses pares.
2. Propriedades das relações binárias
2.1 Reflexividade – laços e 1 na diagonal.
2.2 Simetria – arcos bidirecionais e matriz simétrica.
2.3 Transitividade – caminhos de comprimento 2 implicam arco direto.
3. Acessibilidade
3.1 Definição – existência de caminho de qualquer comprimento.
3.2 Fecho transitivo – união de todas as potências da matriz de adjacência.
3.3 Cálculo – multiplicação booleana + operação OR.
Resposta correta: A)
Os 1 nas posições (1,2), (2,3) e (3,3) indicam exatamente os arcos solicitados.
Resposta correta: B)
Para \(M^{2}_{13}\) calculamos \(\bigvee_{k=1}^{3}(M_{1k}\land M_{k3}) = (0\land0)\lor(1\land1)\lor(0\land0)=1\).
Resposta correta: C)
O fecho transitivo contém todas as pares (v_i , v_j) para os quais existe algum caminho, ou seja, a definição de acessibilidade.
Resposta correta: A)
O grafo forma um ciclo que permite alcançar qualquer vértice a partir de qualquer outro; portanto, todas as entradas são 1.
Olá, alunas e alunos do curso de Fundamentos Matemáticos para a convitação.
Nesta videoaula, eu vou falar de gráficos direcionados, relações, binários e acessibilidade.
Então, eu vou começar estabelecendo uma equivalência no contexto de gráficos direcionados com as relações binárias e com as matrices oleanas.
Em seguida, vamos explorar isso considerando a acessibilidade entre nós num gráfico.
Bom, vamos assumir aqui gráficos direcionados que não possuam arcos paralelos e não tenham pesos associados a eles.
Isso significa que, num gráfico direcionado, isso aqui, essa relação a diaprabi e de vibrar, não representaria arcos paralelos e eles não são paralelos.
Então, isso pode acontecer.
Por outro lado, essa situação não pode não estar sendo considerada onde a extremidade inicial e a extremidade final dos arcos são idênticas.
Então, aqui nós temos arcos paralelos.
Bom, a matriz num gráfico direcionado, uma atriz de adjacência, ela não necessariamente vai ser semérica.
E se nós pensarmos que nós estamos considerando arcos paralelos, nós vamos cair numa matriz de adjacência que vai ter como elementos apenas zeros e um's, o que nos remete as matrices baleanas.
Bom, então, dado uma matriz baleana, nós sempre podemos reconstruir a partir dela o gráfico direcionado que está armazenado naquela repor representada naquela matriz.
Então, isso vai ser possível considerando, vai ser possível fazer essa reconstrução do gráfico a partir dessa matriz baleana e vamos ter um gráfico que não possui arcos paralelos pelo que já foi mencionado.
Dessa maneira, os gráficos direcionados com N e Nose sem arcos paralelos têm uma representação em matriz baleanas, em forma de matriz baleanas.
E a partir de uma matriz baleana, nós conseguimos representar gráficos direcionados sem arcos paralelos.
Bom, isto, hoje, vamos brincar um pouquinho aqui, nós temos esse gráfico direcionado sem arcos paralelos e a sua representação matricial.
Na verdade, a representação aqui de somatriz, de adjacência, que, como podemos ver, é uma matriz baleana, porrada apenas por zero e uns, onde a relação, por exemplo, que nós temos um arco ligando o N-O-2 está aqui representada, a mesma forma do N-O-3.
Esse laço também está aqui representado, o N-3 ligado a ele mesmo, por essa entrada 1 aqui.
Bom, é, é, é, é interessante notar aqui que, por conta das direções dos gráficos, o N-O-2, ele não, nós não temos arcos saindo do N-O-2 para os demais nós deste gráfico.
Então, se nós consideramos um gráfico direcionado com N e Nose sem arcos paralelos, nós podemos definir a relação de adjacência do gráfico g, através dessa relação binária, entre o N-O e o N-J, dizendo que existe um arco, N-G de N-I para N-J, levando o N-I para N-J.
Então, aqui nós temos uma relação de adjacência para um gráfico, onde podemos representar isso, né, que construir esse gráfico da seguinte forma, nós temos o arco que vai de 1 para 2, de 1 para 3, de 3 para ele mesmo, de 4 para 1, 4 para 2 e 4 para 3.
Então, tudo esse gráfico é reconstruído a partir desta relação de adjacência estabelecida para o gráfico, que é uma relação binária.
Bom, dessa forma nós vamos também dar um gráfico poder inferir a relação binária.
Então, nós temos aqui o contexto de um gráfico com 4 N, onde podemos estabelecer a relação binária, que é uma relação que vai de 1 para 4, de 2 para 3, de 2 para 4 e do N-4 para o N-1.
Bom, então lembre-se que acabamos de mostrar uma equivalência também entre esse gráfico entre gráficos direcionados com N e nós, e sem arcos paralelos e relações binárias em conjuntos com N elementos, acabamos de ver isso.
E como já tínhamos estabelecido uma relação também de gráficos direcionados, uma relação de equivalência, de gráficos direcionados com N e nós, e sem arcos paralelos com as matrices moleanas.
Então, nós completamos aqui que o gráfico com essa propriedade, a gente vai conseguir ter uma relação de equivalência, uma relação binária estabelecida entre os elementos e de uma relação binária estabelecida entre os elementos.
Podemos inferir esse gráfico e, além disso da relação binária, podemos inferir a matriz moleana como da matriz moleana podemos inferir essa relação binária e o gráfico.
Bom, então aqui temos um exemplo, a partir de uma relação binária, podemos construir a matriz moleana equivalente.
Então, temos aqui um no-on com uma relação que vai de um no-on, relacionando no-on com o N-4, e isso vai aparecer aqui nessa linha, certo? O mesmo se aplica para as demais relações entre nós aqui estabelecidos.
Bom, dessa maneira, se uma relação binária e um conjunto N tive determinadas propriedades, por exemplo, semitria, reflexividade, isso vai se refletir na estrutura do gráfico e na matriz moleana que corresponde a esse gráfico.
Então, da mesma maneira, determinadas características que estão relacionadas na matriz moleana ou representadas no gráfico dessa matriz, vão também aparecer nas relações de adjacência correspondente.
Bom, dessa forma, vamos recordar que temos as propriedades de reflexividade, semitria, antes de semitria e transitividade em uma relação binária, né? Então, a hora de a gente ver como as ideias que foram apresentadas durante o curso, elas vão se encaixando.
E nós vamos ver o uso disso aqui no estrutura em gráfico.
Então, se nós tivermos, por exemplo, uma relação boa, que é uma relação reflexiva, né? Nós sabemos, então que o NOIN se relaciona com NOIN e com ele mesmo.
Isso aparece no gráfico na forma de um lasso, em cada nó, da mesma maneira, se estamos retratando uma relação binária que contém a propriedade de ser reflexiva, além da gente ter esse lasso, isso vai aparecer na representação do gráfico, a gente vai ter o que, uma matriz boleana com valores iguais na 1 de agonal principal, justamente para descrever esse lasso, justamente para descrever essa propriedade, né? Para imaginar essa propriedade da reflexividade.
Dessa forma, se lembrando agora do conceito do diagrama de raza, nós podemos enxergar esse diagrama no contexto da ordem parcial, considerando uma direcionamento que vai de baixo para cima, nós vamos ter a reflexividade representada através de laços, né? As ligações entre os nós, quando eu me ensinei de baixo para cima, representada através dos direcionamentos, então, um para dois, um para três, três para seis, dois para seis, a reflexividade aqui através do laço, e a partir daí, podemos inferir a transitividade.
Então, por exemplo, temos aqui, no caso, de um para três, de três para seis, de seis para dois, de 18, a inferência de um para seis, de um para doze, de um para 18, de três para doze e três para 18, que fica bastante claro que faz desse direcionamento dos gráficos e onde podemos inferir.
Então, há propriedade de transitividade.
Então, essa, a partir do diagrama, nós conseguimos estabelecer uma representação mais robusta, né? Uma reconstrução das propriedades através do gráfico direcionado.
E a partir daquele gráfico, podemos estabelecer a matriz baleana para representar estas gerações.
Bom, tá, mas onde isso tudo nos leva? Isso nos leva à acessibilidade.
Então, considere um gravo direcionado o NONJ será acessível a partir do NON e se existiu o caminho de NI para NJ.
Então, por exemplo, o NON3 é acessível a partir do NON2.
Agora, nenhum NON que é acessível a partir do NON3.
O NON é acessível a partir do NON4 e o NON4 é acessível a partir do NON1 e a partir do NON2.
Perfeito.
Manda isso.
Nós vamos ter aqui também que o NON2 é o NON1 acessível a partir do NON2.
Nós temos um caminho de 2 até a unpação pelo NON4, seguindo por essa resta que pode ser acessível.
Bom, se a gente pensar no sistema que é modelado por um gravo direcionado como NON inicial, um NON acessível a partir do NON inicial nunca feta tal sistema.
Então, essa questão da acessibilidade, ela pode ser pensada em termos de vale a pena não ter um NON que não é acessível a partir de outro.
Então, considerando um determinado NON inicial, por exemplo, aqui não vale a pena eliminar nenhum NON se eu pensar no NON2 com um NON inicial.
Porque a partir do NON2, eu consigo acessar NON3 com NON4 e NON1.
Então, todos esses NON seriam relevantes em um sistema, cujo NON é um NON2.
Porém, a partir do momento em que você determinou NON inicial e determinou NON, não são acessíveis, então, eles poderiam, num contexto de modelar de problema, se eliminar, tá? É, assim, a matriz de adjacência, por si só ela vai representar esse contexto da acessibilidade do ponto de vista da adjacência entre nós.
Então, por exemplo, se o NON2 são adjacentes nesse graf, isso vai estar representado aqui, só que, claro, considerando o direcionamento que estamos no grafo direcionado.
Então, eu acesso, eu tenho um arco ligando no NON2, isso tá representado aqui, e o NON3, isso tá representado aqui.
Então, de partida, nós já temos a matriz boleana que representando as adjacências, ou seja, os caminhos de comprimento 1.
Bom, então, agora vamos pensar, se eu fizer um produto de matrises, considerando que essa matriz de adjacências representa, então, um caminho de comprimento 1.
Recordando a definição de multiplicação para a matriz no contexto de matriz boleanas, que é essa definição aqui, ao fazer um desistido produto, nós vamos chegar em uma outra matriz que representa agora, as relações envolvam os caminhos de comprimento 2.
Coma, assim, então eu tenho aqui, do 1 para ele mesmo, eu tenho um caminho de comprimento 2.
Assim, eu vou do 1 para o 3, que do 3 para 1, retorno para 1.
Então, tenho aqui um caminho de comprimento 2.
Da mesma forma, como destacado aqui, do 2 para 1, eu tenho passando pelo 3.
Do 3 para o 2, eu também tenho um caminho de comprimento 2, passo por aqui para 1, e depois vou para o 2.
E aí, que se chegamos a um teorena aqui no dos desistigantes, que se há por a matriz boleana, de adjacência de um grafo de destesionados gímos, um M nosce e sem arcos paralelos.
Então, a entrada A e C e J para M produtos realizados, sendo igual a 1, ela vai ser igual a um 6, somente 6, e tinha um caminho de comprimento, um M do Noin para o Noin J.
Beleza, mas então, faz sentido, eu saí multiplicando hoje, na 3.
Vamos pensar num contexto de um grafo.
Se o grafo tem M, nós, então, qualquer caminho com N e arcos, ou Max, e, portanto, com N mais 1, nós com N mais 1, nós, ou Max, tem que ter um Noin repetido, porque eu estou colocando, né, naquele contexto, a partir do momento que eu é cedo para N mais 1, para N mais 1, eu começo a repetir, nós, nesse caminho.
Isso pode não ser, mas tão relevante para mim, em termos de explorar o que esse produto está representando.
Então, de certa forma, nós vamos precisar nunca procurar um caminho de N e a N, J, de comprimento maior que N.
Então, estamos considerando aqui que essa repetição de nós, no caminho, não vai ser interessante para a gente.
Bom, então, considerando isso, chegamos na ideia da matriz de acessibilidade, e vamos demotar aqui por é, que é uma matriz formada, considerando aqueles produtos matriciais que fizemos, considerando o produto de matrizes bolêmeles, onde vamos estabelecer uma relação agora, né, de ou entre os resultados dessas matrizes, e o que isso vai dizer para a gente? Vai dizer que o N e J será acessível a partir de um N e, se isso é o elemento e J, em R, positivo.
Vamos pensar, aqui nós temos 1, sempre em cada um desses produtos, nós vamos ter 1, sempre que existiu o caminho, de determinado comprimento.
A partir do momento que exista através de quando aplicarmos uma relação de junção entre as entradas dessas matrizes, nós vamos ter o valor, sempre que o valor não ocorre, já é um indicativo de que bom aquele N é acessível, e isso para mim é já boa que seja uma informação mais muito suficiente para eu tomar determinadas decisões.
Então, como que isso se aplica aqui? Nós vamos ter o contexto da relação de nada de acessibilidade, que vamos representar por R com N, C, R, em o grafo de ilestionado G, definido a da seguinte maneira, C, N e C, N se relaciona com N e J em R, quando há um caminho em G de N e para N e J, dessa maneira, então eu sei que sempre que eu tiver esse caminho, eu tenho esse relacionamento.
Dessa maneira, esse R, ele é um fecho transitivo da relação binária em R, que representa esse grafo, porque eu estou incluindo em R, em C, R, toda transitividade, ou seja, todo o alcance, deu percorrer a partir de um nó, a partir de um nó, eu consegui seguir uma trajetória até o outro.
Então, eu vou ter toda a relação de transitividade.
Vamos tentar entender isso melhor com um exemplo, se já não ficou claro.
Então, nós temos aqui uma matriz que representa esse grafo com essa relação do que é esse relacionamento binário aqui estabelecido.
Então, nós temos um nó de num pra dois, temos um nó de 5 para 3, de 5 para 1, e tudo isso também está armazenado aqui, 5 para 1, de 5 para 3.
Hoje, depois, vamos fazer uns produtos.
Então, aqui eu estou apresentando direitamente o resultado do produto, vocês podem conferir os cálculos, e para, no caso, para 2, 3, 4, 5, certo? Porque temos uma matriz com 5 nós, um grafo com 5 nós, e aí o que vai acontecer? Bom, então, vamos tentar agora juntar tudo isso porque a gente pega todos os resultados desses produtos e vamos ter aqui através das disjunções dos resultados a matriz R de acessibilidade.
E aí o que essa matriz nos diz? Ela representa exatamente a armazena, esse fecho transitivo a partir de R.
Por quê? Vamos observar aqui, você vai ver que todas as propriedades do fecho transitivo, ele é o menor conjunto com a propriedade que representa contendo essa propriedade de transitividade, por quê? Porque ele vai adicionar todas as relações.
Então, por exemplo, eu tenho aqui 2 para 3, 3 para 1, então eu tenho a transitividade 2 para 1, só que uma vez que eu tenho a transitividade de 2 para 1, eu compoem com 1 para 2, 2 para 1, eu tenho 1 para 1.
Então, se vocês me verificarem aqui, vocês vão ver que esse é o menor conjunto, contendo a transitividade da transitividade a partir dessa relação, então eu vou ler o fecho transitivo.
Bom, isso aqui então nos indica quais são os nós acessíveis para esse gráfico.
Bom, espero que essas ideias têm não ficar claras, eu recomendo a leitura da sessão 7.
1 e nos vemos na próxima aula.
Muito obrigado.