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

@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' антисимметричного орграфа.

Блоги программистов
Подброка решений задач на Python IT_Exp 06.01.2025 Целью данной подборки является предоставление возможности ознакомиться с различными задачами и их решениями на Python, что может быть полезно как для начинающих, так и для опытных программистов. . . .	С чего начать программировать микроконтроллеры raxper 06.01.2025 Введение в мир микроконтроллеров Микроконтроллеры стали неотъемлемой частью современного мира, окружая нас повсюду: от простых бытовых приборов до сложных промышленных систем. Эти маленькие. . .	Из чего собрать игровой компьютер inter-admin 06.01.2025 Сборка игрового компьютера требует особого внимания к выбору комплектующих и их совместимости. Правильно собранный игровой ПК не только обеспечивает комфортный геймплей в современных играх, но и. . .	Обновление сайта www.historian.by Reglage 05.01.2025 Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .	Как использовать GraphQL в C# с HotChocolate Programming 05.01.2025 GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .	Модель полного двоичного сумматора с помощью логических операций (python) AlexSky-coder 04.01.2025 def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()
Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом задержки). Hrethgir 04.01.2025 Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .	Руководство по созданию бота для Телеграм на Python IT_Exp 04.01.2025 Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .	Применение компонентов PrimeVue в Vue.js 3 на TypeScript BasicMan 04.01.2025 Введение в PrimeVue и настройка окружения PrimeVue представляет собой мощную библиотеку компонентов пользовательского интерфейса для Vue. js 3, которая предоставляет разработчикам богатый набор. . .	Как стать Senior developer cpp_developer 04.01.2025 В современной индустрии разработки программного обеспечения позиция Senior Developer представляет собой не просто следующую ступень карьерной лестницы, а качественно новый уровень профессионального. . .	Что известно о дате выхода Windows 12 и чего от нее ждать IT_Exp 04.01.2025 В мире технологий постоянно происходят изменения, и операционные системы не являются исключением. Windows 11, выпущенная в октябре 2021 года, принесла множество инноваций и улучшений, но. . .	Что новенького в .NET Core 9 Programming 04.01.2025 Обзор ключевых изменений в . NET Core 9 Платформа . NET Core продолжает активно развиваться, и версия 9 представляет собой значительный шаг вперед в эволюции этой технологии. Новый релиз. . .

@Tanker6789 1 / 1 / 0 Регистрация: 06.04.2015 Сообщений: 10
		1
	Как преобразовать неориентированный граф в ориентированный граф из матричной записи 06.12.2015, 00:37. Показов 5765. Ответов 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