Пример 2.1

W

W

С: v_i ⦁ ⦁ ⦁ v_j

C’

Удалим из С все вершины и ребра цепи C’, кроме вершины w. Получим новую цепь С₁, соединяющую вершины v_i и v_j, в которой число повторений вершины w будет по крайней мере на единицу меньше, чем в цепи С.

С₁ : v_i ⦁ ⦁ ⦁ v_j

Если полученная цепь С₁ простая, то все доказано. Если же С₁ не является простой, то поступим с ней так же, как и с цепью С. В силу конечности множества вершин и ребер графа получим простую цепь, соединяющую вершины v_i и v_j.

Следствие 1.1. Если вершина неориентированного графа содержится в некоторой замкнутой цепи, то она содержится и в некотором цикле. Если вершина орграфа содержится в некотором замкнутом пути, то она содержится и в некотором контуре.

Замечание 1.1. Следствие 1.1. перестает быть верным для произвольной цепи с совпадающими концами. Например, для неориентированного графа, состоящего из двух вершин v₁ и v₂ и единственного ребра { v₁, v₂ }, их соединяющего цепь v₁, v₂, v₁ с совпадающими концами не содержит цикла.

Определение 1.3. Неориентированный граф G’ = (V’,U’) называют ассоциированным с орграфом G = (V,U), если V’ = V, а { v_i, v_j } ∊ U’ тогда и только тогда, когда ( v_i, v_j ) ∊ U или ( v_j,v_i )∊ U.

Таким образом, в силу определения 1.3, переход от орграфа к ассоциированному с ним графу состоит в «стирании» направлений дуг орграфа, отбрасывании всех петель орграфа (если они есть) и в замене появившихся кратных (параллельных) ребер { v_i, v_j } и { v_j,v_i } одним ребром { v_i, v_j } (если кратные ребра появились).

2. Методы задания графов.

1. Граф (орграф) G = (V,U) может быть задан по определению перечислением элементов множеств V и U. Например,

G = (V,U) = ({v₁, v₂, v₃, v₄, v₅, v₆}, {(v₁, v₂), (v₁, v₃), (v₂, v₁), (v₂, v₃), (v₂, v₄), (v₃, v₁), (v₃, v₄), (v₅, v₆), (v₆, v₄)}).

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

2. Граф (орграф) G = (V,U) может быть задан геометрически. Условимся вершины графа изображать на плоскости или в пространстве точками, а ребра или дуги – отрезками или дугами, соединяющими соответствующие вершины (для неориентированных графов) или направленными отрезками или направленными дугами, идущими из начальной вершины дуги в конечную вершину (для орграфов).

Пример 2.2. Для орграфа предыдущего примера:

v₂ v₅

G:

v₁ v₃ v₄ v₆

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

3. Граф (орграф) G = (V,U) может быть задан матрицей инцидентности. Пусть | V | = m и | U | = n, и пусть все ребра (дуги) графа занумерованы. Тогда граф (неориентированный или ориентированный) может быть задан прямоугольной матрицей размерности m x n. Для ориентированного графа элементы матрицы задаются так:

Пример 2.3. Построим матрицу инцидентности для орграфа предыдущего примера. Для этого занумеруем дуги орграфа, например, следующим образом

(v₁, v₂), (v₁, v₃), (v₂, v₁), (v₂, v₃), (v₂, v₄), (v₃, v₁), (v₃, v₄), (v₅, v₆), (v₆, v₄)

Дата добавления: 2014-12-16