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

@Tanker6789 · Регистрация: 06.04.2015

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

Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из матричной записи?

@Mysterious Light · 06.12.2015, 00:44

Пусть A — матрица смежности орграфа.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A' = A + A^T$
Правда, иногда будут появляться "2" в матрице смежности неорграфа A', но их нужно понимать как «ребро есть».
Кстати, если под «+» понимать не обычное вложение чисел, а OR (дизъюнкцию), то формула работает без дополнительных оговорок.

@Tanker6789 · 06.12.2015, 01:19 **[ТС]**

A^T что значит?

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

Добавлено через 21 минуту
Mysterious Light, не выходит, матрица остается симетричной

@Mysterious Light · 06.12.2015, 12:14

Ой, простите, неправально прочитал условие)

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

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

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

@Tanker6789 1 / 1 / 0 Регистрация: 06.04.2015 Сообщений: 10
		1
	Как преобразовать неориентированный граф в ориентированный граф из матричной записи 06.12.2015, 00:37. Показов 5707. Ответов 3 Метки нет (Все метки) Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из матричной записи? 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	06.12.2015, 00:44	2
	Пусть A — матрица смежности орграфа. $https://www.cyberforum.ru/cgi-bin/latex.cgi?A' = A + A^T$ Правда, иногда будут появляться "2" в матрице смежности неорграфа A', но их нужно понимать как «ребро есть». Кстати, если под «+» понимать не обычное вложение чисел, а OR (дизъюнкцию), то формула работает без дополнительных оговорок. 1

@Tanker6789 1 / 1 / 0 Регистрация: 06.04.2015 Сообщений: 10
	06.12.2015, 01:19 [ТС]	3
	A^T что значит? Добавлено через 5 минут Mysterious Light, A^T что значит? Добавлено через 21 минуту Mysterious Light, не выходит, матрица остается симетричной 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	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

Опции темы