Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6].
Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это непустое множество вершин или узлов, а E -- множество пар (в случае неориентированного графа -- неупорядоченных) вершин, называемых ребрами.
Вершины и ребра графа называются также элементами графа, число вершин в графе |V| -- порядком, число ребер |E| -- размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) ребра e={u, v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Маршрутом в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Цепью называется маршрут без повторяющихся ребер. Простой цепью называется маршрут без повторяющихся вершин (откуда следует, что в простой цепи нет повторяющихся ребер).
Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его ребер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u, v, u) является циклом. Чтобы избежать таких "вырожденных" случаев, вводят следующие понятия.
Путь (или цикл) называют простым, если ребра в нем не повторяются; элементарным, если он простой и вершины в нем не повторяются.
Кликой неориентированного графа называется подмножество его вершин, таких, что любые две вершины подмножества соединены ребром.
Максимальная клика - это клика, которая не может быть расширена путем включения дополнительных смежных вершин, то есть нет клики большего размера, включающей все вершины данной клики.
Граф называется хордальным, если каждый из его циклов, имеющий четыре и более дуг, имеет хорду, которая является ребром, соединяющим две вершины, не смежные в цикле. Эквивалентное определение -- если любой цикл без хорд имеет максимум три ребра.
Совершенный порядок исключения в графе -- это порядок вершин графа, такой что для каждой вершины v, v и соседи v, находящиеся после v в упорядочении, образуют клику. Граф хордален тогда и только тогда, когда имеет совершенный порядок исключения.
Астероидальной тройкой (АТ) называются три вершины графа, что каждая пара таких вершин соединяется путем, не проходящим через замкнутую окрестность третьей вершины.
Теорема 1. Граф интервальный тогда и только тогда, когда он хордален и не содержит астероидальных троек [10].
Четыре вершины графа порождают клешню с центром в вершине, если - три попарно несмежных соседа вершины.
Теорема 2. Интервальный граф является единичным интервальным тогда и только тогда, когда он не содержит порожденных клешней [11].
Единичный интервальный граф -- граф пересечений интервалов одинаковой длины.
Пусть граф с вершинами и порядок (последовательность) вершин. Порядок называется I-порядком графа, если для всех и, выполняется для всех. Порядок называется UI-порядком графа если для всех.
Теорема 3. Граф интервальный тогда и только тогда, когда у него имеется I-порядок [12].
Теорема 4. Граф единичный интервальный тогда и только тогда, когда у него имеется UI-порядок [13].
Примеры некоторых различных типов графов:
Хордальный, не являющийся интервальным. (bdf астероидальная тройка - есть пути соединяющие каждую пару, не проходящие через закрытое множество соседей, Рис.2).
Рис.2
Интервальный, не являющийся единичным интервальным (клешня, попарно несмежные соседи - не соединяются ребрами, Рис.3).
Рис.3
Единичный интервальный (самый простой пример, Рис.4)
Рис.4
Похожие статьи
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
Входные параметры: входной файл, выходной файл, номер вершины, номер вершины. Если задаваемые номера вершин положительные, то добавляется соответствующее...
-
Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан...
-
Введение - Алгоритмы нескольких махов
Теория графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике и социологии, а также в генетике,...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным,...
-
Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке...
-
Численные эксперименты были проведены для следующих целей: Подтверждение корректности алгоритмов. Подтверждение линейности временных затрат алгоритмов. В...
-
Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных...
-
Элементы теории графов. Сеть Петри. Конечный автомат
Вариант №8 Задача 1. Элементы теории графов Связный ориентированный граф G(Х, Г) задан множеством вершин X={x1, x2, ..., xn} и отображением Гxi={x|Ik|,...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Исследования временных затрат алгоритмов - Алгоритмы нескольких махов
Исследования временных затрат алгоритмов были проведены для трех вариантов программ: LBFS4, LBFS3, MNS3; для двух вариантов сборки исполняемого файла:...
-
Заключение, Список литературы - Алгоритмы нескольких махов
В ходе выполненной работы были изучены алгоритм распознавания единичного интервального графа с помощью трех проходов алгоритма лексикографического...
-
Квадратичная форма - Матричный формализм в теории систем
Квадратичной формой называется выражение: Этой квадратичной форме соответствует матрица Сделаем следующее преобразование с каждым членом квадратичной...
-
Основная программа Построение интерполяционного многочлена Нахождение максимума функции методом дихотомии Вычисление значения заданной функции Создание и...
-
Поворот точки относительно центра на заданный угол: X = o. X + (p. X-o. X) * cos(angle) - (p. Y-o. Y) * sin(angle) Y = o. Y + (p. X-o. X) * sin(angle) +...
-
Стек технологий При выборе стека технологий основное внимание уделялось следующим факторам, в порядке убывания значимости: § Кроссплатформенность; §...
-
Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как...
-
Алгоритм создания открытого и секретного ключей - Алгоритм кодировки RSA
RSA-ключи генерируются следующим образом: 1. Выбираются два различных случайных простых числа и заданного размера (например, 1024 бита каждое). 2....
-
Введение - Вычисление максимума функции с некоторыми критериями
Если функция, определенная и непрерывная в заданном промежутке, не является в нем монотонной, то найдутся такие части этого промежутка, в которых...
-
Отображения и их свойства. Пусть X и Y - некоторые множества и ГXY, причем Пр1Г=X. Тройка множеств (X, Y, Г) определяет некоторое соответствие,...
-
Если бесконечное множество оказывается возможным привести во взаимно однозначное соответствие с натуральным рядом чисел, то такое множество называют...
-
Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги
В данном пункте нужно проанализировать используемый алгоритм поиска кратчайшего пути. Алгоритм Дейкстры Находит кратчайший путь от одной из вершин графа...
-
Задание: 1. Прочитать текст "Алгоритм и его свойства", в таблице №1 "Алгоритм и его свойства" проверьте правильное заполнение таблицы. Запишите в тетрадь...
-
Степени матриц Произведение матриц AAA...A, где A - квадратная матрица порядка n, можно записать в виде Ak, где k означает число сомножителей, входящих в...
-
Основные сведения о коде - Построение декодера Рида - Маллера
За время исследования помехоустойчивых кодов была наработана огромная теория и выстроена сложнейшая математическая база помехоустойчивого кодирования....
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Граф переходов конечного автомата лексического анализатора Исходная КС-грамматика G({prog, end., if, else, then, begin, end, while, do, or, and, not,...
-
В основе алгоритма лежит численное исследование пространства управляемых параметров редуктора. Процесс поиска оптимального решения выполняется за четыре...
-
Для создания трехмерной реконструкции сцены или объекта необходимо создать его трехмерную модель и вычислить цвет ее вершин. Для геометрической...
-
ИЕРАРХИЧЕСКАЯ МОДЕЛЬ ДАННЫХ ИМД основана на понятии деревьев, состоящих из вершин и ребер. Вершине дерева ставится в соответствие совокупности атрибутов...
-
Модификации алгоритма Лемпеля-Зива, предложенная Терри Уэлчем - Анализ алгоритма Лемпеля-Зива
В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не...
-
ВВЕДЕНИЕ - Анализ алгоритма Лемпеля-Зива
Одна из задач любой информационной системы обеспечивать хранение и передачу информации. Причем хранение и передача информации занимают определяющее место...
-
Основная проблема, решаемая в аналитической модели: выбор способа вычисления весовых коэффициентов, отражающих степень и характер влияния факторов на...
-
Упорядоченное множество Наряду с понятием множества как совокупности элементов важным понятием является понятие упорядоченного множества или кортежа....
-
Матрица B эквивалентна матрице А в том случае, если существуют такие две неособенные матрицы P и Q, что B=PAQ. Преобразование подобия Рассмотрим линейное...
-
Множество X является подмножеством множества Y, если любой элемент множества X принадлежит и множеству Y. Это определение может быть сформулировано и в...
Некоторые сведения из теории графов - Алгоритмы нескольких махов