Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.68/19: Рейтинг темы: голосов - 19, средняя оценка - 4.68
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
1

Дана матрица инцидентности, вывести множество пар вершин

24.10.2010, 20:50. Показов 3682. Ответов 24
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
есть матрица инцидентности графа, например:

//матрица инцидентности
1 1 0
1 0 1
0 1 1

как вывести множество пар вершин из этой матрицы и название ребра, то есть:

e1-e2 -1
e1-e3 -2
e2-e3 -3


код C++

C++
1
2
3
4
5
6
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
  cout<<"M["<<i+1<<","<<j+1<<"]: ";                                
  cin>>SMatrix[i][j];
}

как дальше, как реализовать программно (вывод множества пар вершин)?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.10.2010, 20:50
Ответы с готовыми решениями:

Построить множество пар вершин по матрице инцидентности
задано матрицу инцидентности. построить множество пар вершин. как реализовать?? ...

Задано множество пар вершин, построить матрицу инцидентности
матрица инцидентности задано множество пар вершин, построить матрицу инцидентности как...

По множеству пар вершин построить матрицу инцидентности
матрица инцидентности задано множество пар вершин, построить матрицу инцидентности как...

Нужны преобразования: список смежных вершин -> список инцидентных ребер -> матрица инцидентности -> матрица смежности
Нужны такие преобразования: список смежных вершин -&gt; список инцидентных ребер -&gt; матрица...

24
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
24.10.2010, 20:53 2
dibilasd,
C++
1
2
3
4
5
6
std::vector<std::pair<int, int> > VecP;
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin(),
It!=VecP.end(), ++It)
{
    std::cout<<It->first<<'-'<<It->second<<'\n';
}
Например
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 21:01  [ТС] 3
а можно пояснения??
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
24.10.2010, 21:05 4
dibilasd, Ну можно и книжку открыть или инет...

C++
1
2
3
4
5
6
7
8
9
//Объявление вектора пар. Пара - два значения. Стандартная шаблонная структура
std::vector<std::pair<int, int> > VecP;
//Цикл от начала до конца
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin(),
It!=VecP.end(), ++It)
{
//Вывод первого и второго элемента каждой пары.
    std::cout<<It->first<<'-'<<It->second<<'\n';
}
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 22:16  [ТС] 5
а как передать елементы Smatrix в Vecp??
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
24.10.2010, 22:23 6
dibilasd, Smatrix? Це массив стандартных объектов или массив пользовательских (класс, структура) ?
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 22:25  [ТС] 7
це массив (матрица инцидентности)

Добавлено через 53 секунды
int SMatrix [50][50];
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
24.10.2010, 22:32 8
dibilasd, А зачем матрицу инцедентности туда загонять?
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 22:32  [ТС] 9
ну а как вывести множество пар вершин из матрицы инцидентности??
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
24.10.2010, 22:38 10
dibilasd, Смотри...

Есть матрица инцидентности.
Есть вектор пар ребер.
Матрица инцидентности заполненная.
Ребро связано с другим ребром только в том случае, если в матрице на этом месте стоит 1. Верно?
Тогда. Если нам нужно вывести инцидентные ребра, то записываем мы в вектор пар номера одного и другого ребра.

Итак псевдокод.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Matrix[n][n];
std::vector<std::pair<int, int> > VecP;
for(int i=0; i<n; ++i)
{
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1)
           VecP.push_back(std::make_pair<int, int>(i, j));
    }
}
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end();
++It)
{
    std::cout<<It->first<<' '<<It->second<<'\n';
}
1
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 23:06  [ТС] 11
например, если ввести матрицу инцидентности:
1 1 0
1 0 1
0 1 1

получится результат работы программы:
1-1
1-2
2-1
2-3
3-2
3-3

а меня интересует результат типа:
1-2 -1
1-3 -2
2-3 -3

то есть, первые две цифры - это названия вершин, а 3 цифра - это название ребра
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
24.10.2010, 23:20 12
dibilasd, И я так понимаю, что ребро
1-2
2-1

Должно выводится 1 раз?
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 23:26  [ТС] 13
да, один раз
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
24.10.2010, 23:34  [ТС] 14
тобто,
матрица инцидентности:
1 1 0
1 0 1
0 1 1

и потому искомые множества будут такими:

1 - 2 - 1
1 - 3 - 2
2 - 3 - 3
Изображения
 
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
25.10.2010, 00:01 15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Matrix[n][n];
std::vector<std::pair<int, int> > VecP;
std::vector<int> Edges;
int l=0;
for(int i=0; i<n; ++i)
{
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1&&i>=j)
        {
           VecP.push_back(std::make_pair<int, int>(i, j));
           Edges.push_back(l);
           l++;
        }
    }
}
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end();
++It)
{
    std::cout<<It->first<<' '<<It->second<<"Number - "<< l<<'\n';
}
Добавлено через 48 секунд
dibilasd, М. Ща. Кажется неверно понял. Поправлю...
Да... Я неверно просек суть. Не исправлю видимо.

Добавлено через 22 минуты
То, что писал я вполне хорошо подходит для смежности...
1
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:04  [ТС] 16
да и в случае смежности получается тот же результат, ребра выводятся два раза
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
25.10.2010, 00:10 17
Вывод.
1-2
1-3
2-3

И где вывод два раза хоть одного ребра?

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
#include <iostream>
#include <vector>
#include <utility>
 
int main()
{
    const int n=3;
    int Matrix[n][n]={ {0, 1, 1}, {1, 0, 1}, {1, 1, 0} };
std::vector<std::pair<int, int> > VecP;
std::vector<int> Edges;
for(int i=0; i<n; ++i)
{
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1&&j>=i)
        {
           VecP.push_back(std::make_pair<int, int>(i+1, j+1));
        }
    }
}
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end();
++It)
{
    std::cout<<It->first<<' '<<It->second<<'\n';
}
return 0;
}
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:18  [ТС] 18
если ввести матрицу смежности:
0 1 1
1 0 1
1 1 0

должно получиться:
1-2
1-3
2-3
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
25.10.2010, 00:18 19
dibilasd, Ну да. Что и получается.
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:21  [ТС] 20
и получается:
1-2
1-3
2-1
2-3
3-1
3-2
0
25.10.2010, 00:21
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.10.2010, 00:21
Помогаю со студенческими работами здесь

Дана матрица инцидентности. Изобразите граф, ей соответствующий
Дана матрица инцидентности. Изобразите граф, ей соответствующий

Графы. Ввод матрицы смежности, матрица инцидентности и список инцидентности неориентированного графа
Здраствуйте. Помогите пожалуйста, а то вообще не врубаюсь в это. Надо написать процедуры ввода...

Дана строка символов, построить и вывести множество
дана строка символов. требуется построить и вывести множество, элементами которого являются: буквы,...

Из списка смежных вершин получить матрицу инцидентности
Здравствуйте. Подскажите пожалуйста в следующем вопросе. Мне необходимо получить матрицу...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru