1. Эйлеров и Гамильтонов обход. Экстремальные задачи связанные с ними.
Цикл — замкнутая цепь. Для орграфов цикл называется контуром.
Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной).
Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь)
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Эйлеров граф — граф, содержащий эйлеров цикл.
Полуэйлеров граф — граф, содержащий эйлеров путь (цепь).
Эйлеров цикл/путь существуют только в связных графах или в графах, которые после удаления всех одиночных вершин превратятся в связные.
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно-связан и для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из неё и выходит.
Эйлеров путь в неориентированном графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечётной степени.
Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.
Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом.
Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию».
Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) - одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
2. Разбиения (графовые числа)
Р
азбиением
неотрицательного целого числа п
называется конечный набор неотрицательных
целых имеет., сумма которых равна п.
В этом смысле разбиение числа 4 может содержать произвольное конечное число пулевых слагаемых. Разбиение графа — это представление числа 2q в виде суммы степеней вершин графа
Только два из пяти разбиений числа 2q=∑di 4 на положительные слагаемые реализуются графами.
Разбиение =∑di числа n на р частей (слагаемых) называется графическим , если существует граф, степени вершин которого равны di.
3.Теорема Эйлера для плоских графов.
Задача. Доказать теорему Эйлера для плоского графа. (Граф называется плоским, если его можно расположить на плоскости так, чтобы ребра пересекались только в вершинах.). Если в графе есть цикл, то есть внутренняя грань. Возьмем цикл, ограничивающий внутреннюю грань. Выкинем из него одно ребро. Граф остался связным, плоским. Число Р уменьшилось на один, но и число Г уменьшилось на один, т.к. грань, которая была по сторону от стертого ребра стерлась. Таким образом, число В+Г-Р не изменилось. Если в графе опять есть цикл мы поступаем так же. Т.к. ребер в графе конечное число, а количество ребер постепенно уменьшается, то когда-нибудь наше стирание его рёбер закончится. Т.е. мы придем к ситуации, что число В+Г-Р не изменилось по сравнению с первоначальным, граф остался связным, плоским и циклов в графе нет. => граф стал деревом, а грань осталась одна - внешняя. Продолжаем стирать грани. Число Р уменьшается на один, число В уменьшается на один, число В+Г-Р не меняется. Полученный граф снова дерево, он плоский и связный, а число вершин у него уменьшилось => поступаем так, пока не останется две вершины, соединенные ребром. Тут уже не сложно посчитать, что В+Г-Р=2+1-1=2, а число В+Г-Р не менялось => для начального графа оно тоже 2.