С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 35, средняя оценка - 4.66
fenix117
8 / 8 / 1
Регистрация: 16.03.2011
Сообщений: 249
#1

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

19.02.2012, 13:34. Просмотров 5197. Ответов 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;
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2012, 13:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как из матрицы смежности получить матрицу инцидентности? (C++):

С матрицы смежности в матрицу инцидентности, список рёбер и вершин, диаграмма - C++
Помогите, пожалуйста. На C# или C++ нужна такая программа, что когда задается матрица смежности (5 на 5 можно) и выводились: 1) матрица...

По матрице инцидентности построить матрицу смежности - C++
Здравствуйте, помогите пожалуйста с заданием: По матрице инцидентности графа G построить матрицу смежности, если 1) G — простой...

Определение матрицы смежности графа по заданной матрице инцидентности - C++
Доброй ночи :) Изучаю графы, написал фукнцию для конвертации матрицы инцидентности в матрицу смежности, а наоборот не выходит. ...

Реализация матрицы смежности и инцидентности, поиск циклов в графе - C++
Здравствуйте. Есть программа, выводящая матрицу смежности и инцидентности. Прошу помощи в реализации добавления и удаления вершин и рёбер...

Ориентированный граф. Получить из списка рёбер матрицу смежности - C++
Задача: Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности. Входной файл содержит...

Задание графов матрицами смежности,инцидентности - C++
1. задать граф матрицей смежности; 2. задать граф матрицей инцидентности; 3. задать граф списком ребер. Замечание: 1. для...

1
Байт
Нарушитель
Эксперт C
16704 / 10968 / 1692
Регистрация: 24.12.2010
Сообщений: 21,413
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++;  
}
5
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2012, 12:14
Привет! Вот еще темы с ответами:

Как построить матрицу инцидентности? - C++
Доброго времени суток, Возникла задача. имеем файл, в котором описан неориентированный граф следующим образом: p edge 64 1333 e 1 2...

Преобразование списка смежности в матрицу смежности - C++
Помогите пожалуйста, нужно разработать алгоритм преобразования списка смежности в матрицу смежности, для неорентированного графа. И все...

Получить матрицу, в которой элемент определяется как наибольшее значение из элементов исходной матрицы - C++
Получить матрицу B размером (NxN), в которой элемент (b)ij определяется как наибольшее значение из элементов исходной матрицы A, лежащих...

Даны две целочисленные матрицы 4-го порядка. Получить новую * матрицу путем вычитания из элементов каждого столбца первой матрицы - C++
даны две целочисленные матрицы 4-го порядка. Получить новую матрицу путем вычитания из элементов каждого столбца первой матрицы сумму...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.