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

Декартово произведение графов

03.03.2017, 10:13. Показов 11287. Ответов 7
Метки нет (Все метки)

Объясните пожалуйста декартово произведение графов(маленький пример). Перелопатил инет, расходятся определения везде. С размерностью результирующей матрицы все ясно, а вот как получить элементы никак не могу понять.
Нашел вот один пример для орграфа, но по мне так он неверен

В моем понимании 1 ставится:
1) если оба элемента совпадают (x1y1; x1y1),
2)если один совпадает а второе ребро существует (x1y2; x1y1)
Но тогда как я писал выше данный пример решения неверен.
Например элемент матрицы (x1y2; x1y1) я бы сделал 1, а не 0, т.к ребро у2->у1 существует, а x1 и в том и в том элементе.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Миниатюры
Декартово произведение графов  
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.03.2017, 10:13
Ответы с готовыми решениями:

Декартово произведение графов.
Решить

Декартово произведение графов
Помогите, пожалуйста, умножить графы

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

Произведение графов
Объясните, пожалуйста, как перемножить эти графы? Определение знаю - что каждой вершине х первого...

7
Эксперт по математике/физике
3431 / 2435 / 795
Регистрация: 01.09.2014
Сообщений: 6,619
03.03.2017, 19:10 2
Цитата Сообщение от 25th_July Посмотреть сообщение
Перелопатил инет, расходятся определения везде.
В таком случае нужно смотреть определения в литературе или на заслуживающих доверия сайтах (MathWorld, математическая энциклопедия и т.д.). Было бы интересно увидеть примеры разных определений.

Цитата Сообщение от 25th_July Посмотреть сообщение
В моем понимании 1 ставится:
1) если оба элемента совпадают (x1y1; x1y1),
2)если один совпадает а второе ребро существует (x1y2; x1y1)
В двух книгах, которые я посмотрел, произведение определяется для неориентированных графов. Я полагаю, что его легко перенести на орграфы. Но ни в одной из книг петли в произведение (ваш пункт 1) автоматически не добавлялись.

Цитата Сообщение от 25th_July Посмотреть сообщение
Но тогда как я писал выше данный пример решения неверен.
Например элемент матрицы (x1y2; x1y1) я бы сделал 1, а не 0, т.к ребро у2->у1 существует, а x1 и в том и в том элементе.
Я согласен. Но вы не написали статус матрицы смежности произведения. Может быть, вы сгенерировали его случайным образом.
0
0 / 0 / 1
Регистрация: 01.03.2017
Сообщений: 32
03.03.2017, 21:49  [ТС] 3
Везде говорится про декартово произведения в множествах, то есть просто про набор пар элементов.
Что значит статус матрицы смежности?
Здесь в примере, котором я нашел, даны матрицы для ориентированных графов. Я просто не могу найти четкого критерия, по которому определять значения элементов матрицы.
0
Эксперт по математике/физике
3431 / 2435 / 795
Регистрация: 01.09.2014
Сообщений: 6,619
03.03.2017, 22:10 4
Цитата Сообщение от 25th_July Посмотреть сообщение
Перелопатил инет, расходятся определения везде.
Цитата Сообщение от 25th_July Посмотреть сообщение
Везде говорится про декартово произведения в множествах, то есть просто про набор пар элементов.
Как к вам относиться ввиду следующих фактов?

1) Сначала вы говорите, что определения расходятся, что подразумевает, что вы все-таки нашли определения требуемого понятия, то есть декартова произведения орграфов.

2) Потом вы говорите, что вы нашли только определение декартова произведения множеств.

А если вы нашли только определения произведения множеств, значит, определение в сообщении №1 вы придумали? И где вы нашли различные определения произведения множеств?

Цитата Сообщение от 25th_July Посмотреть сообщение
Что значит статус матрицы смежности?
В сообщении №1 вы привели матрицу 9x9, но не сказали, откуда ее взяли. Насколько я знаю, вы могли заполнить ее случайными числами.

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

Харари Ф. Теория графов. – М.: Мир, 1973.

Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.

Берж К. Теория графов и ее применения. – М.: Изд. иностр. лит., 1962.

Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2001.

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. 2-е изд., переработанное и дополненное.

Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. - М.: Изд-во МАИ, 1992.
0
0 / 0 / 1
Регистрация: 01.03.2017
Сообщений: 32
03.03.2017, 23:19  [ТС] 5
Матрица 9х9 была получена так как в теории множеств сказано, что конечная матрица будет размером nxm, где n - размерность первой матрицы, m - второй. Определение в сообщении №1 было действительно придумано мной исходя из приведенного примера( его составлял не я), я написал там фразу "в моем понимании". За список литературы - спасибо. Попробую отыскать там что либо.
Еще по поводу первого пункта вашего последнего сообщения. Декартово произведении множеств - здесь везде все одинаково написано, никаких сомнений нет. Однако, когда дело доходит до применения к графам - начинаются расхождения. Плюс найденный мною пример не соответствует теории, что окончательно сбило меня с толку.
0
Эксперт C
25944 / 16160 / 3466
Регистрация: 24.12.2010
Сообщений: 35,356
03.03.2017, 23:26 6
Вот, нарыл определение.
http://pco.iis.nsk.su/WikiGrap... 0%BE%D0%B2

Добавлено через 1 минуту
Не знаю, насколько оно общепринято, и существуют ли другие
0
Эксперт по математике/физике
3431 / 2435 / 795
Регистрация: 01.09.2014
Сообщений: 6,619
04.03.2017, 00:33 7
Лучший ответ Сообщение было отмечено 25th_July как решение

Решение

25th_July, rогда я вас спрашивал про статус матрицы, я имел в виду вопрос, насколько можно ей доверять. Насколько уважаемый сайт, откуда она взята? Как я сказал, я согласен, что ребро (x1y2; x1y1) должно быть в декартовом произведении, поэтому этот пример не вызывает доверия.

Определение по ссылке в сообщении №6 действительно взято из книги Оре О. Теория графов, но оно какое-то кривое хотя бы потому, что там используется формула https://www.cyberforum.ru/cgi-bin/latex.cgi?(v_1,w_1)\subset H_1. Здесь https://www.cyberforum.ru/cgi-bin/latex.cgi?v_1 и https://www.cyberforum.ru/cgi-bin/latex.cgi?w_1 — вершины графа https://www.cyberforum.ru/cgi-bin/latex.cgi?H_1. Даже если оставить в стороне тот факт, что граф отождествляется с множеством ребер, как понимать, что упорядоченная пара https://www.cyberforum.ru/cgi-bin/latex.cgi?(v_1,w_1) является подмножеством?

Я не специалист в теории графов, но, мне кажется, правильное определение декартова произведения есть в Википедии. Именно согласно этому определению n-мерный куб есть произведение отрезков https://www.cyberforum.ru/cgi-bin/latex.cgi?K_2. Оно такое же, как в книгах Емеличев и др., Харари, а также в Судоплатов С.В., Овчинникова Е. В. Элементы дискретной математики (2003). В книге Кузнецова и Адельсон-Вельского приведены три определения прямого произведения, из которых ни одно не совпадает с определением декартова произведения в Википедии. Так что ТС прав: определения сильно различаются.
1
0 / 0 / 1
Регистрация: 01.03.2017
Сообщений: 32
04.03.2017, 11:03  [ТС] 8
Думаю буду прилерживаться определения википедии при реализации. Оно как мне кажется наиболее логичное. Спасибо за ответ!
P.S. А вообще было бы интересно узнать мнение какого-нибудь прям математика, так как все таки вопрос нельзя считать полностью решенным
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.03.2017, 11:03

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Построить пересечение, объединение и произведение графов.
У меня контрольная в универе: И такая задача: Для графов G1 и G2 найти: G1^G2;G1vG2;G1xG2 Я...

Декартово произведение
Если есть некоторое множество элементов и мне надо вычислить количество подмножеств данного...

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

Декартово произведение
Добрый день помогите разобраться с задачей. " Вычислить координаты всех восьми соседей заданной...


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

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

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