Размещено на http://www.allbest.ru/

6

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию Московский Государственный

Гуманитарно-Экономический Институт

Факультет: Прикладной математики и информатики

Кафедра: Прикладная математика

Курсовая работа по дисциплине

«Дискретная математика»

по теме: «Алгоритм проверки двух графов на изоморфизм»

Выполнила:

Студенка группы ПМ-10

Колесникова А. Н.

Преподаватель

дискретной математики

Труб Н.В.

Москва 2012



Оглавление

Введение

1. Постановка задачи

2. Теоритическая часть

2.1 Основные определения теории графов

2.2 Изоморфизм графов (пример)

2.3 Машинное представление графов

2.3.1 Матрица смежности (пример)

2.3.2 Матрица инцидентности (пример)

2.3.3 Массив ребер (пример)

3. Алгоритм (блок-схема)

4. Пошаговая проверка на изоморфизм двух графов вручную

5. Реализация программы на языке C#

6. Трансляция программы на примере

Заключение

Список используемой литературы



Введение

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



1. Постановка задачи

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

Для достижения поставленных целей в работе сформулированы следующие

задачи:

1) Сформулировать определение изоморфизма графов

2) Доказать на примере изоморфизм двух графов вручную

3) Сформулировать алгоритм проверки

4) Нарисовать блок-схему

5) Написать программу по данной блок-схеме

6) Показать, как работает программа на примере.



2. Теоритическая часть

2.1 Основные определения теории графов

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

Графом называется пара , где V - некоторое множество, которое называют множеством вершин графа, а E - отношение на V () - множество ребер графа. То есть все ребра из множества E соединяют некоторые пары точек из V.

Если отношение E симметричное (т.е. ), то граф называют неориентированным, в противном случае граф называют ориентированным. Фактически для каждого из ребер ориентированного графа указаны начало и конец, то есть пара (u, v) упорядочена, а в неориентированном графе (u, v) = (v, u).

Если в графе существует ребро (u, v), то говорят, что вершина v смежна с вершиной u (в ориентированном графе отношение смежности несимметрично).

Путем из вершины u в вершину v длиной k ребер называют последовательность ребер графа . Часто тот же путь обозначают последовательностью вершин . Если для данных вершин u, v существует путь из u в v, то говорят, что вершина v достижима из u. Путь называется простым, если все вершины в нем различны. Циклом называется путь, в котором начальная вершина совпадает с конечной. При этом циклы, отличающиеся лишь номером начальной точки, отождествляются.

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

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

При программировании вершины графа обычно сопоставляют числам от 1 до N, где - количество вершин графа, и рассматривают . Ребра нумерую числами от 1 до M, где . Для хранения графа в программе можно применить различные методы. Самым простым является хранение матрицы смежности, т.е. двумерного массива, скажем A, где для невзвешенного графа (или 1), если и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти памяти был достаточен для хранения N² значений, даже если ребер в графе существенно меньше, чем N². Это не позволяет построить алгоритм со временем порядка O(N) для графов, имеющих O(N) ребер.

Этого недостатка лишены такие способы хранения графа, как одномерный массив длины N списков или множеств вершин. В таком массиве каждый элемент соответствует одной из вершин и содержит список или множество вершин, смежных ей.

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

Наконец, при решении задач на графах, в том числе и с помощью компьютера, часто используется его графическое представление. Вершины графа изображают на плоскости в виде точек или маленьких кружков, а ребра -- в виде линий (не обязательно прямых), соединяющих соответствующие пары вершин, для неориентированного графа и стрелок - для ориентированного (если ребро направлено из u в v, то из точки, изображающей вершину u, проводят стрелку в вершину v).

Степенью s вершины v графа (V,E) называется число его вершин, смежных с v, или, что то же, число ребер, инцидентных этой вершине.

Ясно, что при всяком изоморфизме графов L и L' соответствующие друг другу вершины должны иметь одинаковую степень.

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

2.2 Изоморфизм графов

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

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

Рассмотрим два графа G=<V,E> и G'=<V'E'>, где V и V'-это количество вершин, а E и E' -количество ребер в графах G и G, и дадим определение изоморфизма.

Граф G изоморфен графу G', если между множеством вершин V и V' можно установить взаимно однозначное соответствие, такое, что две вершины смежны в G' тогда и только тогда, когда соответствующие им вершины в графе G смежны.

Исходя из этого определения, можно сказать, что графы G и G' изоморфны.

Автоморфизмом графа G называется изоморфизм графа G на себя.

Изоморфные графы естественно отождествлять, т.е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игнорируется при введении понятия "граф".

Если графы G и G' изоморфны, то ясно, что в этом случае

|V(G)| = |V(G')| и |E(G)| = |E(G')|.

Мы можем рассматривать Q как операцию, преобразующую граф G в граф G', и в соответствии с этим писать QG=G'.

Всякий граф G имеет тождественный (или тривиальный) автоморфизм I, такой, что Ix = x для каждого ребра x и каждой вершины x из G.

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

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

Для изоморфизма двух n-вершинных графов само определение этого отношения дает теоретически безукоризненный способ проверки: надо просмотреть все n! взаимно однозначных соответствий между множествами вершин и установить, совмещаются ли полностью ребра графа хотя бы при одном соответствии. Однако даже весьма грубая оценка показывает, что такое решение задачи "в лоб" практически непригодно: уже при n=20 перебор всех n! вариантов потребовал бы около 40 лет машинного времени.

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

Вначале естественно поставить вопрос: какие характеристики графов инвариантны относительно изоморфизма?

Примеры таких инвариантов графа G известны: это число вершин n(G), число ребер m(G) и вектор степеней s(G)=(s₁, s₂, ...,s_n), который, в частности, дает числовые инварианты

min s_i и max s_i

i принадлежит {1,2,...,n} i принадлежит {1,2,...,n}

Второй из них часто называется степенью графа.

Определение :

Пусть f - функция, относящая каждому графу G некоторый элемент f(G) из множества M произвольной природы. Эту функцию мы будем называть инвариантом, если на изоморфных графах ее значения совпадают, т.е. Для любых G и G' из изоморфности графов G и G' следует f(G)=f(G').

Введем несколько наиболее важных инвариантов графа:

· плотность f(G) - число вершин клики графа G. Инвариантность этой характеристики следует из того, что при изоморфном соответствии двух графов каждому подмножеству вершин одного графа, порождающему клику, соответствует в другом графе подмножество с тем же числом вершин и тоже порождающее клику;

· неплотность e(G) - это наибольшее количество попарно несмежных вершин графа;

· xроматическое число g(G);

· число компонент связности K(G);

· число Хадвигера h(G).

Заметим, что матрица смежностей не является инвариантом графа: при переходе от одной нумерации его вершин к другой она претерпевает перестановку рядов, состоящую из некоторой перестановки строк и точно такой же перестановки столбцов. Любая функция от элементов a_ij матрицы, не меняющаяся ни при каких перестановках рядов матрицы смежности, является инвариантом графа G. К числу таких функций относятся сумма всех элементов, неупорядоченный набор сумм элементов каждой строки или сумм элементов каждого столбца, определитель матрицы, ее характеристический многочлен и корни последнего и др.

Определение:

Инвариант f называется полным, если для любых графов G и G' из равенства f(G)=f(G') следует изоморфизм графов G и G'.

Из рассмотренных инвариантов, которые отнесены к "легко вычислимым", даже наиболее "богатый" - вектор степеней s(G) - не является полным. В процессе развития теории графов не было нехватки в гипотезах полноты или иного "трудно вычислимого" инварианта, но все эти гипотезы рано или поздно опровергались конкретными примерами.

Определение:

Степенью s вершины v графа (V,E) называется число его вершин, смежных с v, или, что то же, число ребер, инцидентных этой вершине.

Ясно, что при всяком изоморфизме графов G и G' соответствующие друг другу вершины должны иметь одинаковую степень.

Определение:

Пусть G=(V,E) - n-вершинный граф, а s₁, s₂, ...,s_n - степени его вершин, выписанные в порядке неубывания: s₁ <= s₂ <= ... <= s_n.

Упорядоченную систему (s₁, s₂, ...,s_n) будем называть вектором степеней графа G и кратко обозначать s(G).

Вместо самого вектора степеней часто пользуются его обращением t(G)=(t₁, t₂, ...,t_n), где t_i=s_n-i (i=1,2,...,n) - те же степени вершин, но расположенные в порядке невозрастания: t₁ >= t₂ >= ... >= t_n.

Из сказанного выше следует, что для изоморфизма графов G и G' необходимо совпадение векторов их степеней: s(G)=s(G').

Однако достаточным это условие не является: на рисунке 1 мы видим две пары неизоморфных графов с одинаковыми векторами: s = (1,2,2,2,2,3):

Рис.1. Пара неизоморфных графов

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

Во-первых, если s(G) не равно s(G'), то отсюда сразу следует неизоморфность графов G и G'.

Во-вторых, если s(G)=s(G'), то для проверки графов G и G' на изоморфизм требуется перебор не всех n! соответствий между вершинами, а лишь тех, при которых сопоставляются вершины одинаковой степени.

2.3 Машинное представление графов

Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным. Рассмотрим три способа проверки изоморфизма двух графов:

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

2. Матрица инцидентности

3. Массив ребер

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

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

Сначала дадим определение смежности.

Если ребро соединяет две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины. Если степень вершины равна 0, то получается изолированная графа. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом.

Пусть v₁, v₂ -- вершины, е = (v₁, v₂) -- соединяющее их ребро. Множество вершин, смежных с вершиной v, называется множеством смежности вершины v.

Матрица смежности - это матрица размером nЧn, где n-количество вершин графа. Элементами матрицы смежности являются 0 и 1, Если вершины соединены, то ставится 1 и наоборот.

Матрица смежности симметрична относительно главной диагонали.

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

Для изоморфных графов верно следующее:

GG'¦V (G) ¦=¦V (G') ¦, ¦E (G) ¦=¦E (G') ¦,

{deg(v)¦v V(G)} = {deg(v)¦v V(G')}.

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

Составим матрицы смежности для графов G и G':

.

2.3.2 Матрица инцинденций

Пусть имеется граф G, не содержащий петель, имеющий n вершин и m дуг (ребер). Графу G можно сопоставить матрицу инциденций графа G. Строки m этой матрицы соответствуют вершинам, столбцы n - дугам (ребрам) графа. Если граф неориентированный, то элементами матрицы будут 1 и 0.

2.3.3 Массив ребер

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

Представляются графы в таком виде:

Количество вершин в графе G:6

Количество ребер в графе G:6

Начальная вершина ребра 1: 1

Конечная вершина ребра 1: 2

Начальная вершина ребра 2: 2

Конечная вершина ребра 2: 3

Начальная вершина ребра 3: 3

Конечная вершина ребра 3: 4

Начальная вершина ребра 4: 4

Конечная вершина ребра 4: 2

Начальная вершина ребра 5: 4

Конечная вершина ребра 5: 6

Начальная вершина ребра 6: 6

Конечная вершина ребра 6: 5

Количество вершин в графе G':6

Количество ребер в графе G':6

Начальная вершина ребра 1: 3

Конечная вершина ребра 1: 6

Начальная вершина ребра 2: 6

Конечная вершина ребра 2: 1

Начальная вершина ребра 3: 1

Конечная вершина ребра 3: 5

Начальная вершина ребра 4: 5

Конечная вершина ребра 4: 2

Начальная вершина ребра 5: 2

Конечная вершина ребра 5: 4

Начальная вершина ребра 6: 4

Конечная вершина ребра 6: 6

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



3. Алгоритм (блок-схема)

Обозначения:

V1-количество вершин в первом графе

E1-количество ребер в первом графе

V2-количество вершин во втором графе

E2- количество ребер во втором графе

[i ; j]-индексы элемента в массивах и матрицах смежностей [номер строки; номер столбца]

mA[i] и mB[i]- отсортированные в порядке возрастания вектора степеней графов

S-количество преобразований



Пошаговая проверка на изоморфизм двух графов вручную.

С помощью описанного выше алгоритма докажем, что графы G и G' изоморфны.

Сначала надо преобразовать графы в матрицы смежности.

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

Далее найти векторы степеней каждого графа и сравнить их.

S(G)=(1,2,2,2,2,3)

S(G')=(1,2,2,2,2,3)

Так как векторы степеней одинаковые, то продолжаем проверку с помощью перестановки строк и столбцов в матрице смежности графа G':

1) Переставим местами 3 строку с 1 и 3 столбец с первым

Так как матрицы не одинаковые, то продолжаем преобразования

2) Переставим местами 6 строку со 2 и 6 столбец со 2

Сравнив измененную матрицу G' с матрицей G видно, что они одинаковые и отсюда следует, что графы G и G' изоморфны.



4. Реализация программы на языке C#

изоморфизм граф массив матрица

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Изоморфизм_графов

{

class Program

{

static void Main(string[] args)

{

Console.Write("Enter the number of vertices: "); int v1 = int.Parse(Console.ReadLine());

Console.Write("Enter the number of ribs: "); int e1 = int.Parse(Console.ReadLine());

int[,] m1 = new int[e1, 2];

for (int i = 0; i < e1; i++)

{

Console.Write("\nEnter the number of first a vertex for an " + (i + 1) + " rib: "); m1[i, 0] = int.Parse(Console.ReadLine()) -1;

Console.Write("\nEnter the number of second a vertex for an " + (i + 1) + " rib: "); m1[i, 1] = int.Parse(Console.ReadLine())-1;

}

//ввели вершины и ребра для первого графа

bool [,] a= new bool[v1,v1],

b = new bool[v1, v1];

for (int i = 0; i < e1; i++)

{

a[m1[i, 0], m1[i, 1]] = true;

a[m1[i, 1], m1[i, 0]] = true;

}

//построили матрицу смежности для первого графа

Console.Write("Enter the number of vertices: "); int v2 = int.Parse(Console.ReadLine());

Console.Write("Enter the number of ribs: "); int e2 = int.Parse(Console.ReadLine());

int[,] m2 = new int[e2, 2];

for (int i = 0; i < e2; i++)

{

Console.Write("\nEnter the number of first a vertex for an " + (i + 1) + " rib: "); m2[i, 0] = int.Parse(Console.ReadLine())-1;

Console.Write("\nEnter the number of second a vertex for an " + (i + 1) + " rib: "); m2[i, 1] = int.Parse(Console.ReadLine())-1;

}

for (int i = 0; i < e2; i++)

{

b[m2[i, 0], m2[i, 1]] = true;

b[m2[i, 1], m2[i, 0]] = true;

}

//////заполнили матрицы смежности

int[] mA = new int[v1], mB = new int[v2];

mA = Schet(a);

mB = Schet(b);

for (int i = 0; i < mA.Length && i < mB.Length; i++)

if (mA[i] != mB[i])

{ Console.WriteLine("Not Isomorphism"); break; }

int f = 0;

while (f < v1 && f < v2)

{

int s = 0;

for (int j = 0; j < v1 && j < v2; j++)

if (a[f, j] != b[f, j])

if (s < Fact(v1))

{

bool q = false;

for (int w = 0; w < mA.Length; w++)

{

for (int g = 0; g < mB.Length; g++)

{

if (mA[w] == mB[g])

{

bool t;

for (int h = 0; h < b.Rank; h++)

{

t = b[h, w];

b[h, w] = b[h, g];

b[h, g] = t;

}

for (int h = 0; h < b.Rank; h++)

{

t = b[w, h];

b[w, h] = b[g, h];

b[g, h] = t;

}

q = true;

}

if (q) break;

}

if (q) break;

}

f = 0; s++;

break;

}

else { Console.WriteLine("Not Ispmorphism"); break; }

f++;

}

if ((f>=v1-1 || f >= v2-1))

Console.WriteLine("Ispmorphism");

Console.Read();

}

static void Izomorf(int i, int j, bool[,] a, bool [,] b)

{

}

static public int Fact(int x)

{

var y = 1;

for (int i = 1; i < x; i++)

y = y * i;

return y;

}

static int[] Scan(bool[,] x)

{

int[] mX = new int[x.Rank];

for (int j = 0; j < (x.Rank); j++)

{

int xx = 0; //количество true в строке

for (int i = 0; i < (x.Rank); i++)

if (x[i, j])

xx++;

mX[j] = xx;

}

return mX;

}

static int[] Schet(bool[,] x)

{

int[] mX = new int[x.Rank];

for (int j = 0; j < (x.Rank); j++)

{

int xx = 0; //количество true в строке

for (int i = 0; i < x.Rank; i++)

if (x[i, j])

xx++;

mX[j]=xx;

}

for (int j = 1; j < mX.Length; j++)

{

int min = mX[j], temp = j, ind = j;

for (int i = j; i < mX.Length; i++)

if (min > mX[i])

{

min = mX[i];

ind = i;

}

temp = mX[j];

mX[j] = min;

mX[ind] = temp;

}

return mX;

}

}

}



Заключение

Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом.



Список литературы

⁽¹⁾ Татт У. Теория графов. - М.: Мир, 1988. - 424 с.

⁽²⁾ Земляченко В.Н., Корнеенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов // Теория сложности вычислений, I. Записки научных семинаров ЛОМИ. - 1982. - Т.118. - С.83-158.

⁽³⁾ Зыков А.А. Основы теории графов. М.: Наука, 1987. - 384 с.

⁽⁴⁾ Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: Высш.шк., 1976. - 392 с.

⁽⁵⁾ Рейнгольд Э., Hивергельт Ю., Део H. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.

⁽⁶⁾ Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. - М.: Мир, 1981. - 368 с.

Размещено на Allbest.ru