ALGORITMOS E IMPLEMENTAÇÕES ⇒ Linguagem PHP

[Deleted User 25727]

Uma estrutura em grafo é utilizada para modelar relações entre pares de elementos
de um determinado conjunto. Os elementos são chamados de vértices e as relações
entre pares, quando existirem, definem o conjunto de arestas. Tomemos um exemplo
prático: um conjunto de alunos do CEDERJ pode ser modelado como um conjunto de
vértices de um grafo enquanto as arestas podem representar relações entre pares de
alunos que pertençam a uma mesma turma. A figura abaixo ilustra o grafo resultante
do seguinte conjunto de alunos V = {Maria, João, José, Ana, Antônio,
Joana}, sabendo que Maria, João e Ana foram da mesma turma de PAW em 2021;
João, José e Joana da mesma turma de redes em 2020; e Antônio e Joana da
mesma turma de sistemas operacionais também em 2020.
Note que é possível representar o grafo através de uma matriz de adjacências M = V
V, onde M[j]=1 quando a aresta entre i e j existir. × Na figura abaixo,
M[j]=1 indica que eles pertenceram a uma mesma turma; enquanto
M[j]=0 indica que eles nunca pertenceram a uma mesma turma.
Pergunta:
Deseja-se desenvolver em PHP uma função para atualizar uma matriz de
adjacências, considerando a adição de um novo vetor de vértices. Note que todas as
arestas já representadas na matriz de adjacências devem ser preservadas. Note
também que o novo vetor de vértices pode conter arestas para vértices já existentes na
matriz original. Esta função deve utilizar passagem de parâmetro por referência para
atualizar a matriz de adjacências, gerando arestas considerando a mesma
probabilidade p. Note que a implementação das funções deve respeitar as assinaturas
abaixo, nas quais o parâmetro $vetorVerticesNovos contém o vetor com os novos
vértices, $matriz é a matriz de adjacência atual e $probabilidade é a mesma
probabilidade do item anterior.
function atualiza_matriz($vetorVerticesNovos, &$matriz, $probabilidade)