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)
ALGORITMOS E IMPLEMENTAÇÕES ⇒ Linguagem PHP
Moderador: [ Moderadores TTB ]
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última mensagem
-
- 3 Respostas
- 2162 Exibições
-
Última mensagem por Brunoranery
-
- 9 Respostas
- 5375 Exibições
-
Última mensagem por Catador