Операции над графами

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

· Операция дополнения — Понятие полного графа позволяет ввести теоретико-множественную операцию дополнения произвольного графа до полного:

· Операция удаления ребра. Свойство: коммутативность.

· Операция добавления ребра. Операция, обратная к предыдущей.

· Операция удаления вершины. — При этом удаляются и все ребра, инцидентные вершине.

· Операция добавления вершины. Операция, обратная к предыдущей.

· Операция введения вершины в ребро.

· Операция стягивания ребра. – Гомеоморфизм графов. Граф Петерсена и К₅.

· Операция отождествления (слияния) вершин. — Добавляем ребро и по нему стягиваем вершины.

· Операция объединения графов.

Операция объединения графов называется дизъюнктивной, если множества вершин и множества рёбер объединяемых графов не пересекаются.

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

· Прямое произведение графов

Лекция 12

Обходы графов

Обходы графов.

Понятие смежности вершин приводит к понятию пути в графе.

Путём (маршрутом) в графе называется чередующаяся последовательность вершин и ребер, в которой соседние элементы инцидентны: v₀,e₁(v₀,v₁),v₁,…v_m.

Примечание. Это определение общее для всех видов графов: псевдо-, мульти-, орграфов. Для обычных графов достаточно указать последовательности либо вершин, либо ребер.

· Если начальная и конечная вершины совпадают, то путь замкнут, иначе открыт.

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

· Если все вершины (а, следовательно, и ребра) маршрута различны, то это – простая цепь.

· Цепь имеет начало и конец.

· Говорят, что цепь с началом u и концом v соединяет вершины u и v: <u, v>.

· Замкнутая цепь называется циклом. Простую цепь иногда называют контуром.

Критерий двудольности графа: граф двудолен, если все его простые циклы состоят из чётного числа рёбер.