Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Введем операцию подразделения ребра графа Г. Пусть (аи а}) — произвольное ребро графа Г и а — объект, не принадлежащий 9й. Операция подразделения ребра (щ, щ) графа Г состоит в построении графа Г', имеющего своими вершинами множество
содержащего все ребра графа Г, кроме выделенного (щ, а,-), и плюс два новых ребра {аи а), (а, а.,), т. е.
Граф Г2 называется подразделением графа Гі, если он может быть получен из Гі путем применения конечного числа раз операции подразделения ребер.
Определение. Графы Гі и Г2 называются гомео-морфпыми, если существуют такие их подразделения, которые изоморфны.
15 С. В. ЯбловсіфЙ
Рис. 2
2Г = 2Я11Ы,
9Ї' = (ЭЛ (а,-, а,)) и {(я* а), (а, а}) }.
Пр и мер 4. На рис. 3 изображены два графа Г, и Г2. Эти графы не изоморфны, и в. то же время гомеоморфны, так как каждый из них может быть подразделен до трафа Г, изображенного на рис. 4.
Определение. Граф Г' называется подграфом Г, если егр вершины и ребра принадлежат графу Г.
Теорема 2 (критерий плоской реализуемости). Для того чтобы конечный граф Г имел плоскую реализацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфен ни одному из графюе рис. 2.
§ 2. Оценка числа графов
Пусть у(й) —максимальное число попарно неизоморфных графов без изолированных вершин с к ребрами.
Теорема 3. 'у (к) < (с2&}\ где Сі и сг — константы.
Доказательство. Очевидно, что граф с к ребрами имеет не более 2к вершин. Занумеруем вершины графа натуральными числами 1, 2, ... Очевидно, что число сортов ребер, т. е. пар вершин, которые могут связываться ребрами, не превосходит величины
г-Н!л = (2'‘+‘) = й(2й + 1).
Поскольку 7(&) не превосходит максимального числа занумерованных попарно неизоморфных графов с к ребрами, а это число не больше, чем число сочетаний с повторениями из г элементов по к, то
ї(д)<я;=(г+^1)<
{г+ь-і)Ь ^,{гі? + 2ЬУ' . LYln-г.,h -.,о.М0 ^ ы < - ТТуГ = + к ) \2ек) < е (2еН) *
[т)
что и требовалось доказать,
С л е д с т в и е. Максимальное число занумерованных попарно неизоморфных графов без изолированных вершин с й ребрами, не превосходкт с1{с2Ь)Г1.
Мы не делаем здесь оценок снизу для 'у(й) и потому лишены возможности понять качество полученной верхней оценки величины К (Л).
Глава 2
СЕТИ
§ 1. Сети и их свойства
Обобщим понятие графа.
Определение. Множество 3?? = {аи д2, ...) и набор 91 = {?„; Еи Е2, . - .1, в котором каждое Е, есть набор элементов из 2Я, т. е. ?, = ...), называется
сетью и обозначается ?Ш(?„; Е{, Е2, ...). Объекты мно7 жестка 2Я называются вершинами, а объекты из набора Е0 — полюсами сети*).
Пример 1. Пусть
9Я = И, 2, 3, 4, 5, 6, 7}, 91 - {Ер, Еи ?2, Е3, ?4, ?5},
где
?„-(1,2,6), ?1 = {1, 3, 3, 4, 5), ?2 = {4, 4, 4, 5, 6), Е3 — ?4 — (2, 4), ?5-(2, 5, 6, 7).
Тогда 9Л(?„; Еь, ?2, ?3} ?4, ?6) будет сетью.
В случае, когда множество 9Л и набор 91 конечны, сеть будет называться конечной. Так, например, только что рассмотренная сеть будет конечной. Сеть, в которой бесконечно по крайней мере ЙЯ или 91, называется бесконечной. Частным случаем бесконечных сетей являются счетные сети, т. е. бесконечные сети, у которых 591 и 91 не более чем счетны.
Подобно тому как это было сделано в случае графов, можно ввести понятие геометрической реализации для конечной или счетной сети. Прежде всего введем одно
*) В литературе встречаются близкие понятия: понятие «блок-схемы» и понятие «гиперграфа». Понятие блок-схемы уже, чем понятие сети; а понятие гиперграфа отличается от понятии блок-схемы и сети незначительной деталью. Понятие блок-схемы появилось раньше понятия сети, а понятие гиперграфа — позже. См., например, [7, 32].
15*
обозначение. Если Е — набор, то через </?> будем обозначать множество всех объектов из Е. Пусть 5Ш{Ей\ Ей...) — сеть. Разобьем множество Ш на три непересекающиеся части:
= (Е0У — множество полюсов,
?Ш2 = 5К\ и — множество
изолированных вершин, отличных от полюсов, — прочие вершины.
Каждой вершине из множеств 5^ и Ш2 сопоставим в трехмерном евклидовом пространстве точку так, чтобы различным вершинам соответствовали различные точки. Эти точки мы пометим символами соответствующих вершин из 2Я. Очевидно, полюсам будут соответствовать точки, помеченные символами йуро), й\’а<оь • .. Каждому набору, ау2(*ь ...) из ^ (ь ^ 1) сопоставим в трех-
мерном евклидовом пространстве круг (если Ei содержит
Щ 5Нг Щ
Рис. 1
один или два объекта, то можно вместо круга брать вершину или дугу), на периферии которого выбраны попарно
разЛИЧНЫе вершИНЫ, Помеченные СИМВОЛамИЙу^), а>’2(г)} ..«
из набора Ей При этом мы требуем, чтобы круги попарно не пересекались и не содержали выбранных ранее вершин (рис. 1).
Затем все точки, которые помечены одним и тем же символом из 2Й, соединяются связной компонентой Дополнительно потребуем, чтобы связная компонента Ас с построенными ранее вершинами и кругами имела общими только точки, помеченные символом аи и чтобы связные компоненты А\ и Л, (г1^/) не имели общих точек. Данную фигуру будем называть геометрической реализацией исходной сети. Очевидно, что образами вершин ах из Ш?2 сети ЗЛ^о; Е1а ...) будут изолированные вершины
