Метод построения функции Гранди на графе

Выбираются максимально внутренне устойчивые множества , и полагается , .

Выбирается максимально внутренне устойчивое множество Х₂ в графе g с количеством Х без Х₁ ― G(X \ X₁) и полагается: . Продолжая этот процесс, получаем функцию Гранди для графа G(X).

Пример построения функции Гранди для графа:

Нарисуем табличку

Рис. 54

Таким образом, получили функцию Гранди.

Свойства хроматического числа

Основные свойства отразим в утверждениях:

1. Граф является би-хроматическим, т.е. имеет хроматическое число в том и только том случае, если он не содержит циклов нечётной длины.

2. Пусть G(x) – симметрический граф. Чтобы граф G(x) был р-хроматическим, необходимо и достаточно, чтобы он допускал функцию Гранди, для которой .

Рассмотрим метод проверки раскрашивания графа G(x) посредством р-цветов.

Полагаем:

1. 

2. 

3. Каждая вершина может быть окрашена только в один цвет, поэтому

4. Т.к. две смежные вершины не могут быть окрашены одним цветом, то сумма . Если у нас граф окрашен р цветом, то при введении обозначений все условия должны выполняться. Если две вершины x_l и х_s на ребре U_j окрашены в один цвет, то мы бы имели значение . Подставим это в (4)

мы окрасили неправильно.

5. Задача состоит в том, чтобы найти наименьшее число р, для которого система (1), (3), (4) имеет целочисленное решение. Полученное число р будет хроматическим числом графа. В этом случае система целых чисел , удовлетворяющих условиям (3), (4), отвечает конкретному варианту раскраски вершин графа, и при минимальном р отвечает раскраске вершины с минимальным числом красок.

3. Для графов G₁(X) и G₂(X) с одним и тем же множеством вершин имеем

3. Если G₁(Х₁) и G₂(Х₂) – два графа с хроматическими числами р₁ и р₂ и , то граф является р-хроматическим .

Гамильтоновы пути, контуры и задача Коммивояжера

Гамильтонов путь в графе – это путь, проходящий через каждую его вершину один и только один раз.

Гамильтонов контур – это контур, проходящий через каждую вершину (за исключением начальной или конечной), которая совпадает один и только один раз.

Рассмотрим две задачи:

1. Дан орграф G. Требуется найти Гамильтонов контур, если он существует.

2. Дан полный орграф G, дугами которого приписаны произвольные веса C = {C_ij}. Найти такой Гамильтонов контур, который имеет наименьший общий вес.

Эту задачу называют задачей Коммивояжера.

Замечание:

Если заданный орграф G неполный, то его можно рассматривать как полный орграф, приписывая отсутствующим дугам бесконечно большой вес.

Необходимо сделать n деталей, используя один и тот же станок. При переходе от производства детали i к детали j необходимо на перенаватку станка затратить время {C_ij}. В частном случае С = 0.

Ставится задача нахождений такой последовательной обработки деталей, которая не требует перенаватки станка.

Для решения этой задачи строят граф G, вершины которого являются деталями, а существование дуги (i, j) означает, что при переходе от детали i к детали j не требуется перенаватки станка.

Решение задачи существует тогда, когда построенный граф будет иметь Гамильтонов контур.

Если предыдущая задача не имеет решения, то решаем задачу определения такой последовательности обработки детали, при которой минимальные затраты на перенаватку???????????????????????????????????????????????????????????????????

Транспортные задачи связаны с объездом рядов пунктов и возвращением в исходный.

Задачи соединения отдельных пунктов электро-газоснабжения.

В настоящее время нет простых критериев или алгебраических методов, позволяющих выяснить: существует или нет в произвольном графе G Гамильтонов контур.

Существующие алгебраические методы определения Гамильтоновых контуров из-за большого времени работы и объёма памяти не могут быть применимы к задачам с более чем 20 вершинами.