Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
#1

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

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

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

а на вывод функции должно вывести матрицу инцидентнности и смежную матрицу. Не имеет значение куда, на экран либо в текстовый файл.

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2013, 18:38
Ответы с готовыми решениями:

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

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

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

Как из матрицы смежности получить матрицу инцидентности?
Здравствуйте. Можно ли из матрицы смежности получить матрицу инцидентности?...

Граф в виде матрицы смежности и количества вершин
Переписывайте тексты в тело сообщения!!!! Всем здравствуйте. Помогите доделать...

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

Тот же вопрос с номерами ребер. Можно ли считать, что их номера 1, 2, ..., m, или их номера тоже должны быть больше единицы?
0
ulian
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
palva
3097 / 2231 / 448
Регистрация: 08.06.2007
Сообщений: 8,129
Записей в блоге: 4
07.02.2013, 22:28 #9
Цитата Сообщение от ulian Посмотреть сообщение
1≤V≤n, 1≤U≤ в таком диапазоне вершины
Я скоро заплачу! Ну невозможно такое, чтобы вершин было n и их номера находились в диапазоне 1≤V≤n, потому что номеров больших единицы в этом диапазоне всего n-1.
0
ulian
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
palva
3097 / 2231 / 448
Регистрация: 08.06.2007
Сообщений: 8,129
Записей в блоге: 4
07.02.2013, 22:36 #11
Цитата Сообщение от ulian Посмотреть сообщение
(целое число, больше нуля)
А вы сначала написали, что больше единицы. Теперь всё встало на своё место.
Подождите немного, сейчас попробую написать вариант, если никто раньше не напишет.
0
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
07.02.2013, 22:37  [ТС] #12
да, спасибо большое.
0
palva
3097 / 2231 / 448
Регистрация: 08.06.2007
Сообщений: 8,129
Записей в блоге: 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
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
08.02.2013, 00:32  [ТС] #14
Спасибо вам большое!
0
08.02.2013, 00:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2013, 00:32

Реализация матрицы смежности и инцидентности, поиск циклов в графе
Здравствуйте. Есть программа, выводящая матрицу смежности и инцидентности....

Программа завершается при большом размере матрицы смежности
Добрый день! Прошу помощи по решению проблемы. В общем я пишу программу для...

Определение матрицы смежности графа по заданной матрице инцидентности
Доброй ночи :) Изучаю графы, написал фукнцию для конвертации матрицы...


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

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

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