ALGORITMOS E IMPLEMENTAÇÕES ⇒ Linguagem PHP

[Auto Excluído (ID: 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 desenvolver grafos cujas arestas
entre os vértices possuem uma probabilidade p de existir (grafo conhecido pelo nome
de Erdõs-Rényi, G(n,p)), onde n é o número de vértices. Esta função deve retornar a
matriz de adjacências correspondente. Note que a implementação das funções deve
respeitar as assinaturas abaixo, na qual o parâmetro $vetorVertices contém o vetor
de vértices (p.ex., o vetor V da figura acima) e o parâmetro $probabilidade é um
número real entre 0 e 1 usado para definir se cada uma das arestas entre os elementos
de V existem ou não.
Dica: A implementação da função deve considerar cada uma das possíveis arestas do
grafo através da combinação dois a dois de todos os vértices. A aresta existe se o valor
retornado por uma função aleatória for menor que o valor da probabilidade utilizada. A
função aleatória deve retornar valores pertencentes ao mesmo intervalo real de
probabilidades, ou seja, entre 0 e 1.
function cria_grafo($vetorVertices, $probabilidade)