![]() |
Здравствуйте, гость ( Вход | Регистрация )
![]() |
Deft |
![]()
Сообщение
#1
|
Школьник ![]() Группа: Продвинутые Сообщений: 29 Регистрация: 6.3.2008 Город: Краснодар Учебное заведение: КубГУ Вы: студент ![]() |
Задача:
Сколько существует графов с вершинами из {a, ..., z}, изоморфных данному: (IMG:http://i009.radikal.ru/0804/70/6ae1993709da.jpg) Буду искренне благодарен, если хотя бы немного подскажете как решать такие задачи. |
![]() ![]() |
Deft |
![]()
Сообщение
#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" - количество неотличимых вершин. - Все получаемые сочетания перемножаются. Это и будет ответом. К сожалению, ответа от издателя задачника нет, поэтому, я не уверен, что ответ точный, проверял сам, могут быть ошибки. Но метод решения именно такой. |
![]() ![]() |
![]() |
Текстовая версия | Сейчас: 27.5.2025, 22:07 |
Зеркало сайта Решебник.Ру - reshebnik.org.ru