Форум программистов, компьютерный форум, киберфорум
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
1 / 1 / 0
Регистрация: 06.04.2015
Сообщений: 10
1

Как преобразовать неориентированный граф в ориентированный граф из матричной записи

06.12.2015, 00:37. Просмотров 2538. Ответов 3
Метки нет (Все метки)

Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из матричной записи?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.12.2015, 00:37
Ответы с готовыми решениями:

Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством пересечений
Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством...

Python 2.7. Как удобнее всего реализовать ориентированный граф со сложными весами?
Нужно работать с графом, содержащим во многих вершинах и ребрах набор разнотипных значений....

Неориентированный граф
Есть такое задание "Реализация АТД « Неориентированный граф» через класс. Граф представлен в виде...

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

3
Эксперт по математике/физике
4138 / 2043 / 420
Регистрация: 19.07.2009
Сообщений: 3,097
Записей в блоге: 23
06.12.2015, 00:44 2
Пусть A — матрица смежности орграфа.
https://www.cyberforum.ru/cgi-bin/latex.cgi?A' = A + A^T
Правда, иногда будут появляться "2" в матрице смежности неорграфа A', но их нужно понимать как «ребро есть».
Кстати, если под «+» понимать не обычное вложение чисел, а OR (дизъюнкцию), то формула работает без дополнительных оговорок.
1
1 / 1 / 0
Регистрация: 06.04.2015
Сообщений: 10
06.12.2015, 01:19  [ТС] 3
AT что значит?

Добавлено через 5 минут
Mysterious Light, AT что значит?

Добавлено через 21 минуту
Mysterious Light, не выходит, матрица остается симетричной
0
Эксперт по математике/физике
4138 / 2043 / 420
Регистрация: 19.07.2009
Сообщений: 3,097
Записей в блоге: 23
06.12.2015, 12:14 4
Ой, простите, неправально прочитал условие)

Нужно неориентированный граф преобразовать в ориентированый. Вообще, странная постановка задачи, нужны уточнение, что именно хочется получить.

Вообще-то всякий неориентированный граф может мыслиться как частный случай ориентированного, когда между двумя вершинами A и B либо нет никаких дуг, либо есть в точности две дуги. И симметричная матрица как раз задаваёт орграф.

Другой вариант задачи: нужно из матрицы A получить антиссиметричную матрицу A'. Строго говоря, такая задача неоднозначна в решении. К примеру, для полного графа с n вершинами существует ровно https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{\frac{n(n-1)}2} антисимметричных таких орграфов. Как вариант, можно у матрицы A занулись верхний или нижный треугольник (над/под главной диагональню), сделав таким образом нижне- или верхнетреугольную матрицу A' антисимметричного орграфа.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.12.2015, 12:14

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

Неориентированный граф
Никогда с WinApi не работал с графами, прошу помощи по задаче. Дан неориентированный связанный...

Неориентированный граф!!!
Еще раз обращаюсь за помощью к форуму..от этих задач зависит стипендия! Помогите пожалуйста! ...

Неориентированный граф
Доказать, что неориентированный граф с n вершинами содержит по крайней мере n-1 ребер. Кто знает...

Неориентированный граф
Здравствуйте. Хотелось бы разобраться с представлением частично-упорядоченных множеств в виде...

Неориентированный граф
Неориентированный граф представляет собой схему встреч между людьми.После ввода графа...

Неориентированный граф
Условие Найти эйлеров цикл в неориентированном графе. Граф состоит из N вершин, пронумерованных...


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

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

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