Операции над графами, подграфы.

Объединением графов G₁(V₁, E₁) и G₂(V₂, E₂) называется граф G(V, E) = , где V = , E = . Пересечением графов G₁(V₁, E₁) и G₂(V₂, E₂) называется граф G(V, E) = , где V = E = Дополнением графа G₁(V₁, E₁) называется граф G(V, E) = , где , E = Кольцевой суммой графов G₁(V₁, E₁) и G₂(V₂, E₂) называется граф G(V, E) = , где V = , E = . Подграфом графа G(V, E) называется граф G ¢ (V ¢, E ¢ ), где . Подграф называется остовным подграфом графа G(V, E), если . Подграф называется собственным подграфом граф G, если .

34.Связанность, компоненты связанности, матрица связанности, выделение компонентов связанности. Две вершины называются связными, если существует маршрут между ними. Связность для вершин является бинарным отношением. Неориентированный граф называется связным, если между любыми двумя вершинами есть маршрут. Любой граф G можно разбить на непересекающиеся подмножества вершин по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств – несвязны. Тогда все выделенные таким образом подграфы называют компонентами связности графа G. При этом связный граф имеет одну компоненту связности. Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[s_ij] порядка n, элементы которой равны

Матрица связности графа G − квадратная матрица S(G)=[s_ij] порядка n, элементы которой равны

Поиск маршрутов в графах.

Алгоритм (Тэрри ) поиска пути в связном графе, из вершины v i в вершину v j, где v i v j.

Исходя из вершины v i осуществлять последовательный переход от каждой достигнутой вершины к смежной ей вершине, по следующим правилам:

1. идя по произвольной дуге, всякий раз отмечать направление, в котором оно было пройдено;

2. исходя из некоторой вершины vk, всегда следовать только по дуге, которое не было пройдено или было пройдено в противоположном направлении;

3. для всякой вершины vk, отличной от v i, отмечать первую заходящую в vk дугу, если вершина vk встречается в первый раз;

4. исходя из некоторой вершины, vk, отличной от вершины v i, по первой заходящей в vk дуге идти лишь тогда, когда нет других возможностей.

Путь в орграфе из вершины v i в вершину v j, где v i ` v j , называется минимальным , если он имеет минимальную длину среди всех путей орграфа из v i в v j.

Деревья, свойства деревьев. Лес.

Граф называется деревом, если он является связным и не имеет циклов. Любые две различные вершины дерева можно соединить единственной (и притом простой) цепью. Число дуг дерева на единицу меньше числа его вершин. Пусть G – дерево. Тогда любая цепь в G является простой. Если какую-нибудь пару несмежных вершин дерева соединить дугой, то полученный граф будет содержать ровно одну цепь. Граф, все компоненты связности которого являются деревьями, называется лесом .

37.Остовное дерево, минимальное остовное дерево. Остовным деревом (остовом или каркасом) связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Замечание. Остовное дерево графа не единственно. Число дуг произвольного неорграфа G, которое надо удалить для получения остова, не зависит от последовательности их удаления и равно m – n + k, где m – число дуг, n – число вершин, k – число компонент связности графа G. Минимальное остовное дерево (или минимальное покрывающее дерево ) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

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

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

39. Гамильтоновы графы и циклы.

Маршрутом (или путем ) в графе G называется чередующаяся последовательность вершин и ребер v₀, e₁, v₁, …, v_t_{− 1}, e_t, v_t₊₁, в которой e_i = v_i_{− 1}v_i (1 ≤ i ≤ t). Такой маршрут кратко называют ( v ₀, v_t )-маршрутом и говорят, что он соединяет v₀ c v_t; в свою очередь вершины v₀, v_t — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v₀, v₁, …, v_t своих вершин. Если v₀=v_t, то (v₀, v_t)-маршрут называется замкнутым. Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, быть может, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром ). Гамильтоновой цепью графа называется его простая цепь, которая проходит через каждую вершину графа точно один раз. Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом. Граф называется гамильтоновым, если он обладает гамильтоновым циклом. Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (Hamilton W.), который в 1859 году предложил следующую игру-головоломку: требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вернуться в начальную вершину.

Планарные графы.

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

1 234