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

@ulian · Регистрация: 28.11.2012

Студворк — интернет-сервис помощи студентам

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

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

@ulian · 07.02.2013, 19:42 **[ТС]**

кто-то может помочь?

@palva · 07.02.2013, 20:03

А ребра больше единицы, они что, не подряд идут? Например, возможен такой набор всех ребер графа: 3 6 29 33002

@ulian · 07.02.2013, 20:04 **[ТС]**

да, там имеется в виду начальное и конечное значение вершины, но можно ограничится числами до 100)

@palva · 07.02.2013, 20:15

Вы не ответили на вопрос. У вас написано, что номер вершины больше 1. Значит ли это, что номера вершин идут не подряд, типа 1,2,3,...,15, когда n=15, а в разбивку, так как я написал.

@ulian · 07.02.2013, 20:27 **[ТС]**

они должны идти по-порядку

@palva · 07.02.2013, 20:38

Я пытаюсь понять нужен ли предварительный просмотр номеров. То есть, если я прочитал n=4, то номера вершин не могут быть 1,2,3,4, поскольку они должны быть больше единицы. Может ли оказаться, что номера вершин следующие: 20,21,22,23 ? Или начальный номер обязательно 2?

Тот же вопрос с номерами ребер. Можно ли считать, что их номера 1, 2, ..., m, или их номера тоже должны быть больше единицы?

@ulian · 07.02.2013, 21:43 **[ТС]**

вершин должно быть больше единицы, начиная с 2 и так далее 3,4,5,... до н
ребер же начиная с единицы 1,2,3,... до м
1≤V≤n, 1≤U≤ в таком диапазоне вершины

@palva · 07.02.2013, 22:28

Сообщение от ulian

1≤V≤n, 1≤U≤ в таком диапазоне вершины

Я скоро заплачу! Ну невозможно такое, чтобы вершин было n и их номера находились в диапазоне 1≤V≤n, потому что номеров больших единицы в этом диапазоне всего n-1.

@ulian · 07.02.2013, 22:32 **[ТС]**

не знаю, возможно я не правильно понял задание. Переписал заданиев точную с книги.
1. Считывание графа из входного файла. На вход подается текстовый файл следующего
вид:
n m
v1 u1
v2 u2
....
vm um
Здесь n - количество вершин графа (целое число, больше нуля), m - количество ребер графа
(целое число, больше нуля), vi и ui
* - Начальная и конечная вершина ребра i (1 ≤ vi ≤ n,
1 ≤ ui ≤ n, целые числа). Индексация вершин в файле ведется с 1. Считается, что граф является
ориентированным.
Таким образом можно сказать, что граф задается в файле списком ребер.
Требуется сделать вывод матриц инцидентности и смежности.

@palva · 07.02.2013, 22:36

Сообщение от ulian

(целое число, больше нуля)

А вы сначала написали, что больше единицы. Теперь всё встало на своё место.
Подождите немного, сейчас попробую написать вариант, если никто раньше не напишет.

@ulian · 07.02.2013, 22:37 **[ТС]**

да, спасибо большое.

@palva · 07.02.2013, 23:54

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

outfile.txt

Code
1
2
3
4
5
6
7
8
9
10
11
12
Матрица смежности
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;
}

@ulian · 08.02.2013, 00:32 **[ТС]**

Спасибо вам большое!

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@ulian 0 / 0 / 0 Регистрация: 28.11.2012 Сообщений: 53

	Матрицы инцидентнности и смежности 06.02.2013, 18:38. Показов 3323. Ответов 13 Метки нет (Все метки) Помогите написать программу, на входе дан текстовый файл вида: n m v1 u1 v2 u2 ......... vm um где n - количество вершин графа, m - количество ребер, v и u - начальное и конечное значение ребра(целые числа >1) а на вывод функции должно вывести матрицу инцидентнности и смежную матрицу. Не имеет значение куда, на экран либо в текстовый файл. 0

@ulian 0 / 0 / 0 Регистрация: 28.11.2012 Сообщений: 53
	07.02.2013, 19:42 [ТС]
	кто-то может помочь? 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	07.02.2013, 20:03
	А ребра больше единицы, они что, не подряд идут? Например, возможен такой набор всех ребер графа: 3 6 29 33002 0

@ulian 0 / 0 / 0 Регистрация: 28.11.2012 Сообщений: 53
	07.02.2013, 20:04 [ТС]
	да, там имеется в виду начальное и конечное значение вершины, но можно ограничится числами до 100) 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	07.02.2013, 20:15
	Вы не ответили на вопрос. У вас написано, что номер вершины больше 1. Значит ли это, что номера вершин идут не подряд, типа 1,2,3,...,15, когда n=15, а в разбивку, так как я написал. 0

@ulian 0 / 0 / 0 Регистрация: 28.11.2012 Сообщений: 53
	07.02.2013, 20:27 [ТС]
	они должны идти по-порядку 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	07.02.2013, 20:38
	Я пытаюсь понять нужен ли предварительный просмотр номеров. То есть, если я прочитал 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 [ТС]
	вершин должно быть больше единицы, начиная с 2 и так далее 3,4,5,... до н ребер же начиная с единицы 1,2,3,... до м 1≤V≤n, 1≤U≤ в таком диапазоне вершины 0

@ulian 0 / 0 / 0 Регистрация: 28.11.2012 Сообщений: 53
	07.02.2013, 22:32 [ТС]
	не знаю, возможно я не правильно понял задание. Переписал заданиев точную с книги. 1. Считывание графа из входного файла. На вход подается текстовый файл следующего вид: n m v1 u1 v2 u2 .... vm um Здесь n - количество вершин графа (целое число, больше нуля), m - количество ребер графа (целое число, больше нуля), vi и ui * - Начальная и конечная вершина ребра i (1 ≤ vi ≤ n, 1 ≤ ui ≤ n, целые числа). Индексация вершин в файле ведется с 1. Считается, что граф является ориентированным. Таким образом можно сказать, что граф задается в файле списком ребер. Требуется сделать вывод матриц инцидентности и смежности. 0

@ulian 0 / 0 / 0 Регистрация: 28.11.2012 Сообщений: 53
	07.02.2013, 22:37 [ТС]
	да, спасибо большое. 0

@ulian 0 / 0 / 0 Регистрация: 28.11.2012 Сообщений: 53
	08.02.2013, 00:32 [ТС]
	Спасибо вам большое! 0