Версия для печати темы

Автор: Deft 16.4.2008, 16:47

Задача:
Сколько существует графов с вершинами из {a, ..., z}, изоморфных данному:

Буду искренне благодарен, если хотя бы немного подскажете как решать такие задачи.

Автор: tig81 16.4.2008, 16:51

Цитата(Deft @ 16.4.2008, 19:47)

Автор: Deft 17.4.2008, 7:07

Определение изоморфных графов я знаю, звучит оно так:
Графы G = (V, U) и G1 = (V1, U1) называются изоморфными, если существует такая биекция h: V -> V1, что
для любого a, b принадлежащего V (( a, b ) принадлежит U тогда и только тогда, когда (h( a ), h( b )) принадлежит U1
Еще знаю как определить изоморфны ли 2 графа или нет. Но это не особо помогает в решении поставленной задачи. Как бы говоря понятно, что нужно найти, но как это найти не очень понятно.
P.S. Ссылочка, к сожалению, не работает. Выдает пустую страницу.

Автор: tig81 17.4.2008, 8:52

Цитата(Deft @ 17.4.2008, 10:07)

Автор: Deft 17.4.2008, 9:52

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

Автор: Deft 18.4.2008, 14:59

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

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



Начатьная цифра, т.е. из чего будем выбирать - это кол-во различных символов в алфавите. Для латинского алфавита - 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" - количество неотличимых вершин.
- Все получаемые сочетания перемножаются. Это и будет ответом.

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

Автор: Gusachenko 20.2.2011, 16:03

учишься на ФПМ ? От слова Костенко есть дрожь в коленках?)))) если на половину ответил да, то нужен совет.... это правильное решение кол-ва изоморфных графу? ты сдал зачет за 2 семестр?

скажи, почему вершины 9 и 10 выбираешь по отдельности? они же одинаковые? и по такой же причине 11 и 12? 14 и 15? короче все зеркальные? можешь уточнить термин "если невозможно отличить"?

и почему тогда 19 и 20 выбираются вместе? ведь они отличины получаются ведь из 18 в 19 нет ребра и из 17 в 20, получаются они отличимы?