2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
|
||||||||||||||||
1 | ||||||||||||||||
Графы: матрицы соединений и матрицы связей08.01.2014, 20:00. Показов 3326. Ответов 7
Метки нет (Все метки)
Графом называется совокупность точек ( узлов), некоторые из которых соединены между собой направленными ребрами. Граф , состоящий из n узлов можно описать двумя матрицами порядка n : матрицей соединений и матрицей связей. Элемент матрицы соединений a[i,j] = 1, если граф содержит ребро направлено от узла i к узлу j и a[i,j] = 0 в другом случае . Элемент матрицы связей b[i,j] = 1, если с узла i можно попасть в узел j , двигаясь по ребрам и b[i,j] = 0 в другом случае .
Задача : ввести количество узлов некоторого графа. Задав произвольно матрицу соединений ( в интерактивном режиме или случайным образом ) , построить матрицу связей для этого графу . Предусмотреть графическое отображение такого графа и числовой вывод обеих матриц . Я реализовал генерацию/ручной ввод матрицы соединений, и немножко написал о матрицы связей, но не могу правильно задать алгоритм для ее создания. Прошу помочь, и так же подсказать как сделать графическое отображение такого графа. Написан мной код привожу:
0
|
08.01.2014, 20:00 | |
Ответы с готовыми решениями:
7
Лабиринт для матрицы соединений Дана матрица соединений некоторой сети из n узлов; получить матрицу связей этой сети Графы: перевод матрицы инцидентности в список ребер Матрицы. Найти и распечатать сумму элементов 5-го столбца матрицы А и сумму элементов последней строки матрицы В |
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
|
|
08.01.2014, 21:10 | 2 |
Можно с помощью поиска в глубину/в ширину реализовать.
1
|
2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
|
|
08.01.2014, 21:13 [ТС] | 3 |
поподробней.
Я должен анализировать первую матрицу, и на ее основе сделать другую. А как это сделать с помощью поисков?
0
|
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
|
|
08.01.2014, 21:34 | 4 |
Каждая строка матрицы связей будет создана с помощью одного прохода алгоритмом.
С помощью алгоритма поиска в ширину помечаем вершины, связанные с i-ой. Создаем массив, заполненный нулями, кроме i-ого элемента - вершины, с которой начинается поиск(ее помечаем 1). Для всех смежных вершин с вершинами, которые помечены 1, в массив ставим 2. На следующем шаге помечаем 3 все смежные вершины с такими, которые помечены 2. И т.д., пока на каком-либо шаге не найдется смежных вершин. В матрицу связей записываем ноль, если в массиве записан ноль, если что-то другое - записываем единицу.
1
|
2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
|
|
08.01.2014, 21:41 [ТС] | 5 |
хм спасибо, попробую вникнуть в суть.
а после построения другой матрицы, не подскажете как вывести сам граф?
0
|
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
|
|
08.01.2014, 21:52 | 6 |
А что значит "графическое отображение графа" ? Я, честно говоря, не представляю, как его можно отобразить в консоли.
0
|
2354 / 1772 / 212
Регистрация: 07.01.2011
Сообщений: 10,342
|
|
08.01.2014, 22:24 [ТС] | 7 |
а если например это сделать на С#, не через консоль, а через GUI.
С помощью чего это можно реализовать?
0
|
162 / 162 / 42
Регистрация: 29.05.2010
Сообщений: 435
|
|
08.01.2014, 22:35 | 8 |
Ну самый простой вариант - это разместить вершины графа на окружности (поделить 360 на количество вершин, с помощью формул переходить от полярной системы координат к декартовой). Ну и соединять вершины ребрами, где надо.
1
|
08.01.2014, 22:35 | |
08.01.2014, 22:35 | |
Помогаю со студенческими работами здесь
8
Зеркально отразить элементы матрицы относительно горизонтальной оси симметрии матрицы Вычесть из элементов первого столбца матрицы значение максимального элемента матрицы Разделить все элементы матрицы на максимальный по абсолютной величине элемент матрицы Поменять большие элементы в строке матрицы с маленькими элементами этой же матрицы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |