Регулярный граф, Однородный граф, бесконечный однородный граф кратко

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

Regular graph регулярный граф - граф, у которого степени всех вершин равны между собой; степень его вершин называется степенью регулярного графа. Все полные графы регулярны; регулярны также графы платоновых тел. Регулярным графом степени n является n -мерный куб. Другое название - однородный граф .

Однородный граф - это граф, у которого все вершины имеют одинаковую степень.

Теорема 7.5.1. Однородный граф не имеет дефицита.

Теорема 7.5.3. Почти однородный граф G, в котором отклонения, определяемые в (7.5.6), удовлетворяют условиям (7.5.8), имеет однородный суграф первой степени.

Если О - однородный граф, то он восстанавливаем.

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

На рис. 1.2.2 приведены примеры двух бесконечных однородных графов.

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

Заметим, что обыкновенный полный граф, имеющий k вершин, является ( k - 1) - однородным. Можно еще отметить, что согласно теореме 1.3 - однородный граф имеет четное число вершин, если k нечетно.

Если для всех вершин d(v) = k, то граф называется однородным графом степени k или k-однородным. Граф на рис. 10.21.5 является полным и 3-однородным.

Рис. 10.21.5.

Бесконечный граф

Примеры бесконечных однородных графов.

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

Бесконечным графом называется пара (V(G), E(G)), где V(G)— бесконечное множество элементов, называемое вершинами, а E(G) — бесконечное семейство неупорядоченных пар элементов из V(G), называемых ребрами.

Если оба множества V(G) и E(G) — счетны, то называется счетным графом.
Заметим, что наши определения исключают те случаи, когда V(G) — бесконечно, а E(G) — конечно.

Такие объекты являются всего лишь конечными графами с бесконечным множеством изолированных вершин.

Когда E(G) — бесконечно, а V(G) — конечно, такие объекты являются конечными графами с бесконечным числом петель или кратных ребер.

Некоторые определения таких понятий, как "смежный", "инцидентный", "изоморфный", "подграф", "объединение", "связный", "компонента" переносятся на
бесконечные графы.

Степенью вершины бесконечного графа называется мощность множества ребер, инцидентных Степень вершины может быть конечной или бесконечной.
Бесконечный граф, все вершины которого имеют конечные степени, называется локально
конечным. Об этом говорит сайт https://intellect.icu . Хорошо известным примером такого графа является бесконечная квадратная
решетка, часть которой изображена на рисунке. Локально счетный бесконечный граф —
это граф, все вершины которого имеют счетную степень. Под счетным множеством здесь
и в дальнейшем понимается бесконечное множество, допускающее взаимно однозначное
отображение на множество натуральных чисел.

Теорема Каждый связный локально счетный бесконечный граф является счетным.
Доказательство
Пусть — произвольная вершина такого бесконечного графа, и пусть —
множество вершин, смежных , — множество всех вершин, смежных вершинам
из , и т.д. По условию теоремы — счетно и,
следовательно, множества тоже счетны. Здесь используется тот факт,
что объединение не более чем счетного множества счетных множеств счетно.
Следовательно, — последовательность множеств, объединение которых
счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного
графа в силу его связности. Отсюда и следует нужный результат.
Следствие Каждый связный локально конечный бесконечный граф является
счетным.
Помимо этого, на бесконечный граф можно перенести понятие маршрута,
причем тремя различными способами:
1. Конечный маршрут в определяется так. Маршрутом в данном графе
называется конечная последовательность ребер вида
, . Маршрут можно обозначить и так:
.
2. Бесконечным в одну сторону маршрутом в с начальной вершиной
называется бесконечная последовательность ребер вида , .
3. Бесконечным в обе стороны маршрутом в графе называется бесконечная
последовательность ребер вида
,

Бесконечные в одну сторону и в обе стороны цепи и простые цепи определяются
очевидным образом, так же как и понятия длины цепи и расстояния между вершинами.
Бесконечные простые цепи не так уж трудно обнаружить.

Теорема. (Кениг, 1936) Пусть G — связный локально конечный бесконечный граф, тогда для любой вершины V существует бесконечная в одну сторону простая цепь с начальной вершиной V .

Доказательство
Если — произвольная вершина графа , отличная от , то существует
нетривиальная простая цепь от до , отсюда следует, что в имеется бесконечно
много простых цепей с начальной вершиной . Поскольку степень конечна, то
бесконечное множество таких простых цепей должно начинаться с одного и того же
ребра. Если таким ребром является , то, повторяя эту процедуру для
вершины , получим новую вершину и соответствующее ей ребро .
Продолжая таким образом, получим бесконечную в одну сторону простую
цепь .
Важное значение леммы Кенига состоит в том, что она позволяет получить
результаты о бесконечных графах из соответствующих результатов для конечных графов.

Типичным примером является следующая теорема.

Теорема. Пусть G — счетный граф, каждый конечный подграф которого планарен, тогда и G планарен.

Доказательство

Так как — счетный граф, его вершины можно занумеровать в
последовательность . Исходя из нее, построим строго возрастающую
последовательность подграфов графа , выбирая в качестве подграф с вершинами и ребрами графа , соединяющими
только эти вершины между собой. Далее, примем на веру тот факт, что графы могут
быть уложены на плоскости конечным числом, скажем , топологически различных
способов, и построим еще один бесконечный граф . Его вершины
, пусть соответствуют различным укладкам
графов , а его ребра соединяют те из вершин и , для
которых и плоская укладка, соответствующей . Мы видим,
что граф связен и локально конечен, поэтому, как следует из леммы Кенига, он
содержит бесконечную в одну сторону простую цепь. А так как граф является
счетным, то эта бесконечная простая цепь и дает требуемую плоскую укладку графа .

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

Вопросы:

1. Дайте определение Регулярного и Однородного графов.

2. Дайте определение бесконечного графа.

3. Какой граф называется однородным?

4. Где применяются бесконечные графы?

Надеюсь, эта статья про регулярный граф , была вам полезна, счастья и удачи в ваших начинаниях! Надеюсь, что теперь ты понял что такое регулярный граф , однородный граф, бесконечный однородный граф и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.