Доказательство по индукции
Теорема:! – число элементов из множества , причём эти элементы не удовлетворяют ни одному из свойств от . Тогда и суммирование берется по всем наборам длины . Задача (о конечных беспорядках): ! даны предметов и есть ящиков . Считаем, что вместимость ящика – предмет. Сколькими способами можно разместить все предметы так, чтобы номера ячеек и номера предметов не совпадали. Решение: ! свойство означает, что предмет попал в ячейку . Тогда . Заметим, что в этой задаче основное множество состоит из распределения всех предметов по ячейкам. И тогда по теореме 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) Свободный член равен .
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1059)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |