IPB

Здравствуйте, гость ( Вход | Регистрация )

> Сколько существует графов, изоморфных данному, Дискретная математика.
Deft
сообщение 16.4.2008, 16:47
Сообщение #1


Школьник
*

Группа: Продвинутые
Сообщений: 29
Регистрация: 6.3.2008
Город: Краснодар
Учебное заведение: КубГУ
Вы: студент



Задача:
Сколько существует графов с вершинами из {a, ..., z}, изоморфных данному:
(IMG:http://i009.radikal.ru/0804/70/6ae1993709da.jpg)
Буду искренне благодарен, если хотя бы немного подскажете как решать такие задачи.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
 
Ответить в эту темуОткрыть новую тему
Ответов
Deft
сообщение 18.4.2008, 14:59
Сообщение #2


Школьник
*

Группа: Продвинутые
Сообщений: 29
Регистрация: 6.3.2008
Город: Краснодар
Учебное заведение: КубГУ
Вы: студент



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

Ответ к заданию приведенному выше (C[x,y] - означает C из "x" по "y"):
Для начала пронумеруем вершины графа:

(IMG:http://i007.radikal.ru/0804/fa/510833028763.jpg)

Начатьная цифра, т.е. из чего будем выбирать - это кол-во различных символов в алфавите. Для латинского алфавита - 26 символов, для русского - 33.

Ответ:
C[26,2] * C[24,1] * C[23,2] * C[21,1] * C[20,2] * C[18,1] * C[17,1] * C[16,1] * C[15,1] * C[14,1] * C[13,1] * C[12,1] * C[11,1] * C[10,1] * C[9,1] * C[8,2]


Поставим соответствие (цифры соответствуют номерам вершин на картинке выше):
C[26,2] - 1,2.
C[24,1] - 3.
C[23,2] - 4,5.
C[21,1] - 6.
C[20,2] - 7,8.
C[18,1] - 9.
C[17,1] - 10.
C[16,1] - 11.
C[15,1] - 12.
C[14,1] - 13.
C[13,1] - 14.
C[12,1] - 15.
C[11,1] - 16.
C[10,1] - 17.
C[9,1] - 18.
C[8,2] - 19,20.

Метод решения:
- Пронумеровываем все вершины графа.
- Если вершина отличима, то выписывается C[x,1], где "x" - количество еще не выбранных букв.
- Если вершина неотличима, то выписывается C[x,y], где "x" - количество еще не выбранных букв, "y" - количество неотличимых вершин.
- Все получаемые сочетания перемножаются. Это и будет ответом.

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

Сообщений в этой теме


Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия Сейчас: 27.5.2025, 22:07

Книжки в помощь: "Сборник заданий по высшей математике" Кузнецов Л.А., "Сборник заданий по высшей математике" Чудесенко В.Ф., "Индивидуальные задания по высшей математике" Рябушко А.П., и другие.




Зеркало сайта Решебник.Ру - reshebnik.org.ru