 Булевы матрицы и операции над ними.

Матрицу, состоящую из нулей и едениц, будем называть булевой матрицей.

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

 Изоморфизм графов.

Пусть G₁ и G₂ - граф без петель и кратких ребер.

Графы G₁=<M₁, R₁> и G₂=<M₂, R₂> называются изоморфными, если существует взаимно однозначное отображение : M₁M₂ сохраняющее смежность, то есть ребро (m', m")M₁ тогда и только тогда, когда ребро ((m'), (m"))M₂.

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

Введем понятие степени вершины графа (орграфа).

Степенью вершины m неориентированного графа называется число (m) ребер графа, инцидентных данной вершине m.

Изолированная вершина имеет степень 0, висячая - 1, петель в неориентированного графа увелиивает степень соответствующей вершины на 2.

Полу степенно исхода (захода) вершины m орграфы А называется число ⁺(m) (^-(m)) дуг орграфа, исходящих из вершины m (заходящих в вершину m).

Петля на вершине орграфа увеличивает ⁺(m) и ^-(m) на 1.

Свойства изоморфизма:

1) если графы G₁ и G₂ изоморфы; и : M₁M₂ - биективное отображение, сохраняющее смежность, то

- количество вершин и количество ребер в G₁ и G₂ одинаковы;

-  mM₁ (m)=((m)), то есть изоморфизм сохраняет степень вершины.

2) Если орграфы D₁ и D₂ изоморфы и : M₁M₂ - биективное отображениt, сохраняющее смежность, то  mM₁ ⁺(m)=⁺((m)), ^–(m)=^–((m)).

количество вершин и количество дуг измороф графов равны.

П ример

M ₁={1,2,3,4,5}

R₁={(1,2),(2,1),(2,5),(5,2),(2,4),(4,2),(2,3),(3,2),(3,4),(4,3)}

Хотим построить изоморф ему.

При сравнении двух графов и проверки того, являются ли они изоморфными

1) Сравниваем количество вершин и ребер - если не равны, то граф точно не изоморфа.

2) Подсчитываем количество вершин с одинаковой степенью

в первом графе:

во втором графе:

если k₀t₀, k₁=t₁, …, k_m=t_m, то граф не изоморф.

Но можно привести пример графов, у которых все эти условия выполняются, но тем не менее эти графы не изоморфы, то есть таких биективное отображение , которое бы сохраняло смежность:

 Метод поиска в глубину.

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

Метод основан на:

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

2) Как выходит из тупика (возвращается по исследованному пути и делает другой выбор на самом близком так, если это возможно)

на неориентированном графе поиск в глубину осуществляется так: Когда посещаем вершину xX, то далее идем по одному из ребер (x, y), инцидентному вершине y. Если вершина y уже пройдена (посещалось ранее), то возвращаемся в x и выбираем другое ребро. Если вершина y не пройдена, то заходим в нее и применяем процесс прохождения рекурсивно уже с вершиной y. Если все ребра инцидентные вершине x, просмотрены, то идем назад по ребру (s, x), по которому пришли в x и ????????????????? вершине s.

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

Задать граф - значит описать множество его вершин и ребер.

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

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

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

a_{i j}

b_{i j}

b_{i j}

1, если существует ребро (x_i, x_j)

0, если вершины x_i, x_j не связаны ребром (x_i, x_j)

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

1, если вершина x_i инцидентна ребру u_j.

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

- матрица инцидентности для ориентироанного графа:

+1, если ребро u_j выходит из вершины x_i

-1, если ребро u_j входит в вершину x_i

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

- матрица весов графа (граф называется взвешенным, если каждому его ребру сопоставляется число) - это матрица W=[w_{i j}], где w_{i j} - вес ребра, соединяющего вершины i, j=1,2,…,n. Веса несуществующих ребер полагают равными 0 или  в зависимости от приложений.

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

- структура смежности графа: для каждой вершины графа составляются списки вершин, смежных с ней.