Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Изоморфизм графов
СообщениеДобавлено: 06 июн 2014, 19:25 
Не в сети
Продвинутый
Зарегистрирован:
26 дек 2013, 16:33
Сообщений: 60
Cпасибо сказано: 18
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Ребят, как проверить изоморфизм двух графов? Составил матрицу смежности, а дальше?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Изоморфизм графов
СообщениеДобавлено: 06 июн 2014, 20:01 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Изоморфизм графов, ЕМНИП, NP-задача, м.б. даже NP-полная (погуглите, для уточнения). Соотв-но, алгоритмы все будут неэффективные, похожие на переборные.

В качестве очевидной эвристики можете использовать тот факт, что при изоморфизме степень вершины остается постоянной.

Ну и гуглите. Попробуйте в Зыкове поискать конкретные алгоритмы, в Харари, в Берхсе, в Кристофидесе и т.п.

Начните с Вики и с указанной литературы:
http://ru.wikipedia.org/wiki/%D0%98%D0% ... 0%BE%D0%B2
Ыыы! Пишут, что неизвестно, NP-полная или нет.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Изоморфизм графов
СообщениеДобавлено: 07 июн 2014, 08:15 
Не в сети
Продвинутый
Зарегистрирован:
26 дек 2013, 16:33
Сообщений: 60
Cпасибо сказано: 18
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Гуглил, искал. Я хотел услышать, конкретный пример применения на практике

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Изоморфизм графов
СообщениеДобавлено: 07 июн 2014, 10:46 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
На практике используется для шифрования данных банковских карточек. Детально, к сожалению, не знаю.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Почему графов с семью вершинами меньше чем графов с шестью?

в форуме Дискретная математика, Теория множеств и Логика

ivanirkutov

2

278

13 сен 2018, 05:47

Изоморфизм полей

в форуме Линейная и Абстрактная алгебра

Logic_is_dead

2

643

23 апр 2014, 03:26

Построить изоморфизм

в форуме Линейная и Абстрактная алгебра

H0las

0

509

27 дек 2015, 09:45

Показать изоморфизм

в форуме Дискретная математика, Теория множеств и Логика

K1b0rg

0

170

02 июл 2019, 22:39

Доказать изоморфизм

в форуме Линейная и Абстрактная алгебра

Ariphm

14

891

12 июн 2018, 01:17

Доказать изоморфизм

в форуме Линейная и Абстрактная алгебра

olegsh1971

2

431

07 мар 2015, 19:52

Доказать изоморфизм

в форуме Линейная и Абстрактная алгебра

Woodpecker

1

494

17 мар 2015, 23:52

Изоморфизм множеств

в форуме Дискретная математика, Теория множеств и Логика

famesyasd

9

661

30 сен 2016, 17:07

Доказать изоморфизм

в форуме Линейная и Абстрактная алгебра

Ana1229

1

184

15 мар 2020, 19:20

Изоморфизм при факторизации

в форуме Дискретная математика, Теория множеств и Логика

dab15

1

290

27 июн 2015, 15:38


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved