2.3    Оценка числа графов

Обозначим через Н™ - число всех сочетаний с повторениями из п эле­ментов по га, т.е. число всех таких семейств, содержащих га элементов из данных п и различных элементов, что один и тот же элемент может вхо­дить в семейство несколько раз. Следующее утверждение доказано в 1.1. Здесь мы приведем второе доказательство.

Утверждение 5. Н"' = С™+те^1.

Пример. Я3 = 4, т.к. на базе {а, 6} существуют только следующие семейства из 3-х элементов:

{а, а, а},       {а, а, 6},       {а, 6,6}, {6,6,6}.

ДОКАЗАТЕЛЬСТВО. Рассмотрим основное множество М = {а\...., ап}. Если п = 1, то Я]™ = 1 = С™ и все доказано. Сделаем предположение ин­дукции об истинности нашего утверждения для п элементного множества и докажем его для множества, содержащего (п + 1) элементов:

N = {аь .. .,ап+і}.

Число сочетаний с повторениями из (гг+1) элементов по га, не содержащих ап+\, равно Я™; число сочетаний с повторениями из (п + 1) элементов по га, содержащих ап+\ ровно один раз, равно Я™-1; число сочетаний с повто­рениями из (п + 1) элементов по га, содержащих ап+\ ровно 2 раза, равно Я™^2 и т.д. Следовательно,

ттт    _ ттт  ,   ттт-2  і  . .    і   0"1  і  і _ пт , \  . . .  \ \ л

11п+1 ~~ -"п   '  11п       ' '  -"п  і  -1- — '  ^те+т^2 ' ' 'іт

/п+т,— 1ф

Докажем индукцией по га, что

Гт    = 1 -I- Г1 4- Г2   А- ■ ■ ■ А- Г7

Если га = 1, то С,!_| = гг+1 = 1 + С*. Пусть искомое равенство верно для га. Докажем его для га + 1. Имеем

Утверждение доказано.

Утверждение 6. ('^)п < п\

ДОКАЗАТЕЛЬСТВО. Так как (1 + ±)п < е, то < п".

Предположим истинность нашего неравенства для п и докажем его для гг+1). Имеем

п + 1)! = п\ ■ (п + 1) > (-Г ■ (п + 1) > 1И±1)! . (п + 1) = (И^у^1.

е'     '       '       е ■ еп     '       '     ' е

Теорема 2. Максимальное число 7 (га) попарно неизоморфных графов без изолированных вершин с га ребрами удовлетворяет неравенству

7(га) < Сі(с2т)т,

где с\,С2 - некоторые константы.

ДОКАЗАТЕЛЬСТВО. Каждый граф с га ребрами имеет не более 2га вершин. На множестве из 2т вершин число пар вершин, которые могут связываться ребрами, не превосходит числа г = Я|то = С|то+1 = т(2т + 1 Тогда искомое число графов с т ребрами 7 (га) не превосходит

Нгт = С™т^ < < {2т:^Г = (1 + ±)т ■ (2еш)т < е • {2ету.

Теорема доказана.

Задача 11. У Вас имеется 3 кувшина А, В, С объемом соответственно 8, 5 и 3 литров. Кувшин А наполнен водой. Вам необходимо разделить воду на 2 равные части, используя пустые кувшины В, С. Можно ли это сделать?

РЕШЕНИЕ. Предлагается следующее решение, использующее язык тео­рии графов. Рассмотрим целочисленную решетку плоскости


 

 

 

 

 

 

 

3

 

 

 

 

 

 

2

 

 

 

 

 

 

1

 

 

 

 

 

 

0

Г 1   2   3  4 5

Каждому распределению воды по кувшинам В и С сопоставим точку (а, 6) нашей решетки, где 6 - количество воды в В и с - количество воды в С. Так как 6 £ {0,1, 2, 3,4, 5}, с £ {0,1,2,3}, то множество возможных узловых точек решетки состоит из 6 х 4=24 точек. Будем считать точки вершинами графа. Две вершины (61,01) и (62,02) соединены (ориентиро­ванным ) ребром, если за одно переливание из состояния (61,01) можно перейти к состоянию (62,02). Наша задача заключается в существовании пути (маршрута) от вершины (0,0) к вершине (4,0). Укажем такой путь: (0,0) -> (5,0) -> (2,3) -> (2,0) -> (0,2) -> (5,2) -> (4,3) -> (4,0). Проиллю­стрируем этот путь графически:

 

►—1

1--1

►—1

 

>—

2\

1 1

 

1 '

 

 

1

О" 1

►——1

2

>-1

3

>-

4

>—

5

 

Задача 12. Решить аналогичную задачу для кувшинов Л, Б, С, объемы которых соответственно равны 12, 7, 4.

ОТВЕТ: (7, 0), (3, 4), (3, 0),(0, 3), (7, 3), (6, 4), (6, 0).