Доказательство по индукции

Теорема:! – число элементов из множества , причём эти элементы не удовлетворяют ни одному из свойств от . Тогда и суммирование берется по всем наборам длины .

Задача (о конечных беспорядках): ! даны предметов и есть ящиков . Считаем, что вместимость ящика – предмет. Сколькими способами можно разместить все предметы так, чтобы номера ячеек и номера предметов не совпадали.

Решение: ! свойство означает, что предмет попал в ячейку . Тогда . Заметим, что в этой задаче основное множество состоит из распределения всех предметов по ячейкам. И тогда по теореме 2 ответом будет являться число .

Графы.

Опр.: Граф – это , где – вершины и – рёбра.

Опр.: Графы без кратных рёбер и петель называют простыми.

Опр.: Степенью вершины называется число рёбер, инцидентных вершине .

Лемма 1 (о рукопожатиях): Сумма степеней всех вершин равна удвоенному числу рёбер, т.е. .

Следствие: Число вершин нечётной степени чётно.

Лемма 2: .

Доказательство: По лемме 1 .

Доказательство: .

Опр.: Пустой граф – это .

Опр.: Полный граф – это граф, у которого 2 вершины смежные.

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

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

Опр.: Цикл – это граф, у которого степень вершины равна 2, .

Изоморфизм графов.

Опр.: Два графа и называются изоморфными, если биекция . . Если , это автоморфизм графа .

Опр.: Множество всех автоморфизмов является группой относительно операций композиций. – группа всех автоморфизмов графа .

Опр.: Функция, аргументы которой являются графы, называется графовым инвариантом, если на изоморфных графах она принимает одинаковые значения. Это функции: число вершин, число рёбер, число вершин данной степени, число циклов данной длины, число мостов.

Матричное задание графов.

Опр.: . Определим матрицу , где , если и – смежные; иначе . – матрица смежности ,однозначно определяет граф. Пока графы без кратных рёбер и петель. Свойства матрицы: 1) Она симметричная; 2) Число единиц в -м столбце (строке) равно степени вершины ; 3) Если и изоморфны, то матрица-перестановка .

Опр.: Матрица перестановка – это матрица, в которой единица так, что в каждом столбце и строке только одна единица.

Опр.: Введём матрицу , где , если инцидентна ; – иначе.

Опр.: Операции с графами: 1) ; 2) ; 3) , где – не просто разность и , но и все рёбра, которые были инциденты в графе этим вершинам; 4) , где – вершины, которых раньше не было; 5) , операция определена только при , где – рёбра, связывающие с .

Укладка графов в пространстве.

Опр.: Граф называется плоским, если он изображён на плоскости без пересечения рёбер.

Опр.: Граф называется планарным, если он изоморфен плоскому графу.

Опр.: Будем говорить, что граф стягивается к графу , если он получен из удалением некоторых вершин степени 2.

Теорема (критерий планарности): Граф планарен не содержит подграфов, стягиваемых графом и .

Теорема: граф укладывается в .

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

Теорема: Граф является планарным он укладывается на сфере.

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

Эйлеры графы.

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

Опр.: Связные части графа называются компонентами.

Лемма 1:Если в конечном графе степень вершины не меньше 2, то он содержит цикл.

Доказательство: Строим последовательность . 1) любая; 2) и смежна с ; 3) При берем и смежную с и не смежную с . т.к. граф конечен, то рано или поздно вершина встретится два раза.

Теорема (критерий эйлеровости): Связный граф Эйлеров степень его вершины чётна.

Доказательство: При проходе через вершину её степень увеличивается на 2. Индукция по числу рёбер в графе . По лемме 1 в цикл . Удалим из графа все рёбра цикла . Получим граф . Число рёбер числа рёбер в графе . По индукционному предположению в Эйлеров маршрут.

Опр.: Алгоритм построения Эйлерова маршрута: 1) Начинаем с вершины; 2) Убираем пройденные ребра и изолированные вершины; 3) Идём по мосту нет других вариантов.

Опр.:Назовём граф полуэйлеровым, если он обладает маршрутом, содержащим каждое ребро ровно 1 раз.

Теорема (критерий полуэйлеровости): Связанный граф полуэйлеров число вершин нечётной степени ноль или две.

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

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

Теорема: ! – граф с вершинами при . Если степень вершины , то – гамильтонов.

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

Плоские графы.

Опр.: Граф называется плоским, если он уложен на плоскости без пересечения рёбер (в конкретной реализации).

Теорема 1 (о плоских графах): ! плоский граф с вершинами, ребрами, гранями и компонентами связности. Тогда , в частности, если граф связен, тогда .

Доказательство: Индукция по . База индукции: . Тогда есть пустой граф , т.к. . Рассмотрим случаи: 1) – связный граф, т.е. . Индукционный шаг: Для рёбер теорема верна. Добавим новое ребро . Возможны 2 ситуации: а) ; б) ; 2) имеет компонент связности: . В силу доказанного пункта 1 справедливо: , где – число вершин, граней и ребер компоненты соответственно. .

Теорема 2:В связанном планарном графе с вершинами и ребрами. Тогда , при .

Доказательство: . Возможны 2 случая: 1) *треугольникбез1ребра*; 2) *треугольник*. ! . В этом случае грань ограничена не меньше, чем ребрами , где – число граней в некоторой плоской реализации графа. По теореме 1 .

Теорема 3: Графы и не планарны.

Доказательство: 1) ! планарен. Тогда по теореме 2 . Противоречие; 2) ! планарен. т.к. двудольный граф, то он не содержит циклов нечётной длины. В частности цикла грань в плоской реализации графа ограничена не меньше, чем 4-я рёбрами . По теореме 1: . Это противоречие.

Теорема 4: планарный граф содержит вершину степени .

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

Двойственные графы.

Опр.: ! – связный плоский граф. Построим по этому графу новый граф (двойственный). 1) Вершины есть точки на гранях; 2) Через каждое ребро графа проведём линию , соединяющую две точки и из соседних граней (возможно одинаковых) и объявим их рёбрами графа .

Теорема 5: Если – связный плоский граф, то такой же, причем где - это число вершин, рёбер и граней в графах и соответственно.

Расстояние на графах.

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

Опр.: – максимальное удаление от .

Опр.: – диаметр графа.

Опр.: – радиус графа. Вершина, на которой этот минимум достигается – центр графа.

Деревья и леса.

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

Опр.: Граф, у которого все связные компоненты – деревья, называется лес.

Теорема: Следующие условия эквивалентности: 1) Граф – дерево; 2) 2 вершины из связаны единственной цепью; 3) Граф не содержит циклов и, добавляя одно ребро, получим ровно один цикл; 4) Граф связен и , где – число рёбер, – число вершин.

Доказательство: 1) 4) Индукция по числу вершин. Из пункта 4 следует следствие.

Следствие: Если – лес с вершинами, ребрами и компонентами связности (деревьями), то .

Свойства: ! – граф с сами знаете чего. – циклическая функция графа . Свойства : 1) Если – лес, то ; 2) в есть цикл; 3) равна числу рёбер, выкинув которые, получится лес; 4) , где – компоненты.

Перечисление графов.

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

Опр.: Два помеченных графа и называются изоморфными (как помеченные), если они изоморфны и образ и прообраз имеют одинаковые метки.

Опр.: Дерево, содержащее все вершины, связного графа, называется его остовным деревом.

Теорема (Кэли): Число помеченных деревьев с вершинами равно .

Раскрашивание графа.

Введение: – граф без петель, цветов.

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

Опр.: Для всякого планарного графа .

Опр.:! – число раскрашиваний графа в цветов. – хроматическая функция графа .

Теорема 1: Хроматическая функция является многочленом от .

Доказательство: ! – две несмежные вершины в графе . Построим 2 новых графа и из . 1) строится из соединением ребром; 2) строится отождествлением вершин и кратных рёбер. . Возможны 2 случая: а) Вершины графа окрашены в разные цвета; б) Вершины графа окрашены в одинаковые цвета. Осталось заметить, что проделывая аналогичную процедуру в и , если у них есть несмежные вершины, то мы получим, что хроматическая функция исходного графа будет совпадать с суммой хроматических функций полных графов. А это будет многочлен.

Опр.: Свойства 1) Старший коэффициент равен ; 2) Коэффициент при равен , где – число рёбер в ; 3) Знаки чередуются; 4) Свободный член равен .