С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/33: Рейтинг темы: голосов - 33, средняя оценка - 4.67
fenix117
8 / 8 / 2
Регистрация: 16.03.2011
Сообщений: 249
1

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

19.02.2012, 13:34. Просмотров 6294. Ответов 9
Метки нет (Все метки)

Здравствуйте. Можно ли из матрицы смежности получить матрицу инцидентности? Матрица смежности у меня для связного неориентированного графа без петель. Вот пример сгенерированной матрицы смежности (симметрична относительно главной диагонали, по диагонали нули):

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++ нужна такая программа, что когда задается...

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

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

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

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

9
Байт
Эксперт C
19259 / 12378 / 2615
Регистрация: 24.12.2010
Сообщений: 25,493
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
Axie
0 / 0 / 0
Регистрация: 22.11.2018
Сообщений: 16
14.12.2018, 17:20 3
C++
1
2
3
4
5
6
7
8
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++
[/quote]
а можно подробнее?
0
Байт
Эксперт C
19259 / 12378 / 2615
Регистрация: 24.12.2010
Сообщений: 25,493
14.12.2018, 17:39 4
Получил в личку.
Цитата Сообщение от Axie
Вот ваша программа для преобразования матрицы смежности в матрицу инцидентности, можете объяснить подробнее как она работает?
char sm[N][N}; // Матрица смежности
char *in[N]; // Матрица инцендентности
...
}
Если бы вы знали, как это достает!
Есть правило 4.6. Прочтите, пожалуйста, и постарайтесь его соблюдать.
0
Axie
0 / 0 / 0
Регистрация: 22.11.2018
Сообщений: 16
14.12.2018, 17:55 5
Прошу прощения, просто я новенький на сайте. Очень нужна помощь, нигде не могу найти информацию по этой теме. Единственная зацепка, это ваш код
0
Байт
Эксперт C
19259 / 12378 / 2615
Регистрация: 24.12.2010
Сообщений: 25,493
14.12.2018, 19:22 6
Axie, Что именно не понятно?
Кстати, там у меня, кажется описка. В комментариях. должно быть " // v - число ребер"
И там все просто. В строчке 5 создается строка по числу ребер.
И для каждого ребра ставятся 1 в те позиции (номера вершин), которые это ребро соединяет.
Да вы возьмите небольшой граф, составьте матрицы смежности и посмотрите, как из нее программа делает матрицу инцендентности. Просто пошагово.
0
Axie
0 / 0 / 0
Регистрация: 22.11.2018
Сообщений: 16
15.12.2018, 14:53 7
Ругается на эти строки,
C++
1
2
3
4
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++;  
}
Пишет Необработанное исключение в "0x00ec16b6" в "Дискр5.exe": 0xC0000005: Нарушение прав доступа при записи "0xcccccccf".

Возможно в программе ошибки?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <Windows.h>
#include <conio.h>
 
int main()
{
    int i, j, v, n, m, k;
    char a[100][100];
    char *in[100];
    SetConsoleOutputCP(1251);
    SetConsoleCP(1251);
    printf("Введите размерность матрицы n =");
    scanf_s("%d", &n);
    printf("Введите размерность матрицы m =");
    scanf_s("%d", &m);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            printf("a[%d][%d]= ", i + 1, j + 1);
            scanf_s("%d", &a[i][j]);
        }
 
    printf("Матрица смежности: \n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            printf("|%d| ", a[i][j]);
        printf("\n");
    }
    for (i = v = 0; i < n; i++) for (j = i + 1; j < m; j++) if (a[i][j]) 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 < m; j++) if (a[i][j]) {
        in[k][i] = in[k][j] = 1;
        k++;
    }
    printf("Матрица инцидентностей: \n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
            printf("|%d| ", a[i][j]);
        printf("\n");
    }
    system("pause");
    return 0;
}
Пишу на VS 2010
0
Байт
Эксперт C
19259 / 12378 / 2615
Регистрация: 24.12.2010
Сообщений: 25,493
15.12.2018, 17:12 8
Axie, матрица смежности - квадратная. Зачем ты вводишь 2 размера - n, m? Ну и запутался в них, конечно.
Если будут еще ошибки, сообщи какие ты данные вводишь (без a[i][j])
И какое отношение фрагмент (4 строки) имеет отношение к твоему коду?
0
Axie
0 / 0 / 0
Регистрация: 22.11.2018
Сообщений: 16
15.12.2018, 17:45 9
Байт, матрица смежности конечно квадратная, но матрица инцидентностей имеет размер n*m, и еще про какую строку вы говорите?
0
Байт
Эксперт C
19259 / 12378 / 2615
Регистрация: 24.12.2010
Сообщений: 25,493
15.12.2018, 18:48 10
Цитата Сообщение от Axie Посмотреть сообщение
но матрица инцидентностей имеет размер n*m,
Размер матрицы интцендентности вычисляется в программе. И вообще, постарайся немного подумать своей головой. Я уже жалею, что 9 лет назад придумал этот маленький код...
0
15.12.2018, 18:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2018, 18:48

Задание графов матрицами смежности,инцидентности
1. задать граф матрицей смежности; 2. задать граф матрицей инцидентности;...

Как построить матрицу инцидентности?
Доброго времени суток, Возникла задача. имеем файл, в котором описан...

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


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

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

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