1. Главная
  2. Библиотека
  3. Информатика
  4. Сколько различных графов на множестве вершин {1, 2, 3, . . . , 8} изоморфны графу на рисунке?

Сколько различных графов на множестве вершин {1, 2, 3, . . . , 8} изоморфны графу на рисунке?

«Сколько различных графов на множестве вершин {1, 2, 3, . . . , 8} изоморфны графу на рисунке?»
  • Информатика

Условие:

Сколько различных графов на множестве вершин {1, 2, 3, . . . , 8} изоморфны графу на рисунке?

Решение:

Мы хотим посчитать, сколькими способами можно пронумеровать вершины данного графа, причем мы считаем два способа различными, если есть два номера x, y такие, что в одном случае их вершины они соединены ребром, а в другом нет.

Сначала выберем номера для вершин по краям можно сделать

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

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет