Во-первых, извиняюсь если создаю путаницу с определениями. Во-вторых оговоримся, что речь идёт о невзвешенных неориентированных графах.

1) Окрестностью вершины $% u $% порядка $% n $% назовём подграф, состоящий из всех вершин, до которых из вершины $% u $% существует путь длиной не более, чем $% n $%.

2) Однородным графом назовём такой граф, в котором для любых двух вершин $% w $% и $% u $% окрестности этих вершин порядка $% n $% изоморфны при любом натуральном $% n $%.

Вопрос: при каком количестве вершин $% n $% существует (хотя бы 1, если их несколько) $% k $%-регулярный однородный граф с 1 компонентой связанности? PS - в $% k $%-регулярном графе степени всех вершин одинаковы и равны $% k $%.

Вопрос № 2: укладывается ли данный граф на торе?

задан 1 Дек '13 23:20

изменен 1 Дек '13 23:21

10|600 символов нужно символов осталось
0

Если $%n$% чётное, при любом $%1 < k < n$% есть $%k$%-регулярный граф c $%n$% вершинами.
Его можно получить следующим образом. Пусть $%n=2m.$% Тогда занумеруем вершины от $%0 $% до $%2m-1$% и для каждого натурального $%p \leqslant m$% определим $%p$%-цикл как граф, полученный из всех рёбер, соединяющих вершины, номера которых отличаются на $%p$% по модулю $%2m$% (то есть на $%\min(p , 2m-p)$%).
Почти очевидно, что при сдвиге нумерации на константу этих циклы меняться не будут. Значит, и граф, полученный их наложением, меняться не будет, а значит, он будет однороден.
При добавлении $%m$%-кольца степень каждой вершины вырастет на 1, при добавлении другого $%p$%-кольца - на 2. Значит, при любом $%k:1< k< n$% можно получить $%k$%-регулярный однородный граф с $%2m$% вершинами.
Если n нечётное, можно получить лишь $%2l$%-регулярный граф.
Итого:
При $%k=1$% задача имеет решение лишь при $%n=2;$%
при чётном $%k$% есть решение при любом $%n> k$%, при нечётном $%k$% решение есть при любом $%2m > k.$%

ссылка

отвечен 2 Дек '13 0:59

10|600 символов нужно символов осталось
0

Я так понимаю, графы здесь "по умолчанию" считаются простыми, то есть ни петель, ни картных рёбер они не содержат. Если так, то у $%k$%-регулярного графа число вершин не меньше $%k+1$%, и для любого такого значения $%m\ge k+1$% можно построить однородный $%k$%-регулярный граф при $%k\ge2$% с некоторыми естественными ограничениями (для случая $%k=1$% возможен только отрезок). Берём правильный $%m$%-угольник (его контур), и добавляем к нему рёбра. Если $%k$% чётно, то соединяем дополнительно каждую вершину с $%k/2-1$% следующими по часовой стрелке, не считая ближайшего соседа. Временно можно поставить на этих рёбрах стрелки. Тогда выходящих рёбер будет $%k/2-1$%, входящих столько же, и вместе с двумя рёбрами контура получится $%k$%.

Теперь пусть $%k$% нечётно. Тогда $%m$% должно быть чётным по лемме о рукопожатиях. При этих условиях делаем так: добавляем в $%m$%-угольнике все главные (большие) диагонали, а далее соединяем каждую вершину с $%(k-3)/2$% ближайшими, не считая соседей, по обе стороны от этой диагонали.

Во всех случаях граф будет симметричен относительно повторотов, что обеспечивает однородность.

Вопрос об укладке на торе не совсем понятен, потому что конкретный граф здесь не задан, и непонятно, к чему этот вопрос относить. По идее, он должен рассматриваться отдельно для каждого значения $%k$% и/или для значения $%m$%. Тут можно разве что заметить, что у простого графа, уложенного без самопересечений на торе, всегда найдётся вершина валентности не более $%6$% (это выводится из формулы Эйлера при помощи несложного рассуждения), то есть $%k\le6$%. Для $%k=6$% подходит стандартная укладка графа $%K_7$%. Что касается меньших значений $%k$% или больших значений $%m$%, то здесь постановку вопроса следует уточнить.

ссылка

отвечен 2 Дек '13 1:50

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×418
×137

задан
1 Дек '13 23:20

показан
2486 раз

обновлен
2 Дек '13 1:50

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

по почте:

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

по RSS:

Ответы

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

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