Что такое компланарный граф

Планарный граф

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

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

Содержание

Два примера непланарных графов

Здесь мы пользуемся интуитивным понятием слова «линия», подробнее см. в соответствующей статье.

Полный граф с пятью вершинами

Лемма. Полный граф с пятью вершинами (К₅) нельзя уложить на плоскость.

«Домики и колодцы»

Задача о трёх колодцах. Есть три дома и три колодца. Можно ли так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. Мосты строить нельзя.

Лемма. Полный двудольный граф с тремя вершинами в каждой из долей (К_3,3) нельзя уложить на плоскость.

Теорема Понтрягина-Куратовского

Очевидно утверждение: если граф G содержит подграф, гомеоморфный K₅ или K_3,3, его невозможно разложить на плоскости. Оказывается, верно и обратное.

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу из пяти вершин (K₅) или графу «домики и колодцы» (K_3,3).

Теорему также можно сформулировать в следующем варианте (иногда его называют «теорема Вагнера»).

Граф планарен тогда и только тогда, когда не содержит подграфов, стягивающихся в K₅ или K_3,3.

Признаки непланарных графов

Формула Эйлера

Для связного плоского графа справедливо следующее соотношение между количеством вершин , ребер и граней (включая внешнюю грань):

Оно было найдено Эйлером в 1736 г. [1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум. Формула имеет множество полезных следствий. Если каждая грань ограничена не менее чем тремя ребрами (при условии, что в графе больше двух ребер), а каждое ребро разделяет две грани, то

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

Планарные графы в задачах

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

Спрямление графа. Любой плоский граф можно перерисовать так, чтобы он остался плоским, а рёбра стали прямолинейными.

См. также

Примечания

Ссылки

Полезное

Смотреть что такое «Планарный граф» в других словарях:

планарный граф — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN planar graph … Справочник технического переводчика

ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия

Граф Петерсена — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей … Википедия

Плоский граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

плоский граф — планарный граф — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы планарный граф EN flat graph … Справочник технического переводчика

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

Планарность — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия

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

Гамма-алгоритм — Гамма алгоритм алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация … Википедия

Источник

Основные определения теории графов

Содержание

Ориентированные графы [ править ]

Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Источник

Теория графов в криптографии. Обзор основных подходов

Введение

Правильная раскраска графа в протоколах нулевого разглашения

Задача о правильной раскраске графа является одной известнейших проблем в области разметки графов. Формулируется она следующим образом: если дан граф

и количество цветов k (хроматическое число), то существует ли такая раскраска вершин графа G, при которой никакие две вершины, соединенные ребром, не были бы окрашены одним цветом?

Поиск хроматического числа, при котором данная задача разрешима, входит в класс NP-полных (т.е. решаемых не менее чем за полиномиальное время, что очень медленно). Более того, в данной работе было доказано, что при k=3 в случае планарного 4-регулярного графа доказать раскрашиваемость или ее отсутствие также можно не быстрее полиномиального времени. Поэтому даже 3-раскрашиваемость графа имеет большой интерес в криптографии и имеет практическое применение, к примеру, в протоколах нулевого разглашения.

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

Приведем пример. Пусть к студенту подходит школьник начальных классов и просит его решить квадратное уравнение. Из-за своего самолюбия, первый не желает раскрыть ребенку алгоритм нахождения дискриминанта, и потому просто диктует численный ответ. Но школьник хочет убедиться в том, что его не обманули. Тогда студент просит составить другое произвольное квадратное уравнение, чтобы повторить эксперимент. Если и в этот раз ребенок, подставив числа в выражение, получит тождество, то его степень доверия к человеку вырастет. Этот процесс генерации квадратных уравнений и его корней продолжается настолько долго, насколько требуется, чтобы убедить проверяющего в том, что источник достоверен. Важно отметить, что любой протокол нулевого разглашения должен удовлетворять трем свойствам:

Являться полным (порог доверия может быть задан сколь угодно близким к 100%).

Являться корректным (неправильный ответ приводит к потере доверия).

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

Если алгоритм нахождения корней квадратного уравнения тривиален, то задача правильной раскраски графа NP-полна, потому ее решение для чрезмерно больших графов имеет коммерческую ценность. Предложим алгоритм нулевого разглашения на основе 3-раскрашиваемости с использованием распространенного протокола RSA.

Пусть доказывающая сторона, Алиса, знает правильную раскраску в три цвета у фиксированного планарного 4-регулярного графа G. Она хочет доказать контролирующей стороне, Бобу, что знает верное решение (структура графа G ему известна).

Планарный 4-регулярный граф с хроматическим числом k = 3

Для каждой вершины Алиса формирует случайное число r и заменяет в нем два младших бита на 00 (R), 01(G), 10(B) соответственно.

Для каждой вершины Алиса формирует параметры для RSA.

для каждой вершины посылает Бобу значения

Теперь Боб случайно выбирает в графе G одно ребро и сообщает Алисе данные об этом ребре. В ответ Алиса высылает два числа:

На основе которых Боб вычисляет цвета вершин, которые соединены выбранным ребром:

0,\ G=(V,E)» alt=»N=a|E|,\ a>0,\ G=(V,E)» src=»https://habrastorage.org/getpro/habr/upload_files/1cb/aa0/e67/1cbaa0e6776dd2f9e97f1fe2f7333fef.svg» width=»245″ height=»22″/>

Данный алгоритм удовлетворяет условию полноты. Вероятность того, что Алиса не разоблачена, составляет:

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

Поиск гамильтонова цикла в графе

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

Опишем идею алгоритма. Пусть Алиса знает гамильтонов цикл в графе Г и хочет доказать это Бобу (граф ему известен).

Алиса строит граф G, изоморфный графу Г. К примеру, она перенумеровывает вершины, сохраняя их первоначальные связи. Полученный граф представляется матрицей смежности H.

Матрица H шифруется в F, к примеру, по тому же алгоритму RSA:

и отправляется Бобу.

Получив матрицу F (зашифрованный граф G), Боб задает Алисе один из двух вопросов:

Какой гамильтонов цикл у графа G (а)?

Действительно ли G изоморфен Г (б)?

На вопрос (а) Алиса расшифровывает в F ребра, соответствующие гамильтонову циклу в G. На вопрос (b) Алиса расшифровывает граф G полностью, а также предоставляет перестановки, с помощью которых из Г получился G.

Получив ответ, Боб проверяет правильность расшифровки путем повторного шифрования Г и сравнения с F. Таким образом, он убеждается либо в корректности гамильтонова цикла в G, либо в изоморфности графов Г и G. Далее, если обмана зафиксировано не было, увеличить степень доверия и перейти к началу.

Отметим важные аспекты данного протокола. Во-первых, зачем Алисе строить изоморфный граф? Ответ: без этого Боб, получив ответ на вопрос (a), узнал бы гамильтонов цикл в исходом графе Г, что противоречит условию нулевого разглашения.

В-третьих, зачем Бобу задавать два вопроса, а не ограничиться лишь первым? В таком случае Алиса смогла бы сгенерировать свой собственный граф с уже имеющимся гамильтоновым циклом и, очевидно, Боб не обнаружит никаких противоречий в том, что гамильтонов цикл существует и корректен.

Вероятность обмана на t итерациях не превосходит

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

Графы как представление обобщённых клеточных автоматов

Поиск псевдослучайных функций является важной задачей криптографии. Они используются в блочных шифрах (AES) и алгоритмах хеширования (SHA-3). Существуют критерии качества псевдослучайных функций: выполнение строгого лавинного эффекта, анализ на коллизии, степень нелинейности и др. Они в той или иной степени оценивают близость функции к случайной, для чего существуют стандартизированные пакеты тестов (NIST statistical test suit).

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

ГПСЧ на основе регистра сдвига (период не максимальный)

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

Граф ГПСЧ на регистре сдвига с точки зрения клеточного автомата

Таким образом, «качество» псевдослучайной функции в рамках рассматриваемой модели (клеточного автомата) будет определяться решением трех задач:

Как задать входные значения и номер итерации?

Какова структура графа обобщённого клеточного автомата?

Как задать локальные функции связи?

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

Быть приближенным к случайному (для псевдослучайности функции)

Иметь наименьший диаметр из теоретически возможных (для экономии аппаратных ресурсов)

Быть регулярным с минимальной степенью связности (для простоты задания локальных функций связи и повышения эффективности аппаратной реализации)

Не быть двудольным (для исключения быстрого рекурсивного разбиения на подграфы)

Быть масштабируемым на разное число ячеек памяти

есть максимальный по модулю, но не равный d, компонент спектра R. Чем же R отличаются от других?

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

Сгенерировать случайный регулярный граф с заданным числом вершин.

Проверить граф на связность. Если он не связен, перейти к п.1.

Ниже приведен пример сгенерированного таким образом графа Рамануджана:

Randomly-generated 3-regular Ramanujan graph with N = 16 vertices

О графе состояний детерминированного генератора псевдослучайных чисел

Рассмотрим пример. Пусть с помощью ГПСЧ была получена последовательность чисел: <1, 5, 3, 3, 2, 4, 6, 2, 0, 4>. Тогда граф состояний будет выглядеть следующим образом:

Граф сосотояний ГПСЧ

Рассмотрим более практичный пример. Пусть дан простой детерминированный ГПСЧ, у которого каждое состояние имеет один образ (линейно конгруэнтный генератор, генератор на регистре сдвига, и др.). Пусть этих состояний всего 10 (от 0 до 9 включительно). При тестировании устройства была получена очень длинная последовательность псевдослучайных чисел, и после ее обработки построили граф состояний:

Граф состояний детерминированного ГПСЧ

Видно, что данный генератор отнюдь не идеальный: при максимальном периоде 10 на графе можно найти циклы длиной 5, 3 и даже 1. Граф самого безопасного ГПСЧ на десяти состояних должен был бы выглядеть так:

Граф состояний детерминированного ГПСЧ с максимально возможным периодом

Очевидно, что на практике число состояний детерминированного ГПСЧ делают очень большим. Это увеличивает вероятность того, что средняя длина цикла велика. В хороших ГПСЧ она достигает трехзначной степени двойки. Наличие циклов меньшей длины ухудшает его качество, т.к. может привести к полной детерминированности маленького и замкнутого множества состояний. Циклы в графе можно искать c помощью поиска в глубину с отслеживанием ранее проиндексированных вершин.

Заключение

Таким образом, в данной статье были рассмотрены базовые понятия и алгоритмы из теории графов, имеющие практическое применении в криптографии. Освещены такие понятия, как NP-полнота, нулевое разглашение и др. Приведено множество иллюстративных примеров (граф Рамануджана, ГПСЧ на регистре сдвига) и реализаций алгоритмов с ссылками на источники. Надеюсь, что данная статья будет полезной для любопытных читателей.

Источник

Теория графов. Основные понятия и виды графов

Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).

Теория графов

В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.

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

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

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

Давайте на примере.

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

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

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

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

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

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

Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.

Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.

Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.

Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.

Основные понятия теории графов

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

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

В любом графе сумма степеней всех вершин равна удвоенному числу ребер.

Доказательство леммы о рукопожатиях

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

Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).

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

Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.

Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.

Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.

Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.

Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Путь и цепь в графе

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

Циклом называют путь, в котором первая и последняя вершины совпадают.

Путь или цикл называют простым, если ребра в нем не повторяются.

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

Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.

Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.

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

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

Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.

Визуализация графовых моделей

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

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

Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.

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

Виды изобразительных соглашений:

Виды графов

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

Ориентированные и неориентированные графы

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

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

Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.

Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы

Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».

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

Пустой граф — это тот, что состоит только из голых вершин.

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

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

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

Двудольный граф

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

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

Эйлеров граф

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

Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?

Регулярный граф

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

Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.

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

Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:

Гамильтонов граф

Гамильтоновым графом называется граф, содержащий гамильтонов цикл.

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

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

Взвешенный граф

Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.

Графы-деревья

Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.

Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.

Определение дерева

Деревом называется связный граф, который не содержит циклов.

Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.

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

Простым путем называется путь, в котором никакое ребро не встречается дважды.

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

Дерево — минимальный по числу рёбер связный граф.

Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

Определения дерева:

Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.

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

Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:

Теоремы дерева и их доказательства

В дереве с более чем одной вершиной есть висячая вершина.

Доказательство первой теоремы:

Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.

Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.

В дереве число вершин на 1 больше числа ребер.

Доказательство второй теоремы:

Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n

У любого связного графа есть остовное дерево.

Доказательство третьей теоремы:

Чтобы найти остовное дерево графа G, можно найти цикл в графе G и выкинуть одно ребро цикла — потом повторить. И так пока в графе не останется циклов. Полученный граф будет связным, так как мы выкидывали рёбра, не нарушая связность, но в нём не будет циклов. Значит, он будет деревом.

Теория графов и современные прикладные задачи

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

Графы и задача о потоках

Система водопроводных труб в виде графа выглядит так:

Каждая дуга графа отображает трубу. Числа над дугами (весы) — пропускная способность труб. Узлы — места соединения труб. Вода течёт по трубам только в одном направлении. Узел S — источник воды, узел T — сток.

Задача: максимизировать объём воды, протекающей от источника к стоку.

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

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

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

Графы и сетевое планирование

В задачах планирования сложных процессов, где много разных параллельных и последовательных работ, часто используют взвешенные графы. Их еще называют сетью ПЕРТ (PERT).

PERT (Program (Project) Evaluation and Review Technique) — техника оценки и анализа программ (проектов), которую используют при управлении проектами.

Сеть ПЕРТ — взвешенный ациклический ориентированный граф, в котором каждая дуга представляет работу (действие, операцию), а вес дуги — время, которое нужно на ее выполнение.

Если в сети есть дуги (a, b) и (b, c), то работа, представленная дугой (a, b), должна быть завершена до начала выполнения работы, представленной дугой (b, c). Каждая вершина (vi) представляет момент времени, к которому должны быть завершены все работы, задаваемые дугами, оканчивающимися в вершине (vi).

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

Источник

• ← Что такое компланарные окна
• Что такое компланарный погонаж →