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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.60
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
#1

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

18.12.2010, 02:34. Просмотров 6622. Ответов 11
Метки нет (Все метки)

скажите пожалуйста, есть ли какая нибудь закономерность между матрицей смежностей и матрицей инцидентности? или лучше способ как вывести на экран матрицу инцендентности, имея матрицу смежности в с++
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.12.2010, 02:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Матрица инцидентности и смежностей (C++):

Граф задается своей матрицей смежностей; вывести на экран матрицу инцидентности графа. - C++
Пожалуйста помогите с задачкой: Граф задается своей матрицей смежностей; вывести на экран матрицу инцидентности графа. Может я много...

матрица инцидентности - C++
матрица инцидентности задано множество пар вершин, построить матрицу инцидентности как вывести матрицу инцидентности?? ...

Ориентированный граф и матрица инцидентности - C++
Вот у меня есть такое прекрасное задание: Базовый класс: Элемент ориентированного графа. Производные классы: дуга и вершина...

Дана матрица инцидентности, вывести множество пар вершин - C++
есть матрица инцидентности графа, например: //матрица инцидентности 1 1 0 1 0 1 0 1 1 как вывести множество пар вершин из...

Граф задается своей матрицей смежностей вывести на экране окружения каждой его вершины - C++
Привет, ребят! Прошу Очень помочь! Граф задается своей матрицей смежностей. Вывести на экране окружения каждой его вершины. ...

Преобразовать список рёбер в список смежностей - C++
помогите преобразовать список рёбер в список смежностей

11
valeriikozlov
Эксперт С++
4675 / 2501 / 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++;
        }
0
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 10:41  [ТС] #3
а разве можно в динамических массивах использовать обращение к эллементам как в обычных, т.е. у тебя b[i][j] а надо то вроде b[i*n+j]
0
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2010, 10:54 #4
а разве можно в динамических массивах использовать обращение к эллементам как в обычных, т.е. у тебя b[i][j] а надо то вроде b[i*n+j]
можно
0
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();
}
0
valeriikozlov
Эксперт С++
4675 / 2501 / 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] - нельзя
0
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 12:45  [ТС] #7
но с моим кодом все равно идет вывод матрицы с размером [n, col_inc]. на сколько я понимаю new выделяет колво ячеек памяти а delete отказывается от них, т.е. я просто отказался от определенного колва памяти и выделил новое колво, и тот код который написали вы можно ли как то преоброзовать с к моему тоесть обращение чтобы было [i*n+j] или делать только как вы

Добавлено через 25 минут
valeriikozlov или если не сложно расскажите хотя бы принцип вашего алгаритма т.е. из чего исходили при создании
0
valeriikozlov
Эксперт С++
4675 / 2501 / 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();
}
Принцип еще нужен?
1
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
0
valeriikozlov
Эксперт С++
4675 / 2501 / 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
неверный
1
dre
1 / 1 / 0
Регистрация: 01.12.2010
Сообщений: 19
18.12.2010, 14:11  [ТС] #11
спасибо, вы очень помогли. только теперь буду по новому разбираться с этой инцидентностью вчера видать не так понял как её составить((

Добавлено через 7 минут
и последний вопрос, при составлении матрицы инцидентности нумерация ребер должна быть определенной? или произвольной, сейчас прост попробовал с вашей матрицей все правильно, но не пойму почему именно так идет нумерация
0
valeriikozlov
Эксперт С++
4675 / 2501 / 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 единицы,
Кол-во строк соответствует кол-ву ребер в графе. Кол-во столбцов соответствует кол-ву вершин.
1
18.12.2010, 14:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.12.2010, 14:16
Привет! Вот еще темы с ответами:

дана квадратичная матрица z[n][n]. составить программу, которая если матрица симметричная(транспонированная матрица равна исходной), сделает ее не сим - C++
помогите пожалуйста. условие: дана квадратичная матрица z. составить программу, которая если матрица симметричная(транспонированная...

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

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

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


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

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

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