[MÚSICA] Salve, salve. vamos agora à segunda aula da Teoria de Grafos. Vamos continuar explicando que história é essa de grafos. [MÚSICA] Da mesma forma que na primeira parte, o objetivo é a gente criar o nosso vocabulário, para poder falar a mesma língua até ao final do curso. Existe mais de uma forma de classificar os tipos de grafo. A autoconexão. Pode haver grafos irreflexivos, quando os vértices não podem se conectar a si mesmos e grafos reflexivos, quando pode haver uma autoconexão. Aí forma uma alça ou loop. Pensa por exemplo numa teia trófica. Pode ser que uma dessas alças represente canibalismo. Importante é a gente reparar na direção do grafo. Grafos não direcionados, ou seja, quando as arestas não têm direção, tanto faz dizer que está conectado com dois, quanto que dois está conectado com. Tem grafos direcionados que as arestas têm direção. Nesse caso, a gente chama o sistema de digrafo e as arestas recebem o apelido de arcos. Nesse caso, vai fazer diferença dizer que o vértice está conectado com o dois ou que o vértice dois está conectado com o. Além disso, é importante olhar para o peso das arestas, existem grafos binários, que todas as arestas têm o mesmo peso, ou seja, na verdade, elas não têm peso nenhum, só importa se elas estão presentes ou ausentes; e grafos ponderados, que as arestas têm pesos diferentes. Por exemplo, se esse fosse sistema de interação entre animais e plantas, eu poderia dizer que o peso da aresta é proporcional à frequência da interação entre as duas espécies. Além disso, eu posso pensar classes de vértices. Eu posso ter grafo unipartido que todos os vértices são da mesma classe, então eles podem se conectar todos entre si. Ou grafo bipartido, que há duas classes de vértices. Eu só posso ter arestas entre vértices de classes diferentes. É o caso por exemplo de uma rede de polinização, que uma classe eu tenho as plantas e na outra eu tenho os polinizadores. É claro, polinizador não poliniza polinizador e planta não poliniza planta. Outro ponto muito interessante de a gente prestar atenção é a forma de representar o grafo. A gente entra na questão dos grafos isomórficos. Olha só. A gente diz que dois grafos são isomórficos quando eles têm o mesmo grau, o mesmo tamanho, a mesma topologia, só que são representados de forma diferente. Vamos olhar esse grafo com cinco vértices, e uma lista de arestas que representa esse grafo. Olha esse outro grafo daqui. São os mesmos cinco vértices e, repare, se você olhar, a lista de arestas é a mesma lista daquele outro, então, no fundo, é o mesmo grafo, eu só desenhei de forma diferente. Eu troquei as posições dos vértices mas as arestas continuam do mesmo jeito que elas estavam antes. É a mesma estrutura, só o desenho é diferente. Se eu quero variar o tipo de desenho, eu posso fazer grafo circular, eu posso representar de forma bipartida. Se ele for realmente bipartido, os vértices de uma classe eu empilho de lado e os vértices de outra classe eu empilho do outro lado. Posso fazer também uma representação de minimização de energia. Olha só que legal. O que é que eu chamo minimização de energia? Diminuir a entropia do desenho, não do grafo mas do desenho. Eu estabeleço dois critérios, aqueles vértices que têm grau maior vão ficar mais ao centro do desenho e vértices que ajudam a conectar subgrupos diferentes do grafo também vão ficar mais ao centro. Quanto mais o meu desenho respeitar esses dois critérios, menor é a energia dele, menor é a entropia. Isso é ótimo quando a gente quer estudar, por exemplo, centralidade. Fica muito mais fácil ver qual vértice é mais central, qual é o mais importante na estrutura do sistema. E eu posso fazer desenho de separação de componentes, eu uso os mesmos dois critérios da minimização de energia só que, na hora de desenhar eu afasto os subgrupos que eu identificar naquele gráfico. É claro, esse tipo de desenho é melhor quando a gente está analisando modularidade, ou qualquer tipo de análise de comunidades ou subgrupos. Outra coisa bem interessaante é que, às vezes, grafo pode estar contendo mais de sistema dentro dele. O grafo é o desenho simples que a gente está vendo até agora que existe apenas uma aresta entre dois vértices. Por outro lado, o multigrafo permite que exista mais de uma aresta entre os mesmos dois vértices. Olha, esse aqui é o caso daquele problema das Sete Pontes de Königsberg, do Euler, do século XVIII. Pensa, naquele sistema dele duas partes da cidade poderiam ser conectadas por mais de uma ponte. É o que acontecia ali. Isso acaba sendo multigrafo. Além disso, eu posso ter Hipergrafo, que uma mesma aresta pode conectar mais de dois vértices. Aí já vai aumentado a complexidade do que a gente está representando como grafo. No fundo, é como se tivesse mais de sistema embutido naquele sistema que a gente está analisando. Isso fica mais claro quando a gente trabalha com múltiplas camadas. Por exemplo, eu tenho três grafos, mas eu posso dizer que esses três grafos do desenho têm relação entre si, formando grafo multicamada. E o que define grafo multicamada? Dois ou mais tipos de arestas podem conectar dois vértices. Além disso, existem arestas intracamada e arestas intercamada e cada camada é definida por tipo de aresta. Por exemplo, imagina que eu estou querendo falar de interações entre animais e plantas. O meu assunto preferido. Eu sei que eu sempre acabo voltando para ele. Uma camada pode representar Frugivoria, a outra Nectarivoria e a outra Herbivoria. Ou seja, eu estou falando de relações entre animais e plantas que alguns animais gostam de comer frutos, outros gostam de beber néctar e outros gostam de comer folhas, por exemplo. Só que tem animais que fazem duas ou mais dessas coisas ao mesmo tempo. Aí, eu posso dizer então que é mais fácil representar isso tudo no mesmo sistema, num grafo multicamada. Eu vou ter arestas intracamada que definem as relações de uma determinada camada. A camada de Frugivoria, por exemplo. Então eu digo que o vértice e o dois se relacionam através do consumo de frutos. Eu tenho arestas intercamada. que vão ligar tipos de interações diferentes, por exemplo, nesse caso, eu digo que aquela espécie número seis está presente nas três camadas. Então, existe uma aresta intercamada que conecta ela cada desses subsistemas. [MÚSICA] Quais são as mensagens principais dessa aula e a moral da história? Lembre-se, há diversos tipos de grafos. Grafos podem ser classificados de acordo com as propriedades dos seus vértices e das suas arestas. Essas classificações envolvem classes, direção, peso, autoconexões, múltiplas conexões e outras propriedades. E é possível desenhar grafo de várias formas. Depende da história que você quer contar e de qual é o foco dessa história. E há grafos ainda mais complexos que representam a união de dois ou mais grafos. [MÚSICA]
