Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Ноябрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Профессор
Рейтинг: 3551
∙ повысить рейтинг » 		_Ayl_
Статус: Студент
Рейтинг: 1422
∙ повысить рейтинг » 		Lang21
Статус: Профессионал
Рейтинг: 305
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Номер выпуска:147
Дата выхода:18.11.2009, 22:00
Администратор рассылки:Alexey G. Gladenyuk, Управляющий
Подписчиков / экспертов:107 / 40
Вопросов / ответов:2 / 3

Вопрос № 174199: Здравствуйте эксперты, подскажите пожалуйста со следующей задачей: Есть 2 не ориентированных графа, без обозначения вершин и линий, то есть просто точки между собой соединены и все. Как определить, изоморфны ли они? ...

Вопрос № 174200: Здравствуйте эксперты, подскажите пожалуйста со следующей задачей: Надо построить плоский граф с хромическим числом 4, так чтобы кол-во вершин было минимально. Есть какие-то алгоритмы по постройке? У меня получился граф с 4мя вершинами, меньше нав...
Вопрос № 174199:

Здравствуйте эксперты, подскажите пожалуйста со следующей задачей:
Есть 2 не ориентированных графа, без обозначения вершин и линий, то есть просто точки между собой соединены и все. Как определить, изоморфны ли они?

Отправлен: 13.11.2009, 23:48
Вопрос задал: Tribak, Студент
Всего ответов: 2
Страница вопроса »

Отвечает Гордиенко Андрей Владимирович, Профессор :
Здравствуйте, Tribak.

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

С уважением.

-----
Пусть говорят дела

Ответ отправил: Гордиенко Андрей Владимирович, Профессор
Ответ отправлен: 14.11.2009, 14:37

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 256495 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!
    Отвечает Gh0stik, Модератор :
    Здравствуйте, Tribak.

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

    Вот на примере:




    Так что можно сделать вывод, что в первом случае графы изоморфны, а во втором нет.

    Помимо этого для рисунка 4.5 графы не изоморфны, поскольку в одном графе есть вершина степени 2, а в другом нет.
    Думаю дальнейшие исследования Вы проведете самостоятельно.
    < br>Good Luck!

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

    Ответ отправил: Gh0stik, Модератор
    Ответ отправлен: 14.11.2009, 15:47
    Украина, Славянск
    Организация: Славянский государственный педагогический университет (Кафедра алгебры)
    Адрес сайта: http://gh0stik.rusfaq.ru/
    ICQ # 289363162

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 256502 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Вопрос № 174200:

    Здравствуйте эксперты, подскажите пожалуйста со следующей задачей:
    Надо построить плоский граф с хромическим числом 4, так чтобы кол-во вершин было минимально. Есть какие-то алгоритмы по постройке? У меня получился граф с 4мя вершинами, меньше наверное некуда, поэтому думаю что построил правильно, но если есть алгоритмы, то наверное можно как-то по правилом все это сделать.

    Отправлен: 13.11.2009, 23:48
    Вопрос задал: Tribak, Студент
    Всего ответов: 1
    Страница вопроса »

    Отвечает Гордиенко Андрей Владимирович, Профессор :
    Здравствуйте, Tribak.

    Соотношения, которое позволяло бы вычислить хроматическое число графа G, не существует. Но можно исходить из того, что наиболее простая оценка этого числа имеет вид
    γ(G) ≤ degmax(ν) + 1,
    где degmax(ν) - наибольшая локальная степень вершины ν графа G.

    Об этом написано, например, в учебнике по дискретной математике А. Д. Плотникова.

    Поэтому, как я понимаю, Вы правы. Меньше четырех вершин не получается...

    С уважением.

    -----
    Пусть говорят дела

    Ответ отправил: Гордиенко Андрей Владимирович, Профессор
    Ответ отправлен: 14.11.2009, 14:50

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 256497 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2009, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.11 от 17.11.2009
    В избранное