DRAKON.SU

Текущее время: Четверг, 24 Сентябрь, 2020 15:37

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Степень вершины графа
СообщениеДобавлено: Воскресенье, 20 Октябрь, 2019 09:25 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
http://bit.ly/2MPBBLS
Цитата:
Степень вершины (теория графов)

Материал из Википедии — свободной энциклопедии

Рис. 1. Граф, на вершинах которого отмечены степени.

Степень или валентность вершины графа — количество рёбер графа G, инцидентных вершине x. При подсчёте степени ребро-петля учитывается дважды.[1]

Степень вершины обычно обозначается как d(x) или \deg(v).
Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Содержание

1 Лемма о рукопожатиях
2 Последовательность степеней вершин
3 Частные значения
4 Общие свойства
5 См. также
6 Примечания
7 Источники

Лемма о рукопожатиях

Основная статья: Лемма о рукопожатиях

По формуле суммы степеней для графа {\displaystyle G=(V,E)}G=(V,E),

{\displaystyle \sum _{v\in V}\deg(v)=2|E|\,,}\sum _{{v\in V}}\deg(v)=2|E|\,,
то есть сумма степеней вершин любого графа равна удвоенному числу его рёбер. Кроме того, из формулы следует, что в любом графе число вершин нечётной степени чётно. Данное утверждение (и сама формула) известны как лемма о рукопожатиях. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других, чётно.

Последовательность степеней вершин

Рис. 2. Два неизоморфных графа с одинаковой последовательностью степеней (3, 2, 2, 2, 2, 1, 1, 1).

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью.[2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0).

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

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин).
Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа.
Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность di (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство

{\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)\quad \ k\in \{1,\dots ,n-1\}\,.}\sum _{{i=1}}^{{k}}d_{i}\leq k(k-1)+\sum _{{i=k+1}}^{n}\min(d_{i},k)\quad \ k\in \{1,\dots ,n-1\}\,.

Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, 2 или 4, но не при k равном 3.

Согласно критерию Гавела — Хакими, если невозрастающая последовательность (d1, d2, …, dn) это последовательность степеней простого графа, то (d2 − 1, d3 − 1, …, dd1+1 − 1, dd1+2, dd1+3, …, dn) некоторая последовательность степеней простого графа. Этот факт позволяет построить полиномиальный алгоритм нахождения простого графа с заданной реализуемой последовательностью.

Сопоставим исходной последовательности чисел вершины графа без ребер с требуемыми степенями. Указанное преобразование последовательностей задает как минимум одну вершину графа, все инцидентные ей ребра и множество вершин с новыми требуемыми дополнениями степеней. Упорядочивая оставшиеся вершины по невозрастанию дополнений степеней, получим невозрастающую последовательность степеней простого графа. Повторяя преобразование и упорядочение не более n-1 раза, получаем весь граф.

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

Частные значения

Рис. 3. Концевыми вершинами являются 4, 5, 6, 7, 10, 11 и 12.

Вершина степени 0 называется изолированной.

Вершина степени 1 называется концевой (англ. end vertex), висячей (англ. pendant vertex) или листом графа (англ. leaf vertex). Ребро, инцидентное такой вершине называется висячим (англ. terminal (pendant) edge, end-edge). На рис. 3 висячим ребром является {3,5}.

Подобная терминология используется в изучении деревьев в общем и как структур данных.


Вершина степени n-1 графа порядка n называется доминирующей (англ. dominating vertex).

Общие свойства

Если все вершины графа имеют одинаковую степень k, граф называют k-регулярным или регулярным графом степени k.
В этом случае сам граф имеет степень k.

Эйлеров путь существует в неориентированном, связном графе тогда и только тогда, когда граф имеет 0 или 2 вершины нечётной степени. Если граф содержит 0 вершин нечётной степени, Эйлеров путь является циклом.

Орграф является псевдолесом[неизвестный термин] только если полустепень исхода каждой вершины не больше 1.

Функциональный граф — частный случай псевдолеса, в котором полустепени исхода всех вершин равны 1.

Согласно теореме Брукса, хроматическое число любого графа за исключением клики или нечётного цикла не превышает максимальной степени его вершин (Δ). Согласно теореме Визинга, хроматический индекс любого графа не превышает Δ + 1.

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

См. также

Полустепень захода и полустепень исхода вершин ориентированных графов
Распределение степеней

Примечания

Дистель, стр. 5
Дистель, стр. 278

Источники

Дистель, Рейнхард (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.

Эрдёш, П. & Галлаи, T. (1960), "Gráfok előírt fokszámú pontokkal", Matematikai Lapok Т. 11: 264—274.

Хакими, С. Л. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics Т. 10: 496–506.

Сирксма, Хирард & Хоохефен, Хан (1991), "Seven criteria for integer sequences being graphic", Journal of Graph Theory Т. 15 (2): 223–231.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Воскресенье, 20 Октябрь, 2019 10:25 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 1126
Зачем эта тема?

Как относится к языку Дракон?
Расскажите, как повлияло на Дракон?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Среда, 23 Октябрь, 2019 09:39 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
LKom писал(а):
Зачем эта тема?

Как относится к языку Дракон?
Ответ здесь viewtopic.php?f=148&t=6705


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Среда, 23 Октябрь, 2019 11:17 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 1126
Владимир Паронджанов писал(а):
LKom писал(а):
Зачем эта тема?

Как относится к языку Дракон?
Ответ здесь viewtopic.php?f=148&t=6705

Какие у Вас по теме есть мысли?
Что конкретно по теме предлагаете?

Почему Вы тему по ссылке https://forum.drakon.su/viewtopic.php? закрыли?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Среда, 23 Октябрь, 2019 12:59 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
LKom писал(а):
Какие у Вас по теме есть мысли?

1. В языке ДРАКОН степени вершин (икон), равные 0, не используются.

2. Степень 1 имеют иконы Заголовок и Конец.

3. Степень 2 имеют иконы в линейном (неразветвленном ациклическом) примитиве и в линейной (неразветвленной ациклической) ветке.

4. Степень 3 имеют иконы Вопрос.

Это сырые неполные предварительные тезисы. Их надо проверить и, возможно, исправить.

LKom писал(а):
Что по теме предлагаете?
Я предлагаю молодым специалистам, которые придут нам на смену, тему для научного исследования.

Подробнее см. здесь viewtopic.php?f=148&t=6705

LKom писал(а):
Почему Вы тему по ссылке https://forum.drakon.su/viewtopic.php? закрыли?
Не знаю. Я не удалял.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Среда, 23 Октябрь, 2019 13:33 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1082
Откуда: Россия, Чебоксары
Владимир Паронджанов писал(а):
LKom писал(а):
Почему Вы тему по ссылке https://forum.drakon.su/viewtopic.php? закрыли?
Не знаю. Я не удалял.
Тема имеет статус "Закрыто". Это значит, что никто не может писать в эту тему.
Автор темы может открыть её или закрыть, есть такая настройка в теме.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Среда, 23 Октябрь, 2019 14:36 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
Alexey_Donskoy писал(а):
Владимир Паронджанов писал(а):
LKom писал(а):
Почему Вы тему по ссылке https://forum.drakon.su/viewtopic.php? закрыли?
Не знаю. Я не удалял.
Тема имеет статус "Закрыто". Это значит, что никто не может писать в эту тему.
Автор темы может открыть её или закрыть, есть такая настройка в теме.
Алексей, я не знаю, о чем идет речь.
Если тема закрыта, ее можно свободно читать.
Но я по ссылке получаю:
Цитата:
Запрошенной темы не существует.
Это значит, что тема удалена (а не закрыта).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Среда, 23 Октябрь, 2019 14:55 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1082
Откуда: Россия, Чебоксары
Владимир Паронджанов писал(а):
Но я по ссылке получаю
Это значит, что коллега ошибся, цитируя ссылку. Правильная ссылка у вас выше:
Владимир Паронджанов писал(а):
Ответ здесь viewtopic.php?f=148&t=6705
Но тема по ней закрыта (закрыта от размещения постов других участников). Проверьте её настройки.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Степень вершины графа
СообщениеДобавлено: Среда, 23 Октябрь, 2019 16:29 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
Alexey_Donskoy писал(а):
Правильная ссылка[/url] у вас выше:
Владимир Паронджанов писал(а):
Ответ здесь viewtopic.php?f=148&t=6705
Но тема по ней закрыта (закрыта от размещения постов других участников). Проверьте её настройки.
Вы правы.
Тему по этой ссылке я действительно закрыл. Причина в том, что это "Объявление" (а не обычная тема).

Я закрыл Объявление (от размещения постов других участников) во избежание путаницы.
См. viewforum.php?f=148


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2020, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB