Grafos: fundamentos, aplicações e representações

Texto original

O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.

Texto extraído do video Fundamentos Matemáticos para Computação - Grafos e suas representações

Olá, alunas e alunos do Cústito Fundamento de Sma Temática para Computação.
Nesta videoólogo, eu vou falar de grafos e suas representações.
Eu vou começar definindo grafos apresentando terminologia relacionada.
Vou descrever algumas aplicações e, por último, falar da representação computacional para grafos.
O grafo de uma maneira informal, pode ser visto com um conjunto não vazio de nós, ou vertes e um conjunto de arcos ou arestas.
Estais que cada arco vai dar conectando dois nois.
Trata-se de uma maneira bastante robusta da gente modelar o representar um problema.
Por exemplo, no marido social, podemos utilizar o gráfico para estabelecer relacionamentos entre os usuários.
No marido de computadores, podemos enxergar cada nova computador e as conexões estabelecidas como arcos.
O grafo de uma maneira formal, ele é definido como uma triplor de nada, composta por nós, arcos e por uma função que associa a cada arco.
Um par não ordenado os xy de nóis, chamados de extremidades deste arco.
Aqui nós temos um grafo com 5 nóis onde o conjunto de arcos é representado por esses subconjunto, formados pelos nóis, onde, por exemplo, o subconjunto 1, 2 representa conexão do 9, 1, 2.
Observe que, nesse grafo, nós temos arcos paralelos, que eles estão representados aqui pela repetição do subconjunto.
3, 4 e 3, 4.
Da mesma forma, temos um laço que está sendo representado aqui pelo convotinho 5, 5.
Nesse caso, uma outra maneira de representar o arco é através de um módulo.
Então, o a índice aqui representa a conexão do 9 ao 2.
Se aplicarmos a função, nós vamos ter as extremidades desses arcos.
Então, no aplicando a função sobre o arco, a índice 1, nós temos a extremidade 1 e 2.
Sobre o arco a índice 2, as extremidades 1 e 3 representadas pelo 1 e o 9³.
E assim, sucessivamente.
Simplesemos um direcionamento aos arcos, nós passamos a ter o conceito de grafo direcionado, de grafo, que vai ter uma função agora, g associando a cada arco 1 par ordenado, e não mais um conjunto.
Nós vamos ter um par ordenado de nós onde o x representa a extremidade inicial e o y, a extremidade final desse arco, para indicar o direcionamento.
Então, por exemplo, no caso anterior, simplesernos uma direção aos arcos, nós passamos a ter o par ordenado 1, 2, representando o direcionamento que vai do 9 ao 2.
Então, no caso dos arcos paralelos, por exemplo, nós passamos a ter o par ordenado 3, 4, indicando o 3 como extremidade inicial e o módulo 4 como extremidade final do arco a 3.
Por outro lado, o par ordenado 4, 3, agora, indica o direcionamento que vai do 9³ por 3, representado aqui pelo arco a 4.
Mondeça a forma ao aplicar a função sobre um arco, nós teremos o seu respectivo par ordenado.
Agora, eu vou apresentar diversos terros, como momento utilizados quando estamos trabalhando com grafos.
Então, por exemplo, o conceito de nós adiacentes, nós adiacentes, dois nós são considerados adiacentes quando temos um arco conectando diretamente esses dois nóis, o que, por exemplo, não ocorre o nome e o nosso ínculo, não há um arco conectando eles diretamente, então eles não são adiacentes.
Arcos paralelos são arcos que apresentam as mesmas extremidades, como é o caso desses dois arcos aqui.
Um laço é um arco que conecta um nó a ele mesmo, e um nó isolado é um nó que não se conecta nem um outro.
Um grafo simples é um grafo que não possui glácio nem arcos paralelos.
A ordem de um grafo é dada pelo número de nóis desse grafo.
Então, nesse caso aqui, a ordem é 6.
No grafo simples apresentado, a ordem seria 5.
O grau de um nó é o número de extremidades de arcos naquele nói.
Então, por exemplo, o nosso nó, um aqui, tem duas extremidades desse arco, uma desse arco, que é outra desse aqui.
Então, o seu grau é 2.
O nó 2 tem uma única extremidade de arco incidindo o nele.
Então, o nó é o grau.
O nó 3 já apresenta 3 extremidades incidindo o nele.
Então, o grau é 3, a mesma coisa para o 4.
No nosso 5, nós temos três extremidades, também por conta da extremidade desse arco e das duas extremidades desse arco, que formula isso.
O nosso 6, por outro lado, vai ter grau zero.
Quando temos grafo direcionado, precisamos olhar o grau, considerando o grau de entrada e o grau de saída.
Messe caso, o grau de entrada é representado pelo número de arcos que entram no nói.
E o grau de saída é o número de arcos que saem desse nói.
Então, por exemplo, no nó 1, aqui nós não temos arcos entrando nesse nói.
Então, o seu grau de entrada é 0.
Por outro lado, o seu grau de saída é 2.
O que temos é este arco e esse aqui saindo do nói.
No nói 2, nós temos este arco entrando 1 e nenhum arco saindo grau de saída é 0.
No nói 3, nós temos este arco entrando, este aqui entrando também.
Então, grau de entrada 2 e este aqui saindo grau de entrada 1.
No nói 4, contrarmos, nós temos este arco entrando e dois arcos saindo dele.
E no nó 5, que tem esse laço, nós temos 1, 2 arcos entrando, então grau de entrada 2 e 1 arco saindo grau de entrada 1.
Agora, chegamos no conceito de grafo completo.
Um grafo completo é um grafo simples no qual dois nóis distintos com as que são adjacentes.
Então, por exemplo, calma aqui e este anotação usada muitas vezes para representar um grafo completo.
O grafo completo calma, ele é representado por um único nó.
O k2 teríamos então 2 nóis adjacentes, no k3, conexão entre quaisquer desses dois nóis e a mesma coisa o k4.
Então, é sempre um grafo simples no qual dois nóis distintos com a esquerda não ser adjacentes.
Essa é a ideia do grafo completo.
Um super grafo, ele pega uma estrutura de um grafo e monta um grafo semelhante a partir do subconjunto de nóis e arestas.
Só que, nesse caso, então, a estèmeidade de arco tem que ser os mesmos, tem que apresentar os mesmos nóis que no grafo original.
Então, por exemplo, quando eu faço este subgrafo aqui, eu retirei o laço e retirei um dos arcos paralelos.
Nesse subgrafo aqui, eu retirei o nó 2 e o seu arco.
Respectivo, além de um arco paralelo aqui, obtendo este subgrafo.
O caminho, um grafo, ele é representado dessa forma.
Eu coloco o nó de onde eu quero partir, o nó de onde eu quero chegar e vou listando os arcos que me levam a atingir o nosso seguinte, o arco que me leva a atingir o nosso seguinte de modo a chegar no nó destino aqui.
Então, essa sequência, por exemplo, aqui nesse caminho, é representada dessa forma.
Eu tenho um nó 1, que chega ao nó 3 através do arco 1, 3, depois do nó 3.
Eu parto por nó 4, para ver o arco 3, 4, do nó 4, e parto por nó 5, para o nó 5, através do arco 4, 5.
Então, eu crie um caminho de 1 a 5, onde o comprimento vai ser dado pelo número de arcos neste caminho.
Então, se eu tivesse, por exemplo, essa conexão entre 1 e 4, eu poderia me perder no ciclo nesse caminho.
Eu poderia criar um caminho que incluem um ciclo, ou seja, eu dou uma volta aqui antes de chegar ao 5.
Então, no caminho, eu posso ter a repetição de arcos e nós, isso não é um problema.
E nesse caso, o porquê que eu sei que eu tive um ciclo, eu parti desse nó 4 e retornei a ele, para depois seguir por nó 5, criando um caminho bem mais longo para se chegar de 1 a 5.
Bom, o grafo, ele é connexo, quando há um caminho de qualquer nó para qualquer outro.
Então, observem aqui que eu consigo estabelecer um caminho de 5, por exemplo, para 7, de 5 para 6.
Aqui, eu já não consigo fazer isso.
Há uma desconexão entre esses entre o nó 6 e 7 e os demais.
Então, eu não consigo de 5 chegar a 6, não consigo de 5 chegar a 7, nem de 4 chegar a 6.
Então, só consigo chegar a 6 a partir de 7.
O ciclo, ele é o caminho de 1,9 e 0 para ele mesmo.
Lembra, quando eu tinha apresentado anteriormente? Tal que nenhum arco aparece mais de uma vez, é certo o N0 nas extremidades.
E o grafo, ele vai ser dito, a ciclico, quando ele não tem ciclos.
Então, se observarmos aqui, eu tenho um ciclo, um, três, quatro, um, um, quatro, cinco, um, três, quatro, cinco, um.
Já nesse grafo aqui, eu não consigo identificar nenhum ciclo.
Então, como a gente tinha visto naquele caminho, observe que na parte que temos o ciclo, eu tenho um, quatro, depois eu retorno um, um, quatro, caracterizando o ciclo.
E dentro do ciclo, eu não tenho repetições de nós, nem de arestas.
Eu posso ter repetição em um caminho, mas não num ciclo.
O grafo de partido completo, ele estabelece a seguinte relação.
Eu vou ter dois conjuntos de nós, onde, dentro desses conjuntos, os nós não são adjacentes.
Ele só são adjacentes em relação a nós do outro conjunto.
E nesse caso, para ser completo, qualquer node n não se conecta todos os nós de n2.
Por exemplo, nós também temos pro grafo completo de partido, uma notação específica, que é o KN, onde n é a cardinalidade do conjunto da partição n1 e n é a cardinalidade da partição n2.
Então, nesse exemplo aqui, nós vamos ter n a partição n1 com três elementos, a partição n2 com dois elementos, então seria um grafo K32.
Pode ser que os nós dentro da partição, eles não são adjacentes, mas por outro lado, são adjacentes a todos os nós da outra partição, o que caracteriza ele como completo.
E, observe, então, que se trata de uma partição n1 e n2, não tem elementos incomuntos em conjunto.
Agora, eu vou apresentar algumas aplicações de grafos.
Então, a mais visual é a gente apresentar o grafo em termos de mapeamento.
Por exemplo, para representar trajetórias entre cidades ou percurso a ser entomados por determinado avião, o fato é que os nós podem ser visto como pontos de interesses, ou no caso cidades, e os arcos como as distâncias serem percorridas ou estrajetos a serem seguidos.
Outra aplicação interessante de grafos são as redes neurais em inteligência artificial.
Redenurais são aplicadas, por exemplo, o problema de classificação.
Você tem uma camada de entrada que recebe os dados, os nós fazem o processamento.
E os arcos representam que os pesos desses resultados dos processamentos que podem passar por camadas intermediárias até o termo soma saída para o problema.
Nunca em redes de computadores nós também temos o uso de grafos para modelar essas estruturas de redes.
Então, se observarmos aqui, temos uma estrutura para uma topologia árvore, aqui uma topologia anel, uma topologia barra, e onde cada nó é representado por um computador e as iligações são representadas pelos arcos, que os iligações entre esses computadores.
Vamos falar agora da representação computacional.
Então, eu posso utilizar matrices para representar os se existem pearcos entre um nó e um nó jota.
Então, se eu considerar as linhas aqui com os nós, um, dois e três, e as colunas também, um, dois e três, eu tenho que não se conectar ele mesmo, não há um laço aqui, porém, eles se conectam ao dois e eles se conectam ao três, só que no caso da conexão com três eu tenho dois arcos.
Na mesma forma, eu observo o que é o que é o fazer essa representação, por exemplo, para o nó tres, eu também vou ter o nó tres se conectando ao nó um com dois arcos.
Então, eu estou tendo uma simetria nessa representação.
Então, eu posso, na verdade, armazenar só a parte triangular inferior dessa matriz, porque a parte de cima está replicada, essa matriz é seméptrica, considerando um grafo que não é direcionado.
Quando temos grafo direcionado, precisamos olhar direção, observa que, agora, que o nó um, ele não se conecta ele mesmo tudo bem, mas também não se conectam ao dois.
Eles se conectam apenas ao três com o nó arco, isso aqui, dada direção.
Já o nó dois, eles se conectam ao um e a ele mesmo, e o nó três se conecta apenas ao um, o nó um e o arco, que é isso aqui.
Então, a direção passa a ter um papel relevante na matriz de adjacência, no grafo direcionado.
Bom, se nós observamos as matrizes, se você passar numa matriz M por N muito grande, você pode estar alocando um espaço considerável, mesmo considerado, ou não, você pode estar alocando um espaço considerável para armazenar valores nulos.
Então, estão, na seis vezes, mais eficiente, o te trabalhar com listas, quando você aloca a memória necessária para armazenar os valores listados para uma determinada informação.
Por exemplo, por o nó, eu tenho que se conectar dois, a três, e a três, por conta dos dois arcos aqui.
Então, eu tenho apenas essa informação armazenada, eu não tenho informação de que ele não se conecta ao quatro.
O nó dois, mesmo, é uma coisa se conectar um e ao dois, o nó três, ao um, por dois arcos, e ao quatro, e o nó quatro, ao nó três.
Se eu pensar em grafo direcionado, aí isso ainda fica um pouco mais enxuto, porque eu tenho que considerar os direcionamentos.
Então, no N1, eles se conectam apenas ao três, por esse arco.
O dois se conectam ao N e mesmo, o três se conectam ao N e se conectam ao quatro.
O quatro, por sua vez, não se conectam ninguém.
Eu posso também, como a gente falou isso, vai ser usado para representar problemas.
Se essas ligações representam, por exemplo, distância, azul ou um peso, algum valor de um teresse, qualquer problema, o que vai acontecer? Eu posso ter um campo alocado nesse nó que armazena, não só o índice do nó ao qual eu estou conectado, quanto o peso associado.
Então, por exemplo, um ontem conectado ao três, e o peso associado ao 30.
Então, eu posso inserir uma informação relativa a essa conexão aqui, como, por exemplo, uma distância.
Então, no acaso do nó a dois, ele está conectado ao um, com o fim do dia aqui, e aí ele mesmo com o peso 10.
E assim, sucessivamente.
Uma outra maneira de dar apresentando isso é através de tabelas.
Então, eu posso ter, por exemplo, aqui, nessa representação, considerando o tabela, eu tenho um ponteiro que indica que o nó 1 está conectado a linha 5, o que tem na linha 5, o nó 3, com peso 30, e ponteiro 0, que, ou seja, não está conectado a mais ninguém.
O nó 2 está conectado a informação indicada no ponteiro 6, que é essa linha da tabela, que seria o nó 1 com peso 20.
E aí eu já me remeto ao ponteiro 7, que tem a coleção com ele mesmo, com peso 10, e mais ninguém.
Então, eu percorri toda a informação relativa 2 nessa tabela.
Vamos fazer o percoço com 3.
No ponteiro 8, tem de informação.
O 3 está associado à informação do ponteiro 8, que seria o nó 1 com o peso 10, e também a informação do ponteiro 9, que é o nó 4 com peso 40 e mais ninguém.
Já o nó 4 não se conecta a ninguém.
Bom, é isso aqui.
Nós passamos então na aula de hoje os conceitos bem básicos, a respeito de grafos.
Espero que vocês tenham entendido e recomenda a leitura da sessão.
com.
c6.
1 do nosso material paz.
Obrigado.