Сколько существует попарно неизоморфных графов без петель и кратных ребер, имеющий 6 вершин и 11 ребер? Понятно, что столько же, сколько с 6 вершинами и 4 ребрами. Но это считать только перебором?

задан 8 Апр '15 3:04

изменен 8 Апр '15 3:13

Какой-либо простой удобной формулы здесь не известно (думаю, что её и нет). Нужно всё перебирать, но при этом желательно использовать какой-то принцип перебора, чтобы ничего не пропустить, и ничего не посчитать два раза вместо одного.

(8 Апр '15 8:24) falcao
10|600 символов нужно символов осталось
1

В полном графе с 6 вершинами имеется 15 рёбер, поэтому дополнение графа из условия задачи будет иметь 4 ребра. Графы изоморфны тогда и только тогда, когда изоморфны их дополнения, поэтому достаточно перечислить все попарно неизоморфные графы с 6 вершинами и 4 рёбрами.

Если граф имеет простой цикл, то длина такого цикла равна 3 или 4. Для цикла длиной 4 все рёбра использованы, то есть получается цикл и две изолированные вершины. Пусть есть цикл длиной 3. Тогда четвёртое ребро к нему можно добавить двумя способами. Получится или треугольник с "ножкой" и двумя изолированными вершинами, или треугольник с отрезком и отдельной точкой.

Итак, графов с циклами имеется три. Остальные графы -- объединения деревьев. В каждом дереве рёбер на единицу меньше, чем вершин. Поэтому деревьев должно быть два. Варианты (по числу вершин): 5+1, 4+2, 3+3. Дерево с двумя вершинами одно. С тремя вершинами -- также одно. Деревьев с четырьмя вершинами два: это цепь, а также "трилистник". Добавляя к таким деревьям ещё одно ребро, чтобы снова получилось дерево, мы видим, что с пятью вершинами имеется три дерева: цепь, четырёхполюсник, и ещё одно дерево, получаемое из трилистника (понятно, какое). Итого у нас имеется три случая графов типа 5+1, два случая типа 4+2, и один случай типа 3+3; итого шесть.

Вместо получается ровно 9 попарно неизоморфных графов.

ссылка

отвечен 8 Апр '15 3:43

"Поэтому деревьев должно быть два" - вот это немного непонятно, почему 2? И почему графы без циклов мы рассматриваем именно как объединение деревьев? То есть, понятно, что это оно будет, но почему такой подход?

(8 Апр '15 18:25) Ovod

@Ovod: деревом называется связный граф без циклов. Случай графа с циклами был рассмотрен в начале. Остаётся случай графа, у которого нет циклов ни в одной из связных компонент, что означает, что любая из связных компонент -- дерево. Если таких связных компонент m, то в каждой из них на одно ребро меньше, чем вершин. Значит, m равно разности числа вершин и числа рёбер, то есть 6-4=2.

(8 Апр '15 22:54) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,872
×654

задан
8 Апр '15 3:04

показан
14228 раз

обновлен
8 Апр '15 22:54

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

по почте:

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

по RSS:

Ответы

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

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