Маршруты, цепи, циклы

Основные понятия теории графов

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

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

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

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

Ографом или ориентированным графом называется пара множеств: V – конечное множество вершин и - множество упорядоченных пар элементов из V, т.е. граф, на рёбрах которого указывается направление.

Две вершины графа называются смежными, если существует ребро их соединяющее. При этом вершины u и v называются инцидентными этому ребру, а ребро называется инцидентным этим вершинам.

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

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

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

Граф, имеющий ориентированные и неориентированные ребра, называется смешанным.

Степенью вершины v графа G называется число ребер , инцидентных данной вершине. Если - число чётное, то v – четная вершина. В противном случае – нечетная вершина. Петля учитывается 2 раза.

Лемма (о рукопожатиях). Если m – общее число ребер графа , то

.

Два графа и называются изоморфными, если:

1) существует биекция такая, что число ребер , инцидентное вершинам графа G равно числу ребер , инцидентных вершинам графа , где или

2) существуют две согласованные между собой биекции: (c учетом кратности ребер) такие, что: а

Теорема. Число нечетных вершин любого графа – четное.

Геометрической фигурой называется пара множеств где – некоторое множество точек в пространстве а Y – совокупность некоторых кривых линий, каждая из которых соединяет некоторые пары точек из множества В. Эти кривые соединяют пару точек , причем возможно вырождение этих кривых:

Пусть эти кривые являются жордановыми, т.е. не имеют точек самопересечения, а друг с другом пересекаются только в точках множества В.

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

Если такая геометрическая фигура в пространстве существует, то говорят, что может быть уложен в пространстве .

Конечным графом называется граф с конечным числом ребер.

Теорема. Каждый конечный граф может быть уложен в пространстве .

Плоским называется граф, изображенный на плоскости так, что никакие его 2 ребра не пересекаются геометрически нигде кроме инцидентной им вершины.

Граф, изоморфный плоскому графу, называется планарным.

Граф с n вершинами, у которого отсутствуют ребра, называется пустым или вполне несвязным графом.

Простой граф с n вершинами называется полным, если любые две его вершины являются смежными (соединены ребром).

Объединением двух графов и , где называется граф G, который обозначается где

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

Маршруты, цепи, циклы

Маршрутом в графе называется конечная последовательность ребер вида: Этот маршрут обозначают:

Петля называется тривиальным маршрутом.

Длиной маршрута называется число ребер в нем.

Маршрут называется цепью, если все его ребра различны.

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

Если то цепь называется замкнутой.

Замкнутая простая цепь, содержащая хотя бы одно ребро, называется циклом.

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

Второе определение связного графа. Граф называется связным, если любые две его вершины являются связанными.

Теорема. Первое и второе определения связности равносильны.

Связанность вершин является отношением эквивалентности на множестве вершин графа.

Свойства отношения эквивалентности:

1) рефлексивность ;

2) симметричность (если то );

3) транзитивность (если и то )

Отношение эквивалентности задает разбиение графа на компоненты связности.

Теорема. Каждый граф единственным образом представляется в виде объединения непересекающихся связных подграфов (компонент связности).

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

Если при удалении какого-то ребра в графе, число компонент связности увеличилось на единицу, то это ребро называется мостом или перешейком.