Создать случайную матрицу смежности, где каждый узел имеет минимальную степень k - PullRequest
Новая
       28

Создать случайную матрицу смежности, где каждый узел имеет минимальную степень k

0 голосов
/ 08 апреля 2019

Я хочу создать случайную матрицу смежности, где каждый узел связан с 'k' другими узлами. Граф, представленный матрицей смежности, является ненаправленным.

Я начал с 7 узлов в матрице смежности, и каждый узел должен быть подключен как минимум к 3 другим узлам. Пока я смог получить это: 

0 1 1 0 0 0 0 
1 0 1 1 0 0 0 
1 1 0 1 1 0 0 
0 1 1 0 1 1 0 
0 0 1 1 0 1 1 
0 0 0 1 1 0 1 
0 0 0 0 1 1 0

Как видно из матрицы, в первой и последней строке менее трех соединений.

Моя реализация пока такова: 

   for( int i= 0; i<7; i++){
  for( int j= i+1; j<7; j++){
    if(i==j){
        topo[i][j]=0;
     }
    else{    
        for(int k=j; k<i+3 && k<7; k++){
            int connectivity=0;
            while(connectivity<3){
           if(topo[i][k]!=1 && topo[k][i]!=1){
                   topo[i][k]=1;
               topo[k][i]=1;
               connectivity++;
                }
           else{
               connectivity++;
        }
             }
          }
      }
   }
}

1 Ответ

0 голосов
/ 08 апреля 2019

Я предполагаю, что речь идет о ориентированных графах.Предположим, что v - это число вершин (узлов), а d вершины A (градус, Ваш k) - это число ребер, которые тонут от A до других узлов.

Если вы посмотрите поближе, вы можете узнать, что d значение узла k-th - это число 1 в строке kth.Таким образом, единственное, что нужно сделать, - это нарисовать вектор 0s и 1s с v-1 (мы не соединяем узел с самим собой) элементами для каждой строки.

Вы можете нарисовать случайный вектор из нулейи те, записывая d единиц к нему и случайным образом переставляя его.

Примечание для неориентированного графа - Вы можете перенести этот алгоритм в верхний правый матричный треугольник, динамически переписывая известные значения в нижний левый.Чем для каждой строки сверху вниз. Вы можете принять алгоритм, который рисует остаток строки.

...