Как понять существует ли граф

1. Основные понятия

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

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

Например, на рисунке \(1\) вершины A, D — чётные, так как имеют степени \(2\) и \(4\) соответственно, а вершины B, C, E, K, N, F — нечётные, так как вершины B, E, K, N, F имеют степень \(1\), а вершина C — степень \(3\).

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

Лемма о рукопожатиях.
Сумма степеней всех вершин графа равна удвоенному количеству рёбер.

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

ГРА́ФОВ ТЕО́РИЯ

ГРА́ФОВ ТЕО́РИЯ, раз­дел дис­крет­ной ма­те­ма­ти­ки, в ко­то­ром изу­ча­ют­ся свой­ст­ва гра­фов и их обоб­ще­ний. Гра­фом на­зы­ва­ет­ся па­ра ( $V, E$ ), где $V$ – мно­же­ст­во то­чек, на­зы­вае­мых вер­ши­на­ми, и $E$ – мно­же­ст­во пар вер­шин, при­чём ес­ли по­ря­док, в ко­то­ром пе­ре­чис­ле­ны вер­ши­ны в па­ре, не ва­жен, то эта па­ра вер­шин гра­фа на­зы­ва­ет­ся реб­ром, а ес­ли ва­жен – ду­гой. Граф, со­дер­жа­щий толь­ко рёб­ра, на­зы­ва­ет­ся не­ори­ен­ти­ро­ван­ным гра­фом, или про­сто гра­фом, а граф, со­дер­жа­щий толь­ко ду­ги, – ори­ен­ти­ро­ван­ным гра­фом. На рис. 1 – не­ори­ен­ти­ро­ван­ный граф с вер­ши­на­ми $a, b, c, d$ и рёб­ра­ми $(a, b), (b, c), (c, d), (a, d), (a, c), (b, d)$ , на рис. 2 – ори­ен­ти­ро­ван­ный граф с вер­ши­на­ми $a, b, c, d, e, f$ и ду­га­ми $(a, b), (b, c), (c, d), (d, e), (e, f), (f, a)$ .

графы — Существует ли граф?

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

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

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

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

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

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

2 ответа

Если $%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

Я так понимаю, графы здесь «по умолчанию» считаются простыми, то есть ни петель, ни картных рёбер они не содержат. Если так, то у $%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

falcao
300k ● 9 ● 38 ● 55

Существует ли граф на 9 вершинах, степени которых равны 1, 1, 1, 1, 1, 2, 4, 5, 6?

Правильно ли мое доказательство? Что делать для больших последовательностей? Какой алгоритм док-ва таких задач?
Доказываю следующим образом.
Допустим, что у всех вершин степень равна 0
0 0 0 0 0 0 0 0 0
Тогда чтобы получить вершину со степенью 6 нам нужно добавить ребра
0 0 1 1 1 1 1 1 6
Здесь я соединил последнюю вершину с 3,4,5,6,7,8 вершинами, и у них степень увеличилась на 1
Теперь нам нужно получить вершину со степенью 5
1 1 1 1 1 2 2 5 6
Дальше нам нужно получить вершину со степенью 4
1 1 1 1 2 3 4 5 6
Противоречие

• Вопрос задан более двух лет назад
• 1372 просмотра

Комментировать

Решения вопроса 0

Ответы на вопрос 2

Для правильного вопроса надо знать половину ответа

Теорема Эрдёша — Галлаи
1. 8 ≥ 6 ≥ 5 ≥ 4 ≥ 2 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1
2. 6 + 5 + 4 + 2 + 1 + 1 + 1 + 1 + 1 = 22
Данная последовательность является правильной.
k = 1, 6 ≤ (0 + 8), выполняется,
k = 2, 11 ≤ (2 + 9), выполняется,
k = 3, 15 ≤ (6 + 7), не выполняется.
Значит данная последовательность не является графической, по ней нельзя построить простой граф.

Ответ написан более двух лет назад

Нравится 3 2 комментария