Математическая индукция

Математическая индукция — в математике — один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.

Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино.

28. Понятие графа. Способы задания графов.

Граф G — это упорядоченная пара G: = (V, E), для которой выполнены следующие условия:

· V это непустое множество вершин или узлов,

· E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = { v, v }.

Вершина называется изолированной, если она не является концом ни для одного ребра;

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

. Дуги могут пересекаться, но точки пересечения не являются вершинами графа.

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

29. Изоморфные графы.

Изоморфные графы – графы, которые отличаются только нумерацией вершин.

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

1. количество вершин;

2. количество ребер;

3. степени вершин

4. степени полузахода и полуисхода вершин

5. количество циклов;

6. связность;

7. эйлеровость;

8. гамильтоновость;

9. двудольность.

Если какие-то характеристики не совпадают, то графы не являются изоморфными

30. Двудольный граф. Гамильтонов граф

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

Гамильтонов граф – граф, в котором можно выделить гамильтонов цикл.

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

Эйлеров граф – граф, в котором можно выделить эйлеров цикл.

Теоре́ ма Э́ йлера в теории чисел гласит:

Если a и m взаимно просты, то , где φ (m) — функция Эйлера.

32.Путь, простой путь, цикл графа. Маршрут в графе. Контур.

Маршрут – такая последовательность ребер графа, в которой два соседних ребра имеют общую вершину.

Начало маршрута – вершина, инцидентная первому ребру маршрута

Конец маршрута – вершина, инцидентная последнему ребру маршрута

Циклический маршрут – маршрут, начало и конец которого совпадают.

34. Мультиграфы, гиперграф, псевдограф.

мультиграф есть граф с кратными ребрами.

Гипергра́ ф — обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин.

Псевдограф
пара, где v - непустое множество вершин, а E - некоторое семейство неупорядоченных вершин (ребер), не обязательно различных. Другими словами, от графа псевдограф отличается тем, что в нем, как и в мультиграфе, допускаются кратные ребра и, кроме того, допускаются петли, причем возможно даже несколько петель при одной вершине.