Форум программистов, компьютерный форум CyberForum.ru

Как из матрицы смежности получить матрицу инцидентности? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 35, средняя оценка - 4.66
fenix117
8 / 8 / 1
Регистрация: 16.03.2011
Сообщений: 249
19.02.2012, 13:34     Как из матрицы смежности получить матрицу инцидентности? #1
Здравствуйте. Можно ли из матрицы смежности получить матрицу инцидентности? Матрица смежности у меня для связного неориентированного графа без петель. Вот пример сгенерированной матрицы смежности (симметрична относительно главной диагонали, по диагонали нули):

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

P.S. Пишу на vs 2010 c++, граф представлен как vector<vector<int>> adjacency_matrix;
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2012, 13:34     Как из матрицы смежности получить матрицу инцидентности?
Посмотрите здесь:

C++ Задание графов матрицами смежности,инцидентности
C++ Определение матрицы смежности графа по заданной матрице инцидентности
C++ Получить новую матрицу прибавлением к элементам каждого столбца первой матрицы произведения элементов соответствующих строк второй матрицы
C++ Получить матрицу, в которой элемент определяется как наибольшее значение из элементов исходной матрицы
C++ Даны две целочисленные матрицы 4-го порядка. Получить новую * матрицу путем вычитания из элементов каждого столбца первой матрицы
C++ список смежности в матрицу смежности
Как построить матрицу инцидентности? C++
Ориентированный граф. Получить из списка рёбер матрицу смежности C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
20.02.2012, 12:14     Как из матрицы смежности получить матрицу инцидентности? #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Если без всяких векторов, на старом добром Си, тогда так
C
1
2
3
4
5
6
7
8
9
char sm[N][N};  // Матрица смежности
char *in[N]; // Матрица инцендентности
for(i=v=0; i<N; i++) for(j=i+1; j<N; j++) if (sm[i][j]) v++;
   // Нашли v - число вершин
for(i=0; i<N; i++) { in[i] = (char *) malloc(v); memset(in[i], 0, N); }
for(i=k=0; i<N; i++) for(j=i+1; j<N; j++) if (sm[i][j]) {
   in[k][i] = in[k][j] = 1;
   k++;  
}
Yandex
Объявления
20.02.2012, 12:14     Как из матрицы смежности получить матрицу инцидентности?
Ответ Создать тему
Опции темы

Текущее время: 13:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru