4. Цери, циклы, связный граф, компоненты связности. Определения, свойства(утверждения, теоремы).
Опр.: Последовательность вершин x1,x2,...xp+1 в которой любые две соседние вершины смежны наз. маршрутом в G.
Опр.: Последовательность ребер e1,e2,...ep в кот. любые два смежных ребра смежны наз. маршрутом в G.
Опр.: Маршрут в котором нет опадающих ребер наз. цепью.
Опр.: Цепь в которой все вершины различны наз. простой цепью.
Опр.: Цепь в которой конечные вершины совпадают наз. циклом.
Опр.: Простая цепь в которой конечные вершины совпадают наз. простым циклом.
Опр.: Кол-во ребер в цепи или цикле наз. длиной цепи(цикла). Обозн. l.
Утверждения: 1)Любая цепь содержит простую цепь; 2)Любой цикл содержит простой цикл; 3)Объединение двух различных (u,v)-цепей содержит простой цикл; 4)Объединение простых циклов C и D имеющих общее ребро e содержит простой цикл; 5)Для любого G=(X,E) (связный) и произвольного e"принадлежит или содержится"E имееет место: I)если e принадлежит некоторому циклу графа G, то граф G-e связный граф. II)если ребро e не принадлежит никакому циклю графа G, то граф G-e не связан и имеет ровно 2 компоненты связности.
Опр.: Граф G наз. связным если для любых его двух вершинсуществует цепь их соединяющая.
Опр.: Подграф графа G связный и максимальный по включению(который не содержиться в другом связном подраффе графа G с большим числом элементов) наз. компонентой связности графа G. Колво компонент связности обозн. K,
Утверждение: Для любого G либо он сам либо его дополнение яв-ся связным графом.
Если G-связный, то его дополнение связно и наоборот. Если G-несвязный, то и его дополнение не связно.
Теор.: Для любого G верно неравенство: n-k<=m<=C(сочетания из 2-х по n-k+1)

---

4 Цепи циклы, связный граф , компоненты связности .Определения свойства (утверждения, теоремы)



Цепь в графе — маршрут, все рёбра которого различны. Если все вершины
(а тем самым и рёбра) различны, то такая цепь называется простой
(элементарной). В цепи v0,e1,...,ek,vk вершины v0 и vk называются
концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь,
соединяющая вершины u и v обозначается  . Для орграфов цепь называется
орцепью.



Цикл — замкнутая цепь. Для орграфов цикл называется контуром. Цикл
(простой цикл) в орграфе — это простой путь длины не менее 1, который
начинается и заканчивается в одной и той же вершине.Цикл Гамильтона —
то же, что и Гамильтонов цикл.( простой цикл в графе, содержащий все
вершины графа ровно по одному разу.)



Связный граф — граф, в котором все вершины связаны.

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

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

Примеры применения

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

Связность для орграфов

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

Некоторые критерии связности

Здесь приведены некоторые критериальные(эквивалентные) определения связного графа:

Граф называется односвязным (связным), если:

1 У него одна компонента связности

2 Существует путь из любой вершины в любую

3 Существует путь из заданной вершины в любую

4 Содержит связный подграф, включающий все вершины исходного графа

5 Содержит в качестве подграфа дерево,включающее все вершины исходного графа(оно называется остовным)

6 При произвольном делении его вершин на 2 группы всегда существет хотя бы 1 ребро, соединяющее пару вершин из разных групп