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

Такие, для к-рых существует эйлеров путь (замкнутый путь, содержащий все рёбра графа). Напомню: путь — последовательность, в которой все рёбра разные (необязательно вершины).

Критерий — чётная валентность вершин.

Прямое: добавление вершины v’ к вершине v осуществимо двумя (2n) рёбрами, для того, чтобы не нарушать чётную валентность вершины v. Эйлеров путь просто будет заходить через v по одному ребру и возвращаться в v по другому.

Обратное: в вершину нужно войти и выйти.

Гамил. Графы. Такие, для к-рых существует гамильтонов (включающий все вершины) цикл.

Достаточное условие: для Г с n>3 vi € V: Сигма(валентность)(vi)>= n/2, где n=|V|.

Изоморфизм. Нужно задать взаимно-однозначное соответствие му рёбрами и вершинами графов.

Графы изоморфны, если -~ указать пси и тетта ((~)), чтобы

пси: E1->E2;

тетта: V1->V2;

Для всех e € E1: дельта1(e)={w,v}(w,v € V1) => дельта2(пси(e)) = {тетта(w),тетта(v)}.

Изоморфные графы имеют одинаковое количество рёбер и вершин одинаковой валентности; если Г1 — простой, Г2 — тоже.

Связность. Граф — связный, если для любых двух его вершин существует путь, их соединяющий.

Компонента связности — максимально связный подграф. Число компонент связности — инвариант, не изменяется при изоморфизме.

______

/_____/

//____//

/_____/

5 Красок

Раскраска графа — такое присваивание цветов (натуральных чисел) его вершинам, что никакие 2 смежные вершины не получают одинаковый цвет.

Хроматическое число Х(хи)(G) — наименьшее возможное число цветов в раскраске вершин графа.

Очевидно, что существует m-раскраска графа G, исли X(G) <= m <= |V|.

Одноцветные — мн-во вершин, покрашенных в один и тот же цвет.

Никакие две одноцветные вершины не смежны.

1) Х(полный граф) = n;

2) X(K_(m,n)) = 2;

3) X(T) = 2;

4) X(G) <= 1 + Сигма’, где Сигма’ = max(v € V)(Сигма(v)).

--------

Всякий планарный граф -~ раскрасить 5-ю красакми.

-P:

Достаточно рассматривать связные графы, т.к.

X(U(i=1..n)(Gi)) = max(i=1..n)(X(Gi)).

Индукция по р. База: если p <= 5, то X <= p <= 5. Пусть теорема верна для всех связных планарных графов с p вершинами. Рассмотрим граф G с p+1 вершиной. По следствию к формуле Эйлера существует v € V Сигма(v) <= 5. По индукционному предположению Х(G - v) <= 5. Нужно раскрасить вершину v.

1. Если Сигма(v) < 5, то в 5-раскраске G - v существует цвет, свободный для v.

2. Если Сигма(v) = 5 и для Г'(v) использованы не все пять цветов, то в 5-раскраске G — v существует цвет, свободный для v.

3. Остался случай, когда Сигма(v) = 5 и все пять цветов использованы (вершина vi покрашена в цвет i. Пусть G1,3 — правильный подграф G - v, порожденный всеми вершинами, покрашенными в цвета 1 или 3 в 5-раскраске графа G — v. Если v1 и vз принадлежат разным компонентам связности графа G1,3, то в той компоненте, в которой находится vi, произведем перекраску 1 <-> 3. При этом получится 5-раскраска G - v, но цвет 1 будет свободен для v. В противном случае существует простая цепь, соединяющая v1 и v3 и состоящая из вершин, покрашенных в цвета 1 и 3. В этом случае v2 и v4 принадлежат разным компонентам связности подграфа G2,4 (так как граф G — планарный). Перекрасим вершины 2 <-> 4 в той компоненте связности графа G2,4, которой принадлежит v2, и получим 5-раскраску графа G—v, в которой цвет 2 свободен для V.

Двудольные и паросочетания

Паросочетание или независимое мн-во рёбер — произвольное подмн-во попарно несмежных рёбер графа, взятых со своими вершинами.

Окружение подмн-ва V’ в графе Г — объединению окружений вершин мн-ва V’ за вычетом самих вершин из V’

( Г_G(V’) = U(V € V’)(Г(V)) \ V’ ).

Г(V) — мн-во вершин, соседних с V без самой вершины V.

Для существования в двудольном графе G = G(V U W, E) паросочетания, покрывающего долю вершин V необходимо и достаточно, чтобы для любого подмн-ва V’ € V было верно: |V’| <= |Г_G(V’)|.