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

матрица инцидентности и смежностей - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.60
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 02:34     матрица инцидентности и смежностей #1
скажите пожалуйста, есть ли какая нибудь закономерность между матрицей смежностей и матрицей инцидентности? или лучше способ как вывести на экран матрицу инцендентности, имея матрицу смежности в с++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2010, 07:00     матрица инцидентности и смежностей #2
Цитата Сообщение от dre Посмотреть сообщение
есть ли какая нибудь закономерность между матрицей смежностей и матрицей инцидентности
если эти две матрицы для одного графа, то есть.


Цитата Сообщение от dre Посмотреть сообщение
способ как вывести на экран матрицу инцендентности, имея матрицу смежности в с++
Если имеем матрицу смежности a[n][n], то можно сделать матрицу инцидентности b[n][m] так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int col=0, i, j, j_b=0;
for(i=0; i<n; i++)
    for(j=0; j<n; j++)
        if(a[i][j])
            col++;
col/=2;
int **b=new int*[n];
for(i=0; i<n; i++)
{
    b[i]=new int[col];
    for(j=0; j<col; j++)
        b[i][j]=0;
}
for(i=0; i<n; i++)
    for(j=i+1; j<n; j++)
        if(a[i][j])
        {
            b[i][j_b]=1;
            b[j][j_b]=1;
            j_b++;
        }
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 10:41  [ТС]     матрица инцидентности и смежностей #3
а разве можно в динамических массивах использовать обращение к эллементам как в обычных, т.е. у тебя b[i][j] а надо то вроде b[i*n+j]
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2010, 10:54     матрица инцидентности и смежностей #4
а разве можно в динамических массивах использовать обращение к эллементам как в обычных, т.е. у тебя b[i][j] а надо то вроде b[i*n+j]
можно
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 10:59  [ТС]     матрица инцидентности и смежностей #5
а ошибок у тебя в коде точно нет, а то я попытался под себя сделать ничего не получилось((
вот что пытался сделать я, ( тут без твоей функции)
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
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
int find_cols_Minc(int*ar, int n)
{ int s=0; int cols;
for ( int i=0; i<n; i++)
{for (int j=0; j<n; j++)
if (ar[i*n+j]==1)  s++;
}
cols=s/2;
return cols;}
 
int*matr_incid(int*ar, int n, int col)
{int*ar2;
ar2= new int[n*col];
for (int i=0; i<n; i++)
{for (int j=0; j<col; j++)
if (ar[i*n+j]==ar[j*col+i] && ar[i*n+j]==1 && ar[j*col+i]==1  )  ar2[i*n+j]=1 ;
else ar2[i*n+j]=0;}
 
return ar2;}
 
void outMatrIncid (int*ar5, int n, int col)
{cout<<"\n";
for (int i=0; i<n; i++)
{for (int j=0; j<col; j++)
cout<<" "<<ar5[i*n+j]<<" ";
cout<<"\n";}
}
 
int main()
{int*ar3,*ar4; int n=5;
ar3 =new int [n*n]; int col_inc;
ar3[0*n+0]=0; ar3[0*n+1]=1; ar3[0*n+2]=0; ar3[0*n+3]=0; ar3[0*n+4]=1;
ar3[1*n+0]=1; ar3[1*n+1]=0; ar3[1*n+2]=1; ar3[1*n+3]=1; ar3[1*n+4]=1;
ar3[2*n+0]=0; ar3[2*n+1]=1; ar3[2*n+2]=0; ar3[2*n+3]=1; ar3[2*n+4]=0;
ar3[3*n+0]=0; ar3[3*n+1]=1; ar3[3*n+2]=1; ar3[3*n+3]=0; ar3[3*n+4]=0;
ar3[4*n+0]=1; ar3[4*n+1]=1; ar3[4*n+2]=0; ar3[4*n+3]=0; ar3[4*n+4]=0;
col_inc=find_cols_Minc(ar3,n);
 
delete [n*n] ar3;
ar3= new int [n*col_inc];
ar4=matr_incid(ar3, n, col_inc);
outMatrIncid (ar4, n, col_inc);
getch();
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2010, 11:18     матрица инцидентности и смежностей #6
См комментарии:
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
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
int find_cols_Minc(int*ar, int n)
{ int s=0; int cols;
for ( int i=0; i<n; i++)
{for (int j=0; j<n; j++)
if (ar[i*n+j]==1)  s++;
}
cols=s/2;
return cols;}
 
int*matr_incid(int*ar, int n, int col)
{int*ar2;
ar2= new int[n*col];
for (int i=0; i<n; i++)
{for (int j=0; j<col; j++)
if (ar[i*n+j]==ar[j*col+i] && ar[i*n+j]==1 && ar[j*col+i]==1  )  ar2[i*n+j]=1 ;
else ar2[i*n+j]=0;}
 
return ar2;}
 
void outMatrIncid (int*ar5, int n, int col)
{cout<<"\n";
for (int i=0; i<n; i++)
{for (int j=0; j<col; j++)
cout<<" "<<ar5[i*n+j]<<" ";
cout<<"\n";}
}
 
int main()
{int*ar3,*ar4; int n=5;
ar3 =new int [n*n]; int col_inc;
ar3[0*n+0]=0; ar3[0*n+1]=1; ar3[0*n+2]=0; ar3[0*n+3]=0; ar3[0*n+4]=1;
ar3[1*n+0]=1; ar3[1*n+1]=0; ar3[1*n+2]=1; ar3[1*n+3]=1; ar3[1*n+4]=1;
ar3[2*n+0]=0; ar3[2*n+1]=1; ar3[2*n+2]=0; ar3[2*n+3]=1; ar3[2*n+4]=0;
ar3[3*n+0]=0; ar3[3*n+1]=1; ar3[3*n+2]=1; ar3[3*n+3]=0; ar3[3*n+4]=0;
ar3[4*n+0]=1; ar3[4*n+1]=1; ar3[4*n+2]=0; ar3[4*n+3]=0; ar3[4*n+4]=0;
col_inc=find_cols_Minc(ar3,n);// теперь в col_inc кол-во столбцов для создания матрицы инцидентности
 
delete [n*n] ar3;// удалили массив ar3? (в котором все данные для формирования матрицы инцидентности). Теперь у нас нет данных из матрицы смежности и соответственно мы не сможем создать матрицу  инцидентности
ar3= new int [n*col_inc];
ar4=matr_incid(ar3, n, col_inc);
outMatrIncid (ar4, n, col_inc);
getch();
}
Еще немного добавлю:
Вы формируете двумерный массив выделением одного целого участка памяти. Поэтому у Вас обращение к элементам может быть только таким: b[i*n+j].
У меня в коде я выделяю память под матрицу другим способом. Поэтому в моем коде можно обращаться к элементам матрицы только так: b[i][j]. А вот так: b[i*n+j] - нельзя
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 12:45  [ТС]     матрица инцидентности и смежностей #7
но с моим кодом все равно идет вывод матрицы с размером [n, col_inc]. на сколько я понимаю new выделяет колво ячеек памяти а delete отказывается от них, т.е. я просто отказался от определенного колва памяти и выделил новое колво, и тот код который написали вы можно ли как то преоброзовать с к моему тоесть обращение чтобы было [i*n+j] или делать только как вы

Добавлено через 25 минут
valeriikozlov или если не сложно расскажите хотя бы принцип вашего алгаритма т.е. из чего исходили при создании
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2010, 12:55     матрица инцидентности и смежностей #8
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
48
49
50
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
 
int find_cols_Minc(int*ar, int n)
{ int s=0; int cols;
for ( int i=0; i<n; i++)
{for (int j=0; j<n; j++)
if (ar[i*n+j]==1)  s++;
}
cols=s/2;
return cols;}
 
int*matr_incid(int*ar, int n, int col)
{int*ar2, j_ar2=0, i;
ar2= new int[n*col];
for(i=0; i<n*col; i++)
ar2[i]=0;
for (i=0; i<n; i++)
{for (int j=i+1; j<n; j++)
if (ar[i*n+j]==1)
{
    ar2[i*col+j_ar2]=ar2[j*col+j_ar2]=1; j_ar2++;
}
}
 
return ar2;}
 
void outMatrIncid (int*ar5, int n, int col)
{cout<<"\n";
for (int i=0; i<n; i++)
{for (int j=0; j<col; j++)
cout<<" "<<ar5[i*col+j]<<" ";
cout<<"\n";}
}
 
int main()
{int*ar3,*ar4; int n=5;
ar3 =new int [n*n]; int col_inc;
ar3[0*n+0]=0; ar3[0*n+1]=1; ar3[0*n+2]=0; ar3[0*n+3]=0; ar3[0*n+4]=1;
ar3[1*n+0]=1; ar3[1*n+1]=0; ar3[1*n+2]=1; ar3[1*n+3]=1; ar3[1*n+4]=1;
ar3[2*n+0]=0; ar3[2*n+1]=1; ar3[2*n+2]=0; ar3[2*n+3]=1; ar3[2*n+4]=0;
ar3[3*n+0]=0; ar3[3*n+1]=1; ar3[3*n+2]=1; ar3[3*n+3]=0; ar3[3*n+4]=0;
ar3[4*n+0]=1; ar3[4*n+1]=1; ar3[4*n+2]=0; ar3[4*n+3]=0; ar3[4*n+4]=0;
col_inc=find_cols_Minc(ar3,n);// теперь в col_inc кол-во столбцов для создания матрицы инцидентности
 
ar4=matr_incid(ar3, n, col_inc);
outMatrIncid (ar4, n, col_inc);
getch();
}
Принцип еще нужен?
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 13:06  [ТС]     матрица инцидентности и смежностей #9
спасибо большое, только с расчетом на листочке не сходится, наверно я не правильно нашел матрицу инцидентности, у меня получилась такая

1 1 0 0 0 0
1 0 1 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 1 1 0 0 0
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2010, 13:38     матрица инцидентности и смежностей #10
У нас выводит:
1 1 0 0 0 0
1 0 1 1 1 0
0 0 1 0 0 1
0 0 0 1 0 1
0 1 0 0 1 0
т.е. смотрим по столбцам:
0 столбец - есть ребро между 0 и 1 вершиной
1 столбец - есть ребро между 0 и 4 вершиной
и т.д.
В принципе я встречался и матрицей инцидентности у которой наоборот идут строки и столбцы:
Например (для этого же графа):
1 1 0 0 0
1 0 0 0 1
0 1 1 0 0
0 1 0 1 0
0 1 0 0 1
0 0 1 1 0
т.е. здесь смотрим по строкам:
0 строка - ребро между 0 вершиной и 1 вершиной
1 строка - ребро между 0 вершиной и 4 вершиной
и т.д.
Для того что бы выводило так нужно заменить:
C++
1
2
3
4
5
6
7
void outMatrIncid (int*ar5, int n, int col)
{cout<<"\n";
for (int i=0; i<n; i++)
{for (int j=0; j<col; j++)
cout<<" "<<ar5[i*col+j]<<" ";
cout<<"\n";}
}
на:
C++
1
2
3
4
5
6
7
void outMatrIncid (int*ar5, int n, int col)
{cout<<"\n";
for (int i=0; i<col; i++)
{for (int j=0; j<n; j++)
cout<<" "<<ar5[i+j*col]<<" ";
cout<<"\n";}
}
А Ваш вариант:
1 1 0 0 0 0
1 0 1 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 1 1 0 0 0
неверный
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 14:11  [ТС]     матрица инцидентности и смежностей #11
спасибо, вы очень помогли. только теперь буду по новому разбираться с этой инцидентностью вчера видать не так понял как её составить((

Добавлено через 7 минут
и последний вопрос, при составлении матрицы инцидентности нумерация ребер должна быть определенной? или произвольной, сейчас прост попробовал с вашей матрицей все правильно, но не пойму почему именно так идет нумерация
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.12.2010, 14:16     матрица инцидентности и смежностей
Еще ссылки по теме:

Граф задается своей матрицей смежностей вывести на экране окружения каждой его вершины C++
C++ Преобразовать список рёбер в список смежностей
Как построить матрицу инцидентности? C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2010, 14:16     матрица инцидентности и смежностей #12
Цитата Сообщение от dre Посмотреть сообщение
и последний вопрос, при составлении матрицы инцидентности нумерация ребер должна быть определенной? или произвольной, сейчас прост попробовал с вашей матрицей все правильно, но не пойму почему именно так идет нумерация
Нумерация без разницы какая. Если последний вариант рассматривать:
1 1 0 0 0
1 0 0 0 1
0 1 1 0 0
0 1 0 1 0
0 1 0 0 1
0 0 1 1 0
То принцип такой: в одной строке должно быть ровно 2 единицы,
Кол-во строк соответствует кол-ву ребер в графе. Кол-во столбцов соответствует кол-ву вершин.
Yandex
Объявления
18.12.2010, 14:16     матрица инцидентности и смежностей
Ответ Создать тему
Опции темы

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