Алгоритм определения числа путей длины

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

Федеральное агентство морского и речного транспорта

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Государственный университет морского и речного флота

Факультет информационных технологий

Курсовая работа

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

Алгоритм определения числа путей длины

Санкт-Петербург 2014

1. Определение графа

Граф - это совокупность 2-х множеств: непустого множества вершин и множества рёбер.

a b c - называются вершинами, а соединения между ними - ребра.

В данном случае E = 3 ребра и V = 3 вершины.

G = (V, E)

G - граф, V - вершины, E - ребра.

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

Рис. 1 Неориентированный граф

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

Ориентированные графы имеют следующую форму записи:

G = (V, A),

где V - вершины, A - направленные ребра.

граф дерево связность путь

Рис. 2 Ориентированный граф

Смешанные графы они могут иметь как направленные ребра, так и ненаправленные.

Форма записи данного типа:

G = (V, E, A)

где, V - вершины, E - ребра, A - направленные ребра.

Рис. 3 Смешанный граф

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

2. Деревья

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

Рис. 4 Бинарное дерево

3. Свойства деревьев

Дерево не имеет кратных рёбер и петель.

Любое дерево с вершинами содержит n - 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда , где B - P = 1число вершин, -- число рёбер графа.

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

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

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

Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

4. Длина

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

Расстоянием между вершинами u и v называется длина кратчайшей цепи d(u, v).

Определения путей в графе

Пусть задан ориентированный невзвешенный граф G с n вершинами, и задано целое число k. Требуется для каждой пары вершин i и j найти количество путей между этими вершинами, состоящих ровно из k рёбер. Пути при этом рассматриваются произвольные, не обязательно простые (т.е. вершины могут повторяться сколько угодно раз).

Будем считать, что граф задан матрицей смежности, т.е. матрицей размера , где каждый элемент равен единице, если между этими вершинами есть ребро, и нулю, если ребра нет. Описываемый ниже алгоритм работает и в случае наличия кратных рёбер: если между какими-то вершинами i и j есть сразу m рёбер, то в матрицу смежности следует записать это число m. Также алгоритм корректно учитывает петли в графе, если таковые имеются. Очевидно, что в таком виде матрица смежности является ответом на задачу при -- она содержит количества путей длины между каждой парой вершин.

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

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

Таким образом, решение этой задачи можно представить следующим образом:

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

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

Задача. Найти все пути равные 3 в дереве

Программа

#include <iostream>

#include <fstream>

#include <iomanip>

using namespace std;

void poisk(int **a,int *&b,int n,int beg,int start,int k)

{

k++;

bool check=true;

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

{

if (a[start][i]==1 && i!=beg)

{

if ((k<b[i] && b[i]!=3) || b[i]==-1 || k==3) b[i]=k;

poisk(a,b,n,start,i,k);

}

}

}

int main()

{

setlocale(LC_ALL,"Rus");

int n;

ifstream in("in.txt");

in » n;

int **a=new int *[n];

int *b= new int [n];

for (int i=0; i<n; i++) a[i]=new int[n];

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

{

for (int j=0; j<n; j++)

{

in » a[i][j];

}

}

cout « "матрица смежности графа: " « endl;

cout « "i\\j ";

for (int i=0; i<n; i++) cout « setw(2)«i+1 « " ";

cout « endl;

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

{

for (int j=0; j<n; j++)

{

if (j==0) cout «setw(2)« i+1 « " ";

cout « setw(2) «a[i][j] « " ";

}

cout « endl;

}

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

{

b[i]=-1;

}

poisk (a,b,n,-1,0,0);

cout « "Вершины с длиной пути 3: " « endl;

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

{

if (b[i]==3) cout « "Вершина: " « i+1 « endl;

}

system("PAUSE");

return 0;

Вывод

Программа работает верно. Все пути найдены.

Источники

1. Башмаков А.В., Зуров Е.В., Нырков А.П. Дискретная математика. Методы кодирования и обработки дискретных структур данных. СПб.: СПГУВК, 2012

2. Граф (математика) [Электронный ресурс] // Wikipedia теория графов // Режим доступа: http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)

3. Основные понятия и виды графов [Электронный ресурс] // Kvodo // Режим доступа: http://kvodo.ru/graph-algorithms-introduction.html

4. Количество путей фиксированной длинны [Электронный ресурс] // e-maxx// Режим доступа: http://e-maxx.ru/algo/fixed_length_paths

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