Хроматическое число

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

Хроматическое число – минимальное число красок, которыми можно раскрасить все вершины графа т.о., чтобы никакие две смежные вершины не были покрашены одинаково.

Хроматическим классом графа G наз. натуральное число q(G), обладающее свойствами:

1. каждое ребро графа G можно раскрасить одним из q цветов так, чтобы никакие два ребра не были окрашены в один цвет.

2. это нельзя сделать с q-1 краской.

Хроматический класс совпадает с хроматическим числом смежностного графа.

Теорема Кенинга: Граф является бихроматическим (двудольным, p≤2), если он не содержит циклов нечетной длины.

Док-во:

а) Необходимость

Если граф бихроматический, то он не содержит циклов нечетной длины.

б) Достаточность

Рассмотрим граф G без циклов нечетной длины и покажем, что его можно покрасить двумя цветами. Предположим, что граф G – связный (в противном случае будем рассматривать каждую компоненту связности отдельно). Будем последовательно окрашивать вершины графа по след. правилу:

1. Произвольную вершину a окрашиваем синим цветом.

2. Все вершины, смежные с синими вершинами окрашиваем в красный цвет. Если вершина окрашена в красный цвет, то все смежные ей окрашиваем синим цветом.

3. Т.к. граф связен, то все вершины будут окрашены и ни одна из них не может быть одновременно окрашена двумя цветами сразу, т.к. она входила бы в цикл нечетной длины.

Число внутренней устойчивости

Число внешней устойчивости

10. Понятие внутренней устойчивости.

Множество Ψ наз. внутренне устойчивым, если оно образовано из вершин графа G=(X, Γ), и никакие две вершины в нем не смежны. Т.е.

Если граф задан в виде G=(X, U, F)., то говорят, что множество Ψ внутренне устойчиво, если:

Каждое внутреннее устойчивое множество порождает в графе голый подграф. Каждое внутренне устойчивое множество в графе G, в графе G порождает полный подграф. Максимальный полный подграф наз. кликой.

Определим число внутренней устойчивости. Пусть - семейство всех внутренне устойчивых множеств. Тогда - число внутренней устойчивости.

Т.е. число внутренней устойчивости – это количество элементов в наибольшем по числу элементов внутренне устойчивом множестве. Для того, чтобы найти число внутренней устойчивости необходимо построить семейство всех максимальных внутренне устойчивых множеств.

Метод Магу для выделения максимально внутренне устойчивых множеств.

Если граф зада в виде G=(X, Γ), то множество Ψ внутренне устойчиво, если

Введем ряд булевых переменных: С вершиной свяжем булеву переменную , и положим, что если , то . Если , то

Введем переменную:

Перейдем к булевым переменным:

Тогда для каждого члена совокупность всех вершин, соответствующая переменным, которая в нем отсутствует, дает максимальное внутренне устойчивое множество.

11. Понятие внешней устойчивости.

Пусть задан граф G=(X, Γ). Говорят, что множество внешне устойчиво, если ,

Т.е. множество Т вершин графа наз. внешне устойчивым, если все остальные вершины графа, не входящие в это множество отображены в вершины множества Т.