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

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

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

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

//матрица инцидентности
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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
24.10.2010, 20:50
Ответы с готовыми решениями:

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

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

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

24
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
25.10.2010, 00:22
Студворк — интернет-сервис помощи студентам
А по инцидентности...

У нас по строкам идут вершины, по столбцам ребра или наоборот?

Вообщем если чисто теоретически, тот код надо переделать не особо сильно.
Надо просто проверять какие вершины инцидентны данному ребру в матрице, записывать их номера в вектор пар + записывать в вектор ребер - номер этого ребра. Выводить собственно понятно как.

Добавлено через 29 секунд
dibilasd, Нет. Получается
1-2
1-3
2-3
Я как бэ поправил код. Еще раз попробуйте
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:23  [ТС]
ну так что, с матрицей инцидентности идей нет?
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
25.10.2010, 00:23
dibilasd, Читайте выше ТТ.
0
0 / 0 / 0
Регистрация: 03.11.2009
Сообщений: 14
25.10.2010, 00:28  [ТС]
вершины идут по столбцам, а названия ребер по строкам
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
25.10.2010, 01:05
Ага?

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
#include <iostream>
#include <vector>
#include <utility>
 
int main()
{
    const int n=3;
    int Matrix[n][n]={ {1, 1, 0}, {1, 0, 1}, {0, 1, 1} };
std::vector<std::pair<int, int> > VecP;
std::vector<int> Edges;
for(int i=0; i<n; ++i)
{
    int cnt=0, temp;
    for(int j=0; j<n; ++j)
    {
        if(Matrix[i][j]==1)
        {
           if(cnt==0)
              temp=j;
           cnt++;
        }
        if(cnt==2)
        {
            VecP.push_back(std::make_pair<int, int>(temp+1, j+1));
            Edges.push_back(i+1);
            break;
        }
    }
}
std::vector<int>::const_iterator Iter=Edges.begin();
for(std::vector<std::pair<int, int> >::const_iterator It=VecP.begin();
It!=VecP.end(), Iter!=Edges.end();
++It, ++Iter)
{
    std::cout<<It->first<<'-'<<It->second<<' '<<*Iter<<'\n';
}
return 0;
}
Добавлено через 25 минут
Хотя пожалуй так можно избежать лишних проверок уникальности вершин в ребрах.

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
#include <iostream>
#include <vector>
#include <utility>
#include <set>
 
int main()
{
    const int n=3;
    int Matrix[n][n]={ {1, 1, 0}, {1, 0, 1}, {0, 1, 1} };
    std::set<std::pair<int, int> > VecP;
    std::vector<int> Edges;
    for(int i=0; i<n; ++i)
    {
        int cnt=0, temp;
        for(int j=0; j<n; ++j)
        {
            if(Matrix[i][j]==1)
            {
                if(cnt==0)
                    temp=j;
                cnt++;
            }
            if(cnt==2)
            {
                VecP.insert(std::make_pair<int, int>(temp+1, j+1));
                Edges.push_back(i+1);
                break;
            }
        }
    }
    std::vector<int>::const_iterator Iter=Edges.begin();
    for(std::set<std::pair<int, int> >::const_iterator It=VecP.begin();
    It!=VecP.end();
    ++It, ++Iter)
    {
        std::cout<<It->first<<'-'<<It->second<<' '<<*Iter<<'\n';
    }
    return 0;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
25.10.2010, 01:05

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
25
Ответ Создать тему
Новые блоги и статьи
Очистка реквизитов и табличных частей документа при копировании
Maks 26.07.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил
anaschu 25.07.2026
две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад).
Hrethgir 24.07.2026
В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .
Вот представьте что вам дали бессмертие.
kumehtar 24.07.2026
Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .
сукцессия 41
anaschu 24.07.2026
Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS | Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1.
anaschu 24.07.2026
Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем **Полевые заметки о двухнедельной совместной работе**. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru