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

Матрицы инцидентнности и смежности

06.02.2013, 18:38. Показов 3045. Ответов 13
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите написать программу, на входе дан текстовый файл вида:
n m
v1 u1
v2 u2
.........
vm um
где n - количество вершин графа, m - количество ребер, v и u - начальное и конечное значение ребра(целые числа >1)

а на вывод функции должно вывести матрицу инцидентнности и смежную матрицу. Не имеет значение куда, на экран либо в текстовый файл.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.02.2013, 18:38
Ответы с готовыми решениями:

Генерация матрицы смежности
написал код: #include <cstdlib> #include <iostream> #include <math.h> using namespace std; ...

Построение матрицы смежности
Задаем поле с единицами и нулями (где 1-пустая клетка, 0-препятствие) #include "stdafx.h"...

Из матрицы смежности сделать ориентированный граф
Какаю библиотеку использовать что би нарисовать граф?Возможно есть готов код ,буду очень...

Построение матрицы смежности
Доброго всем времени суток! Была когда-то на форуме такая тема Построение матрицы смежности И вот...

13
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 19:42  [ТС] 2
кто-то может помочь?
0
4240 / 2937 / 687
Регистрация: 08.06.2007
Сообщений: 9,817
Записей в блоге: 4
07.02.2013, 20:03 3
А ребра больше единицы, они что, не подряд идут? Например, возможен такой набор всех ребер графа: 3 6 29 33002
0
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 20:04  [ТС] 4
да, там имеется в виду начальное и конечное значение вершины, но можно ограничится числами до 100)
0
4240 / 2937 / 687
Регистрация: 08.06.2007
Сообщений: 9,817
Записей в блоге: 4
07.02.2013, 20:15 5
Вы не ответили на вопрос. У вас написано, что номер вершины больше 1. Значит ли это, что номера вершин идут не подряд, типа 1,2,3,...,15, когда n=15, а в разбивку, так как я написал.
0
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 20:27  [ТС] 6
они должны идти по-порядку
0
4240 / 2937 / 687
Регистрация: 08.06.2007
Сообщений: 9,817
Записей в блоге: 4
07.02.2013, 20:38 7
Я пытаюсь понять нужен ли предварительный просмотр номеров. То есть, если я прочитал n=4, то номера вершин не могут быть 1,2,3,4, поскольку они должны быть больше единицы. Может ли оказаться, что номера вершин следующие: 20,21,22,23 ? Или начальный номер обязательно 2?

Тот же вопрос с номерами ребер. Можно ли считать, что их номера 1, 2, ..., m, или их номера тоже должны быть больше единицы?
0
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 21:43  [ТС] 8
вершин должно быть больше единицы, начиная с 2 и так далее 3,4,5,... до н
ребер же начиная с единицы 1,2,3,... до м
1≤V≤n, 1≤U≤ в таком диапазоне вершины
0
4240 / 2937 / 687
Регистрация: 08.06.2007
Сообщений: 9,817
Записей в блоге: 4
07.02.2013, 22:28 9
Цитата Сообщение от ulian Посмотреть сообщение
1≤V≤n, 1≤U≤ в таком диапазоне вершины
Я скоро заплачу! Ну невозможно такое, чтобы вершин было n и их номера находились в диапазоне 1≤V≤n, потому что номеров больших единицы в этом диапазоне всего n-1.
0
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 22:32  [ТС] 10
не знаю, возможно я не правильно понял задание. Переписал заданиев точную с книги.
1. Считывание графа из входного файла. На вход подается текстовый файл следующего
вид:
n m
v1 u1
v2 u2
....
vm um
Здесь n - количество вершин графа (целое число, больше нуля), m - количество ребер графа
(целое число, больше нуля), vi и ui
* - Начальная и конечная вершина ребра i (1 ≤ vi ≤ n,
1 ≤ ui ≤ n, целые числа). Индексация вершин в файле ведется с 1. Считается, что граф является
ориентированным.
Таким образом можно сказать, что граф задается в файле списком ребер.
Требуется сделать вывод матриц инцидентности и смежности.
0
4240 / 2937 / 687
Регистрация: 08.06.2007
Сообщений: 9,817
Записей в блоге: 4
07.02.2013, 22:36 11
Цитата Сообщение от ulian Посмотреть сообщение
(целое число, больше нуля)
А вы сначала написали, что больше единицы. Теперь всё встало на своё место.
Подождите немного, сейчас попробую написать вариант, если никто раньше не напишет.
0
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 22:37  [ТС] 12
да, спасибо большое.
0
4240 / 2937 / 687
Регистрация: 08.06.2007
Сообщений: 9,817
Записей в блоге: 4
07.02.2013, 23:54 13
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
#include <fstream>
 
using namespace std;
 
int main()
{
    int n, m, i1, i2, i, j;
    ifstream inf("infile.txt");
    ofstream outf("outfile.txt");
    inf >> n >> m;
    char *a, *b;
    a=new char[n*n];
    for(i=0; i<n*n; i++) a[i]='0';
    b=new char[n*m];
    for(i=0; i<n*m; i++) b[i]='0';
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]='1';
        a[(i2-1)*n+i1-1]='1';
        b[(i1-1)*m+i]='1';
        b[(i2-1)*m+i]='1';
    }
    outf << "Матрица смежности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) outf << a[i*n+j] << ' ';
        outf << '\n';
    }
    outf << "Матрица инцидентности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++) outf << b[i*m+j] << ' ';
        outf << '\n';
    }
    delete a;
    delete b;
    return 0;
}
infile.txt
Код
5 7
1 2
2 3
3 4
4 5
5 1
1 3
2 4
outfile.txt
Код
Матрица смежности
0 1 1 0 1 
1 0 1 1 0 
1 1 0 1 0 
0 1 1 0 1 
1 0 0 1 0 
Матрица инцидентности
1 0 0 0 1 1 0 
1 1 0 0 0 0 1 
0 1 1 0 0 1 0 
0 0 1 1 0 0 1 
0 0 0 1 1 0 0
Добавлено через 14 минут
Извините, сейчас еще раз прочитал задачу и увидел, что граф ориентированный. Тогда нужно внести следующие исправления в программу. центральный цикл
C++
1
2
3
4
5
6
7
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]='1';
        a[(i2-1)*n+i1-1]='1';
        b[(i1-1)*m+i]='1';
        b[(i2-1)*m+i]='1';
    }
надо заменить на
C++
1
2
3
4
5
6
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]='1';
        b[(i1-1)*m+i]='-';
        b[(i2-1)*m+i]='+';
    }
Добавлено через 22 минуты
Еще одна версия. Теперь поддерживаются кратные ребра
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
#include <fstream>
#include <iomanip>
 
using namespace std;
 
int main()
{
    int n, m, i1, i2, i, j;
    ifstream inf("infile.txt");
    ofstream outf("outfile.txt");
    inf >> n >> m;
    int *a, *b;
    a=new int[n*n];
    for(i=0; i<n*n; i++) a[i]=0;
    b=new int[n*m];
    for(i=0; i<n*m; i++) b[i]=0;
    for(i=0; i<m; i++) {
        inf >> i1 >> i2;
        a[(i1-1)*n+i2-1]++;
        b[(i1-1)*m+i]--;
        b[(i2-1)*m+i]++;
    }
    outf << "Матрица смежности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) outf << a[i*n+j] << ' ';
        outf << '\n';
    }
    outf << "Матрица инцидентности\n";
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++) outf << setw(3) << b[i*m+j];
        outf << '\n';
    }
    delete a;
    delete b;
    return 0;
}
2
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
08.02.2013, 00:32  [ТС] 14
Спасибо вам большое!
0
08.02.2013, 00:32
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.02.2013, 00:32
Помогаю со студенческими работами здесь

Объединить матрицы смежности
помогите, в стринггрид (2 шт.) задаются матрицы, в третью вывести результатную матрицу, но только...

Вывод матрицы смежности
Помогите с выводом матрицы смежности. Мой код : begin for a := Low(vershini) to...

Списки смежности из матрицы
Здравствуйте,помогите пожалуйста написать программу,спасибо.Напишите программу, которая строит...

Построение матрицы смежности.
Условие: Внутрь квадрата с координатами левого нижнего угла (0,0) и координатами верхнего правого...


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

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