 Способы задания графов.

1) графическое изображение.

2) матричное представление

1. Матрица смежности вершин ориентированного помеченного графа с n вершинами - это матрица A=[a_{i j}], i, j=1,2,…,n, в которой

a_{i j}

b_{i j}

c_{i j}

c_{i j}

1, если существует ребра (m_i, m_j)

0, если вершины не связаны ребром (m_i, m_j).

2. Матрица смежности ребер

графы с m ребрами - это матрица B=[b_{i j}].

1, если ребра r_i и r_j смежны, то есть имеют общую вершину

0, если ребра r_i и r_j не смежны.

3. Матрица инцидентности для неориентированного графа с n вершинами и m ребрами - это матрица C=[c_{i j}], i=1,2,…,n, j=1,…,m строки в которой соответствуют вершинам, а столбцы - ребрам.

1, если вершина m_i инцидентна ребру r_i

0, в противном случае

Д ля ориентированного графа:

+1, если дуга r_j выходит из вершины m_i

-1, если дуга r_j входит в вершину m_i

0, если вершина не инцидентна ребру r_j.

4. Список ребер графа: каждое ребро представляется парой инцидентных ему вершин; задаются 2 массива r={r₁,…,r_m} и t={t₁,t₂,…,t_m), где m - количество ребер в графе. Каждый элемент в массиве есть метка вершины, а i-е ребро графа выходит из вершины r_i и входит в вершину t_i.

5. Структура смежности графа. Матрица смежности вершин ребер.

Остановимся на способах задания графов.

Матрица инцидентности для неориентированного графа

C={c_i j} - это матрица строки которой соответствуют вершина графа, n столбца - ребром.

c_{i j}

1, если вершина m_i инцидентна ребру r_j

0, если вершина m_i и ребро r_j инцидентны.

4. Матрица весов графа.

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

Взвешенный граф, не имеющий петель и кратных ребер, может быть представлен матрицей весов W=[w_{i j}] – где w_{i j} – вес ребра, соединяющего вершины i и j.

Веса несуществующих ребер полагают равными 0 или .

Матрица весов - это матрица смежности, только вместо 1 стоят веса.

5. Список ребер графа.

При таком способе каждое ребро представляется парой инцидентной ему вершин. Это представление реализуется двумя массивами p=(p₁,p₂,…,p_n) и t=(t₁,t₂,…,t_n), где n - количество ребер в графе.

Каждый элемент в массиве - это метка вершины, а i-е ребро графа выходит из вершины p_i и входит в вершину t_i.

p=(2 2 2 3 3 4 4 5)

t =(3 1 5 3 4 2 5 4)

6. Структура смежности графа.

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

Структура смежности состоит из списков a[x] вершин графа, смежных с вершиной x, при чем вершина x является началом ребра.

Такой способ хранения желателен в алгоритмах в основе которых лежат операции добавление и удаление вершин из списков.

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

1 . Объединение графов G₁=<M₁, R₁> и G₂=<M₂, R₂> - это граф G=G₁G₂=<M, R>, где M=M₁M₂, R=R₁R₂.

2. Пересечение графов G₁=<M₁, R₁> и G₂=<M₂, R₂> - это граф G=<M, R>, где M=M₁M₂, R=R₁R₂.

3. Сумма графов G₁=<M₁, R₁> и G₂=<M₂, R₂> - это объединение графов, у которого R=R₁R₂R₃ , где R₃={(v,w) | vM₁/M₂, wM₁/M₂}

M₁/M₂={m₁, m₂}, M₂/M₁={m₄},

R₃={(m₁, m₄), (m₃, m₄)}

4. Кольцевая сумма графов G₁ и G₂ - это граф G₁=G₁G₂=<M, R> такой, что

G - объединяемая G₁ и G₂, у которого удалены общие ребра то есть E=(E₁E₂)\(E₁E₂), и изолированные вершины (которые могут при этом получатся.

5. Удаление вершины - удаляется требуемая вершина и все ребра, инцидентные ей.

m₂

m₃

m₁

r₁

r₂

r₃

6. Стягиватся по ребру - требуемое ребро удаляется из графа, инцидентные ему вершины склеиваются, объединенной вершине присваивается новое имя.

стягивание

по r₁=(m₁,m₂)

r₂

r₃

m₃

m₁=m₂=m

 Элементы графов.

Введем в рассмотрение объекты, которые можно выделить в графе. Пусть G=<M, R> соединяющим вершины m_o и m_k. Маршрутом в графе, называется чередующаяся последовательность вершин и ребер.

m_o, r₁, m₁, r₂, …, r_k, m_k

в которой любые 2 соседних элемента инцидентны.

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

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

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

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

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

Для орграфов цепь называется путем, а цикл - контуром.

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

П ример. m₁ m₂ m₁ m₅ - маршрут длины 3, соединяющий m₁ и m₅ (но не цепь).

m₁ m₂ m₄ m₂ m₅ - цепь длины - 5, соединяющий m₁ и m₅ (но не простая цепь).

m₁ m₅ m₂ m₄ m₃ - простая цепь

m₁ m₂ m₃ m₄ m₂ m₅ m₁ - цикл (но не простой цикл).

m₁ m₂ m₅ m₁ - прсотой цикл.

Приведем некоторые полезные свойства матриц инцидентности и смежности применительно к этим частям графа.

1) Первое свойство.

По матрице инцидентности можно проверить, образуют ли ребра цикл (или дуги - контур в орграфе),

Пусть D - ограф без петель с непростым множеством дуг.

Тогда для любого контура в D сумма столбцов матрицы инцидентности, соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

Пример. Рассмотрим матрицу инцидентности.

Пусть G - граф без петель с не пустым множеством ребер.

Тогда при покоординатном сложении по модулю 2 для любого цикла в G сумма столбцов матрицы инцидентности соответствующих ребрам, образующим цикл, равна нулевому столбцу.

2) Второе свойство

По матрице смежности можно определить число всех маршрутов длины K из одной вершины в другую.

Обозначим через к-ю степень матрицы смежности (или граф G) G=<M, R>, M={m₁, …, m_n}.

Элемент матрицы A^k графа G равен числу всех маршрутов длины К, соединяющих m_i и m_j.

Найдем число маршрутов длины 1 из 1 в 4: 1,4- один.

Число маршрутов длины 2:

Из 1 в 3 нет маршрутов длин 2.

Из 1 в 1 маршруты длин 2:

 Расстояния в графах.

G=<M, R>.

Определение. Вершины m', m"M называются связанными, если существует маршрут с началом m' и концом m".

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

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

Минимальная длина простой цепи с началом m` и концом m`` называется расстоянием d(m', m") между этими вершинами.

Расстояние d(m', m") удовлетворяет следующим аксиомам:

1) d(m', m")0, причем d(m', m")=0  m'=m"

2) d(m', m")= d(m", m')

3) справедливо неравенство треугольника: d(m', m")+ d(m", m"') d(m', m").

Диаметр, радиус и центр графа.

П усть G - неориентированный связной граф. Тогда можно определить его диаметр d(G)=max d d(m', m").

m', m"G

d(G)=4

Кратчайшие простые цепи, связывающие вершины m', m" с максимальным расстоянием между ними называются диаметральными простыми цепями.

Пусть m - производящая вершина рассматриваемого графа G.

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

r(m)=max r(m') r(1)=4 от 1 до 6

m'G r(2)=4 от 2 до 5

Вершина m называется центром графа G, если максимальное удаление от нее принимает минимальное значение

r(m)=max r(m') r(1)=4 r(5)=4

m'G r(2)=4 r(6)=4

r(3)=4 r(4)=4

r(4)=4

Центр не обязательно должен быть единственным.

М аксимальное удаление (G) от центра называется радиусом графа, а любая кратчайшая цепь от центра m до максимально удаленной от него вершины m' - радиальной цепью.

В неориентированном графе, в котором  две различные вершины m', m" соединены ребром, радиус равен 1 и  вершина является центром.

Вопросы.

1) Обязательно ли диаметральная цепь проходит через центр графа?

2) Обязательно ли диаметральная цепь содержит радиальную цепь целиком?

3) Всегда ли диаметральная цепь является объединением двух радиальных?

3) Третье свойство

По матрице смежности можно проверить наличие контуров в орграфе.

Для того чтобы n- вершиной орграф с матрицей смежности A имел хотя бы один контур, необходимо и достаточно чтобы матрица K=A²+A³+…+Aⁿ имела ненулевые диагональные элементы.