Как изобразить все НЕизоморфные графы с N вершинами и M ребрами? Покажите на примере с малыми N и M. (обыкновенные графы)

задан 29 Июн '14 2:03

изменен 29 Июн '14 2:05

Тут надо просто картинки рисовать и смотреть, чтобы они были принципиально различные. Скажем, при N=1 будет граф с одной вершиной и M петлями. При N=2 мы либо соединяем вершины, либо нет. В каждом из случаев распределяем петли между вершинами. При N=3 будет чуть посложнее, но тоже можно классифицировать. Это всё делается вручную, перебором.

(29 Июн '14 2:11) falcao

Примем как условие, что петель быть не должно. Я предположил, что перебор можно делать, выписывая наборы степеней вершин. Но к сожалению, не получилось понять алгоритм. Возможно ли через наборы степеней вершин описать все неизоморфные графы с N вершинами и M ребрами?

$$\\$$

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

(29 Июн '14 2:18) ssh

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

Если петель нет, то как насчёт кратных рёбер?

(29 Июн '14 3:05) falcao

Рассматриваются неориентированные графы без петель и кратных ребер.

(29 Июн '14 14:53) ssh
1

Такие графы называются простыми. Их нетрудно перечислить для значений, скажем, N=4 (всего 11 графов) и для N=5 (34 графа). Для каждого M=0,1,...,N(N-1)/2 рисуется полный "каталог". К графам для предыдущего значения M пририсовываем новое ребро и следим за тем, чтобы картинки не повторялись. При этом достаточно рассматривать случаи M<=N(N-1)/4, потому что переход от M к N(N-1)/2-M осуществляется за счёт рассмотрения дополнений подграфов в полном графе.

(29 Июн '14 16:00) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×934
×112

задан
29 Июн '14 2:03

показан
2615 раз

обновлен
29 Июн '14 16:00

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru