1,2) Доказательства

Прямое – предположим, что данное утверждение верно, тогда…

Косвенное – предположим, что данное утверждение неверно, тогда…

Прямое – левая часть равна правой, значит, наше предположение верно. Чтд.

Косвенное – получили противоречие, т.к. левая часть равна правой, значит, наше предположение не верно. Чтд.

3) Рекурентные соотношения

4) Теория по графам

5) Задачи

	+(нет общ)	+(x общ)
n(верш)	n1+n2	n1+n2-x	n1+n2	n1+n2-x
m(ребр)	m1+m2+ n1*n2	m1+m2+ (n1-x)*(n2-x)	m1+m2	m1+m2-(x-1)
k	Компонент свзяности
d	Диаметр
h	Хроматического число (цвета)
V	Цикломатич. число (ацикличивание) V=m-n+k
dd

6) КСС

1. Находим все истоки и стоки

КСС1={1} – сток\исток

…

2. Находим в циклы Ц1={1,2}

   1. По возможности объединяем их. КСС1={Ц1,Ц2 }

3. Проверка: все КСС включают в себя все вершины ровно по одному разу.

4. Оставшиеся вершины, если есть: КСС1={1}

7) Эйлер и Гамельтон

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

Что бы сделать граф эйлеровым нужно приблизительно удалить

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

Гамильтоновы графы: полный, с гамильтоновым циклом + другие ребра

Не гамильтоновы графы: имеющую узловую вершину, висячая вершина

Если v=m-n+k=0 граф – дерево – не эйл/не гам

8) Реберность

Граф реберный, когда он разложим по операции объединения на полные подграфы так, чтобы каждая вершина входила в них не более двух раз (при этом каждое ребро было бы задействовано точно один раз).

Методика построения образа графа:

1. Вершины - полные подграфы (K1, K2, ...).

2. Строим по очереди с наибольшего полного подграфа.

3. Ребра соответствуют номерам вершин в данном полном подграфе.

4. Пустые ребра заканчиваем закрашенной вершиной.

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

Внутренняя устойчивость ( – количество пустых подграфов, определяется деревом.

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

Если наибольшая из степеней вершин графа G равна , то h, кроме двух случаев:

1) граф содержит полный подграф на + 1 вершине,

2) = 2 и при этом данный граф содержит контур нечетной длины.

h=2, когда все имеющиеся в графе циклы содержат четное число ребер.

h=2 у двудольных графов:

• ациклические графы, содержащие хотя бы одно ребро,

• простые циклы на четном числе вершин,

• двудольные графы,

• графы, содержащие только четные циклы.

В остальных случаях находятся пустые подграфы (дерево), матрица покрытий и логическое выражение:

Пустой подграф	1	2	3	Цвет
{1;3}	1		1	а
{1;2}	1	1		b

(a+b)*(b)*(a)