@25th_July

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

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

Миниатюры

 

0

@3D Homer

В таком случае нужно смотреть определения в литературе или на заслуживающих доверия сайтах (MathWorld, математическая энциклопедия и т.д.). Было бы интересно увидеть примеры разных определений.

В двух книгах, которые я посмотрел, произведение определяется для неориентированных графов. Я полагаю, что его легко перенести на орграфы. Но ни в одной из книг петли в произведение (ваш пункт 1) автоматически не добавлялись.

Я согласен. Но вы не написали статус матрицы смежности произведения. Может быть, вы сгенерировали его случайным образом.

0

@25th_July

Везде говорится про декартово произведения в множествах, то есть просто про набор пар элементов.
Что значит статус матрицы смежности?
Здесь в примере, котором я нашел, даны матрицы для ориентированных графов. Я просто не могу найти четкого критерия, по которому определять значения элементов матрицы.

0

@3D Homer

Как к вам относиться ввиду следующих фактов?

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

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

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

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

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

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

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

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

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

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

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

Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. - М.: Изд-во МАИ, 1992.

0

@25th_July

Матрица 9х9 была получена так как в теории множеств сказано, что конечная матрица будет размером nxm, где n - размерность первой матрицы, m - второй. Определение в сообщении №1 было действительно придумано мной исходя из приведенного примера( его составлял не я), я написал там фразу "в моем понимании". За список литературы - спасибо. Попробую отыскать там что либо.
Еще по поводу первого пункта вашего последнего сообщения. Декартово произведении множеств - здесь везде все одинаково написано, никаких сомнений нет. Однако, когда дело доходит до применения к графам - начинаются расхождения. Плюс найденный мною пример не соответствует теории, что окончательно сбило меня с толку.

0

Байт

Вот, нарыл определение.
http://pco.iis.nsk.su/WikiGrap... 0%BE%D0%B2

Добавлено через 1 минуту
Не знаю, насколько оно общепринято, и существуют ли другие

0

@3D Homer

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

Определение по ссылке в сообщении №6 действительно взято из книги Оре О. Теория графов, но оно какое-то кривое хотя бы потому, что там используется формула . Здесь и — вершины графа . Даже если оставить в стороне тот факт, что граф отождествляется с множеством ребер, как понимать, что упорядоченная пара является подмножеством?

Я не специалист в теории графов, но, мне кажется, правильное определение декартова произведения есть в Википедии. Именно согласно этому определению n-мерный куб есть произведение отрезков . Оно такое же, как в книгах Емеличев и др., Харари, а также в Судоплатов С.В., Овчинникова Е. В. Элементы дискретной математики (2003). В книге Кузнецова и Адельсон-Вельского приведены три определения прямого произведения, из которых ни одно не совпадает с определением декартова произведения в Википедии. Так что ТС прав: определения сильно различаются.

1

@25th_July

Думаю буду прилерживаться определения википедии при реализации. Оно как мне кажется наиболее логичное. Спасибо за ответ!
P.S. А вообще было бы интересно узнать мнение какого-нибудь прям математика, так как все таки вопрос нельзя считать полностью решенным

0