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

@fenix117 · Регистрация: 16.03.2011

Студворк — интернет-сервис помощи студентам

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

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;

Байт · 20.02.2012, 12:14

Если без всяких векторов, на старом добром Си, тогда так

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++;  
}

@Axie · 14.12.2018, 17:20

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]
а можно подробнее?

Байт · 14.12.2018, 17:39

Получил в личку.

Сообщение от Axie

Вот ваша программа для преобразования матрицы смежности в матрицу инцидентности, можете объяснить подробнее как она работает?
char sm[N][N}; // Матрица смежности
char *in[N]; // Матрица инцендентности
...
}

Если бы вы знали, как это достает!
Есть правило 4.6. Прочтите, пожалуйста, и постарайтесь его соблюдать.

@Axie · 14.12.2018, 17:55

Прошу прощения, просто я новенький на сайте. Очень нужна помощь, нигде не могу найти информацию по этой теме. Единственная зацепка, это ваш код

Байт · 14.12.2018, 19:22

Axie, Что именно не понятно?
Кстати, там у меня, кажется описка. В комментариях. должно быть " // v - число ребер"
И там все просто. В строчке 5 создается строка по числу ребер.
И для каждого ребра ставятся 1 в те позиции (номера вершин), которые это ребро соединяет.
Да вы возьмите небольшой граф, составьте матрицы смежности и посмотрите, как из нее программа делает матрицу инцендентности. Просто пошагово.

@Axie · 15.12.2018, 14:53

Ругается на эти строки,

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

Байт · 15.12.2018, 17:12

Axie, матрица смежности - квадратная. Зачем ты вводишь 2 размера - n, m? Ну и запутался в них, конечно.
Если будут еще ошибки, сообщи какие ты данные вводишь (без a[i][j])
И какое отношение фрагмент (4 строки) имеет отношение к твоему коду?

@Axie · 15.12.2018, 17:45

Байт, матрица смежности конечно квадратная, но матрица инцидентностей имеет размер n*m, и еще про какую строку вы говорите?

Байт · 15.12.2018, 18:48

Сообщение от Axie

но матрица инцидентностей имеет размер n*m,

Размер матрицы интцендентности вычисляется в программе. И вообще, постарайся немного подумать своей головой. Я уже жалею, что 9 лет назад придумал этот маленький код...

@L1ZER · 30.11.2020, 17:17

Сообщение от Axie

for(i=v=0; i<N; i++) for(j=i+1; j<N; j++) if (sm[i][j]) v++;

если я правильно понимаю то эта часть считает кол-во рёбер по матрице смежности?

C#
1
2
3
4
5
6
 int[,] A = new int[,]
            {
                {0, 1, 0},
                {0, 0, 1},
                {1, 0, 1}
            };

вот по такой матрице смежности считает не правильно - выводит кол-во рёбер =2 а надо 4

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@fenix117 8 / 8 / 2 Регистрация: 16.03.2011 Сообщений: 257

	Как из матрицы смежности получить матрицу инцидентности? 19.02.2012, 13:34. Показов 24012. Ответов 10 Метки нет (Все метки) Здравствуйте. Можно ли из матрицы смежности получить матрицу инцидентности? Матрица смежности у меня для связного неориентированного графа без петель. Вот пример сгенерированной матрицы смежности (симметрична относительно главной диагонали, по диагонали нули): 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

@Axie 0 / 0 / 0 Регистрация: 22.11.2018 Сообщений: 16
	14.12.2018, 17:55
	Прошу прощения, просто я новенький на сайте. Очень нужна помощь, нигде не могу найти информацию по этой теме. Единственная зацепка, это ваш код 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	14.12.2018, 19:22
	Axie, Что именно не понятно? Кстати, там у меня, кажется описка. В комментариях. должно быть " // v - число ребер" И там все просто. В строчке 5 создается строка по числу ребер. И для каждого ребра ставятся 1 в те позиции (номера вершин), которые это ребро соединяет. Да вы возьмите небольшой граф, составьте матрицы смежности и посмотрите, как из нее программа делает матрицу инцендентности. Просто пошагово. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	15.12.2018, 17:12
	Axie, матрица смежности - квадратная. Зачем ты вводишь 2 размера - n, m? Ну и запутался в них, конечно. Если будут еще ошибки, сообщи какие ты данные вводишь (без a[i][j]) И какое отношение фрагмент (4 строки) имеет отношение к твоему коду? 0

@Axie 0 / 0 / 0 Регистрация: 22.11.2018 Сообщений: 16
	15.12.2018, 17:45
	Байт, матрица смежности конечно квадратная, но матрица инцидентностей имеет размер n*m, и еще про какую строку вы говорите? 0

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

Решение