С.В. Яблонский - Введение в дискретную математику (1060464), страница 32
Текст из файла (страница 32)
Мы предполагаем, что никакая внутренняя точка кривой, принадлежащей фигуре 8, не является вершиной или внутренней точкой другой кривой. Определение. Фигура 8 называется геометрической реализацией зрау<а Г, если существует взаимно однозначное соответствие между вершинами фигуры 8 и вершинами графа Г, а такя<е между кривыми фигуры 8 и ребрами графа Г такое, что если (Ь„и Ь,,) (а„а,)„ то Ь„, аи Ь„,. а,. (Соответствующие кривые и ребра соединяют соответствующие вершины.) ч. Не ГРАФЫ н сети 224 Пример 2.
Фигура Э на рис. 1, как нетрудно убедиться, является геометрической реализацией графа Г нз примера 1. Опрашивается, любой ли граф Г можно реализовать з евклидовом пространствег Если этот вопрос решается Рве. 1 положительно, то интересно знать, существует лн такое число р, что всякий граф допускает реализацпю в евклидовом пространстве раамерности р? В последнем случае желательно знать минимальное значение р. Ответ на все эти вопросы для случая конечных графов дают теорема 1 и пример 3.
Теорема 1 представляет некоторую перефразировку известной теоремы из топологии. Теорема 1. Каждый конечный граф Г можно реализовать в трехмерном евклидовом пространстве. Дока аательство. Пусть граф Г содержит гп вершин и й ребер. Вовьмем прямую н через нее проведем связку из й плоскостей. На прямой выберем 1п точек Ь„Ь„..., Ь, сопоставим их вершинам графа соответственно а„а„..., а . Каждому ребру графа Г поставим в соответствие плоскость из пучка. Пусть (аь а,) — ребро графа Г.
В плоскости, соответствующей ребру (~, а,), соединим вершины Ь< и Ь, дутой окружности. Выполним такое построение для всех ребер графа Г, получим фигуру 8. Очевидно, что Э является геометрической реаливацней графа Г. Можно показать, что данная теорема не допускает усиления в направлении понижения размерности евклидова пространства, в котором может быть реализован любой граф. Пример 3.
На рис. 2 изображены два графа. Первый из них связан с решением известной задачи о трех домах и трех колодцах*). Второй — полный ее) граф с пятью е) Задача о трех доках в трех колодцах сосговт в следующем: требуется от каждого дома пролс1кпть тропинку к каждому колодцу и так, чтобы тропинка ве пересекались друг с другом. ее) Го есть граф, содержащий все ребра вида (ао а1), 1 < 1 < <(а;ж, гл, ь РРАФы вершинами. В топологии доказывается, что данные графы не допускают реализации на плоскости.
Доказательства этих фактов мы не приводим. Интересный результат, выясняющий условия плоской реалпзуемости, был получен Л. С. Понтрягиным (28) и Рвс. 2 независимо, но позже Куратовскиы. Киже (теорема 2) приводится без доказательства формулировка этого факта. Определение. Графы Г и Г' называются изоморфными, если существует взаимно однозначное соответствие между их вершинами и ребрами и такое, что соответствующие ребра соединяют соответствующие вершины. С точки зрения этого понятия абстрактный граф и его геометрическая реализация являются изоморфными графами. В силу теоремьу 1 вместо абстрактных конечных графов можно рассматривать их реализации.
Другими словами, с графами можно обращаться как с геометрическими объектами. Введем операцию подразделения ребра графа Г. Пусть (а„а,) — произвольное ребро графа Г и а — объект, не принадлежащий й. Операция подразделения ребра (а„ау) графа Г состоит в построении графа Г', имеющего своими вершинами множество й' = й уу (а), содержащего все ребра графа Г, кроме выделенного (ат, ау), и плюс два новых ребра (аь а), (а, а,), т. в. й)' (Я'8(аи ау))0((а„а), (а, а1)). Граф Г, называется подразделением графа Г„если он может быть получен из Г, путем применения конечного числа раз операции подразделения ребер.
Определение. Графы Г, и Г, называются гомеоморфными, если существуют такие их подразделения, которые иэоморфны. 8 Ввевеиис в и верстку е иетеивтику 226 Ч. 1П. ГРАФЫ И СЕТИ П ример 4. Па рис. 3 изображены два графа Г; и Г,. Эти графы не изоморфны н в то же время гомеоморфны, так как каждый из них может быть подразделен до графа Г, изображенного на рис. 4. Определение. Граф Г' называется подграфом Г, если его вершины и ребра принадлежат графу Г. У'г Рвс.
4 Рвс. 3 Теорема 2 (критерий плоской реализуемости). Длл того чтобы конечный граф Г имел плоскую реализацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфен ни одному из графов рис. 2. $2. Оценка числа графов Пусть ц(Ь) — максимальное число попарно неизоморфных графов без изолированных вершин с Ь ребрами. Теорема 3.
ц(Ь)<с,(с,Ь)",где с~ и с — константы. Доказательство. Очевидно, что граф с Ь ребрами имеет не более 2Ь вершин. Занумеруем вершины графа натуральными числами 1, 2, ... Очевидно, что число сортов ребер, т. е. пар вершин, которые могут связываться ребрами, не превосходит величины Нгг» ( ) = Ь(2Ь+ !).
Поскольку ц(Ь) не превосходит максимального числа занумерованных попарно неизоморфных графов с Ь ребрами, а зто число не больше, чем число сочетаний с повторениями из т элементов по Ь, то 7 (Ь) < Н» (/+» — 1) < (т (- » - О» (2»з Ц- 2»)» ы (»)» <» — — (! + а~ (2еЬ)" <е(2еЬ)», что и требовалось доказать. Гл. 2. Сктн Сл е д с т в и е. Максизь»альное число занумерованных попарно неизомор(бнь«р графов без изолированных вершин с Ь ребрами нв превосходит с,(с,Ь)". Ыы пе делаем здесь оценок снизу для 7(Ь) и потому лишены возмоя«кости повять качество полученной верхней оценки величины 7(Ь).
Глава 2 СЕТИ й 1. Сети и их свойства Обобщим понятие графа. Определение. Мяожество И- (а„а„...) и иабор 3(=(Е„; К„Е„...), в котором каждое Е, есть набор алемеятов из И, т. е. Еь =(а»,,о, а»«ин ...), называется сетью и обозначается И(Е;, Е„Е„...). Объекты миожества И пазызаются вершинами, а объекты из набора Еь — полюсами сети з). Пример 1. Пусть И (1, 2, 3, 4, 5, 6, 7), У(= (Е„Е„Е„Е„Е„Е,), где Е. =(1, 2, 6), Е, (1, 3, 3, 4, 5), Еь =(4, 4, 4, 5, 6), Еь Еь = (2, 4), Еь — (2, 5, 6, 7). Тогда И(Е», 'Еь, Еь, Еь, Еь, Е,) будет сетью. В случае, когда множество И и набор 3( конечны, сеть будет называться конечной. Так, например, только что рассмотренная сеть будет конечной.
Сеть, в которой бесконечно по крайней мере И илп 3(, называется бесконечной. Частным случаем бесконечных сетей являются счеткые сети, т. е. бесконечные сети, у которых И и з( ие более чем счеткы. Подобно тому как это было сделано в случае графов, можно ввести покятпе геометрической реализации для конечной или счетной сети. Прежде всего введем одно ») В литературе встречаются близкие понятия: освятив «блоксхемы» в понятие «гваерграфа», Повятае блок-схемы уже, чем повятяе сетя; а понятие гвпергрзфа отлачается от повятйй блоксхемы в сети везяачвтельяой деталью, Понятие блок-схемы появилось раньше пояятия сети, а понятие гилерграфа — позже.
См., например, (7, Зх). ч, 1!1. гглФы и свж» 228 обозначение. Если Š— набор, то через (Е> будем обозначать множество всех объектов из Е. Пусть й(Е;, Е„...)— сеть. Разобьем множество й на три непересекающиеся части: й, — <Ец) — множество полюсов, й, й~ Ц (Е») — множество »эо изолированных вершин, отличных от полюсов, й< — прочие вершины.
Каждой вершине из множеств й, и й, сопоставим в трехмерном евклидовом пространстве точку так, чтобы различным вершинам соответствовали различные точки. Эти точки мы пометим символами соответствующих вершин а, из й. Очевидно, полюсам будут соответствовать точки, помеченные символами»»м<»м, а~»»м< ...
Каждому набору. Е» (оу»(») нч»»о, ...) из И (»>$) сопоставимвтрехмерном евклидовом пространстве круг (если Е< содержит авг %1 йз о о ° ° ° о о ° * ° ..ф ч з«<м а„,»и ат,»е » уш Рзс. $ один или два объекта, то можно вместо круга брать вершину или дугу), на периферии которого выбраны попарно различные вершины, помеченные снмволаына,<»»н а,,»»ь ... из набора Е». При этом мы требуем, чтобы круги попарно не пересекались и не содержали выбранных ранее вершин (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
