Граф Кауца

Граф Кауца $K_{M}^{N+1}$ — это ориентированный граф степени $M$ и размерности $N+1$ , который имеет $(M+1)M^{N}$ вершин, помеченных всеми возможными строками $s_{0}\cdots s_{N}$ длины $N+1$ , которые составлены из символов $s_{i}$ , выбранных из алфавита $A$ , содержащего $M+1$ различных символов с условием, что соседние символы не могут совпадать ( $s_{i}\neq s_{i+1}$ ).

Граф Кауца $K_{M}^{N+1}$ имеет $(M+1)M^{N+1}$ рёбер

$\{(s_{0}s_{1}\cdots s_{N},s_{1}s_{2}\cdots s_{N}s_{N+1})|\;s_{i}\in A\;s_{i}\neq s_{i+1}\}\,$

Естественно пометить каждое такое ребро $K_{M}^{N+1}$ как $s_{0}s_{1}\cdots s_{N+1}$ , создавая один-к-одному соответствие между рёбрами графа Кауца $K_{M}^{N+1}$ и вершинами графа Кауца $K_{M}^{N+2}$ .

Графы Кауца тесно связаны с графами де Брёйна.

Свойства

Для фиксированной степени $M$ и числа вершин $V=(M+1)M^{N}$ граф Кауца имеет наименьший диаметр для любого ориентированного графа с $V$ вершинами и степенью $M$ .
Все графы Кауца имеют эйлеровы циклы. (Эйлеров цикл — это цикл, который посещает каждое ребро ровно раз — этот результат следует из того, что графы Кауца имеют полустепень захода равную полустепени исхода для каждого узла).
Все графы Кауца имеют гамильтонов цикл (Этот результат следует из соответствия, описанного выше между рёбрами графа Кауца $K_{M}^{N}$ и вершинами графа Кауца $K_{M}^{N+1}$ . Гамильтонов цикл на $K_{M}^{N+1}$ задаётся эйлеровым циклом на $K_{M}^{N}$ ).
Граф Кауца степени $k$ имеет $k$ непересекающихся пути из любого узла $x$ в любой другой узел $y$ .

В обработке данных

Граф Кауца использовался в качестве сетевой технологии для соединения процессоров в высокопроизводительных вычислениях^[1] и отказоустойчивых вычислениях^[2], такие сети известны как сети Кауца.

Примечания

↑ Darcy, 2007.
↑ Li, Lu, Su, 2004, с. 308–315.

Литература

Jeff Darcy. The Kautz Graph. — Canned Platypus, 2007.
Dongsheng Li, Xicheng Lu, Jinshu Su. Network and Parallel Computing: IFIP International Conference. — Wuhan, China: NPC, 2004. — ISBN 3-540-23388-1.

Похожие исследовательские статьи

Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:

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

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

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

<span class="mw-page-title-main">Случайный граф</span> общий термин для обозначения вероятностного распределения графов

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

Последовательность де Брёйна — циклический порядок $\text{[math]}$ , элементы которого принадлежат заданному конечному множеству, такой, что все его подпоследовательности $\text{[math]}$ заданной длины $\text{[math]}$ различны.

Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

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

Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.

В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.

Степень (валентность) вершины графа — количество рёбер графа $\text{[math]}$ , инцидентных вершине $\text{[math]}$ . При подсчёте степени ребро-петля учитывается дважды.

<span class="mw-page-title-main">Турнир (теория графов)</span> ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру

Турнир — это ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру. Таким образом, турнир — это орграф, в котором каждая пара вершин соединена одной направленной дугой.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

Теорема Оре — результат в теории графов, доказанный в 1960 году норвежским математиком Ойстином Оре. Теорема даёт достаточное условие для того, чтобы граф был гамильтоновым, по существу утверждая, что граф с «достаточно большим числом рёбер» должен содержать гамильтонов цикл. В частности, теорема рассматривает суммы степеней пар несмежных вершин — если каждая такая пара в сумме даёт как минимум общее число вершин графа, граф является гамильтоновым.

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

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

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

Пространство циклов неориентированного графа — линейное пространство над полем $\text{[math]}$ , состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.

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

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.