Граф плоский граф дерево

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

Гомеоморфные графы

Теорема (Куратовский, 1930) Граф планарен тогда и только тогда, если не содержит подграфов, гомеоморфных

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

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

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

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

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

В дереве одна грань, то есть . Операция удаления ребер из графа не меняет число его вершин, то есть . По теореме 2.1 (см. лекцию 2), в дереве . Отсюда , то есть , а потому или .

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

Триангулированный граф

Рассмотрим плоский граф с пятью вершинами.

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

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

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

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

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

Задачи

Задача 1. На участке три дома и три колодца. От каждого дома к каждому колодцу ведет тропинка.

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

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

Предположим, что граф — плоский, то есть существует его плоское представление. Граф — связный, он не имеет ни одного моста, поэтому не имеет и перегородок. По формуле Эйлера, . Здесь — число вершин, — число ребер, — число граней с учетом бесконечной грани. Подсчитаем число вершин и ребер: = 6, = 9, поэтому .

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

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

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

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

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

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

Источник

Деревья

Определение 13 (Дерево). Связный граф без циклов называется деревом.

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

Пример 5 (генеологическое дерево). На рисунке показано библейское генеологическое дерево.

Определение 14 (Лес, листья). Граф без циклов называется лесом. Вершины

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

3 Раскраска, плоские графы Раскраска графов

Определение 15 (Раскраска). Раскраской графа G = (V,E) называется отображение : V  N . *

Определение 16 (Правильная раскраска). Раскраска называется правильной, если образы любых двух смежных вершин различны: (u) (v), если (u,v)  I. Хроматическим числом графа называется минимальное количество красок, необходимое для правильной раскраски графа.

Пример 6 (раскраска). На следующем рисунке показана правильная раскраска.

Грани графа

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

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

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

Определение 18 (Грань графа). Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.

Данное понятие грани, по-существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник «расплющиваем» так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали «исчезнет», но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.

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

Когда мы говорим «плоский граф», мы имеем в виду геометрический объект. Однако, конечно же не все его геометрические свойства нам важны (например, неважен абсолютный размер). Поэтому точнее считать, что плоский граф – это трёхосновная модель , где V – множество вершин, E – множество рёбер, S – множество граней, I – отношение инцидентности, а B – отношение ограниченности, связывающее рёбра с ограничиваемыми ими гранями.