Характеристика теории графов

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

Содержание

Введение

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

2. Анализ предметной области

3. Описание организации структур данных

4. Описание алгоритма поиска центра графа

5. Формальное описание выходных данных

6. Описание процедур и функций

7. Результаты тестирования программы

Заключение

Литература

Аннотация



Введение

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

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

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Теория графов молодая наука относительно некоторых других поэтому терминология поныне не определена строго.

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



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

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

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

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

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

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

Задача нахождения центра графа

Определение

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

Постановка задачи нахождения центра графа.

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

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

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

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

2. Анализ предметной области

Граф представляет собой совокупность непустого множества вершин и ребер (наборов пар вершин). Две вершины на графе смежны, если они соединяются общим ребром. Путь в неориентированном графе представляет собой последовательность вершин P=()принадлежит V*V*…*V, таких что смежна с для 1 ? i ? n. Такой путь P называется путем длиной n из вершины в (i указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе).

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

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| -- порядком, число рёбер |E| -- размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть

Степенью deg V вершины V называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Графы делятся на два типа, обычные и сложные

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

формально, орграф D=(V,E) состоит из множества V, элементы которого называются вершинами, и множества E упорядоченных пар вершин .

Дуга (u,v) инцидентна вершинам u и v. При этом говорят, что u -- начальная вершина дуги, а v -- конечная вершина.

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

Направленный полный граф называется турниром.

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

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

Контур есть замкнутый путь.

Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур.

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

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

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

3. Описание организации структур данных

Программа организована согласно принципам объектно-ориентированного программирования(ООП). Имеется главный класс с главной функцией main(), которая по очереди вызывает методы другого класса, проводящего операции над данными.

Главный класс имеет название GraphCenterFinder, а другой класс Graph содержит все переменные и методы(функции), которые нужны для решения основного задачи нахождения центра графа. Кроме вызова функций другого класса, главная функция так же проверяет правильность указанных параметров при вызове. Если их слишком много, либо если они вовсе не указаны главная функция сообщит об этом сообщением на экране.

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

Переменные класса Graph включают исходную матрицу, матрицу кратчайших расстояний и искомое расстояние от центрального графа до наиболее удаленной точки.

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

4. Описание алгоритма поиска центра графа

Центром является любая вершина х с наименьшим значением МВВ(х) (максимальное расстояние вершина-вершина), т. е. центр -- это любая вершина х, такая, что расстояние от нее до наиболее отдаленной вершины минимально.

МВВ(х) =min{МВВ(i)}

Центр отыскивается как один из элементов матрицы DN, значение i, j-го элемента которой -- di,j есть кратчайшее расстояние от вершины i к вершине j. Элементы матрицы могут быть вычислены с помощью алгоритма Флойда или алгоритма Данцига.

Опишем их:

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

Алгоритм Данцига - этот алгоритм отличается от алгоритма Флойда последовательностью выполнения действий. Перенумеруем все вершины графа от 1 до n целыми числами и обозначим через di,jm длину пройденного пути из i в j где в качестве промежуточных использованы первые m вершин графа. Матрица Dm длин кратчайших путей имеет здесь размерность m*m.

Вернемся теперь к описанию алгоритма поиска центра графа:

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

Если описать алгоритм поиска центра коротко, то он будет выглядеть следующим образом

1. находим D0 - матрицу, элементами которой являются ai,j - длины кратчайших дуг.

2. Ищем DN - матрицу длин кратчайших расстояний по Флойду или Данцегу.

3. Определяем МВВ(i) для каждой вершины графа.

4. Из всех МВВ(i) выбираем минимальное соответствующая вершина и будет центром.

Пример:

Допустим нам необходимо найти центр графа представленного на рисунке:

Рис 1. Исходный граф

Составим матрицу длин кратчайших дуг между каждой парой вершин - D0, в случае, если дуги между вершиной i и j не существует, элементу ai,j матрицы присваивается значение ?. Матрица D0:

C помощью алгоритма Флойда или Данцега получаем матрицу длин кратчайших путей между каждой парой вершин графа:

Теперь, основываясь на полученной нами матрице длин кратчайших путей, найдем МВВ(i) для каждой вершины графа

МВВ(i)=max{di,j}.

МВВ(1)=max{d(1, j)}=152

МВВ(2)=max{d(2, j)}=122

МВВ(3)=max{d(3, j)}=145

МВВ(4)=max{d(4, j)}=133

МВВ(5)=max{d(5, j)}=197

МВВ(6)=max{d(6, j)}=197

МВВ(7)=max{d(7, j)}=104

МВВ(8)=max{d(8, j)}=200

Центром графа является такая вершина x, для которой МВВ(x)=min{МВВ(i)}. Минимальное значение имеет МВВ(7)=104, а это значит, что вершина 7 является центром графа.

Описание исходного кода программы

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

Кроме созданных самостоятельно классов были использованы также классы, находящиеся в стандартной библиотеке, среди которых:

java.io.* - который содержит классы для работы с потоком ввода/вывода

java.util.Scanner - который содержит классы для работы с вводом/выводом чтением из файла и работы с ним.

Приведем весь исходный код программы:

файл GraphCenterFinder.java

public class GraphCenterFinder {

//Метод должен принимать в качестве параметра имя файла

//с матрицей расстояний исходного графа

//вызов: java GraphCenterFinder имя_файла.txt

public static void main(String[] args) {

//Проверка правильности указания параметров

switch (args.length) {

case 0:

System.out.println("Ошибка! Не указано имя файла.");

System.exit(-1);

break;

case 1:

break;

default: граф множество вершина код

System.out.println("Неверно указаны параметры для запуска программы.");

System.exit(-1);

break;

}

String fileName = args[0];

Graph graph = new Graph("Graph", fileName);

graph.findGraph();

graph.getGraph();

graph.floydAlgorithm();

graph.CenterFinder();

}

}

файл Graph.java

public class Graph {

//Имя файла, содержащего граф

private String fileName;

private String name;

private int vertexCount; //Количество вершин в графе

private int[][] graph; // Матрица с исходным графом

private int[][] shortcut; //Матрица кратчайших расстояний

/*eccentricity - Массив эксцентриситетов.

* в этом одномерном массиве опеределено значение от наиболее удаленной вершины графа

* до текущей вершины

* Сама удаленная вершина не так важна, неоходимо знать только расстояние

* */

private int eccentricity[];

/*переменная minEccentricity собственно и является искомой

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

* являются центрами графа.

* */

private int minEccentricity;

//Конструктор

Graph (String nameParam, String fileNameParam){

this.name = nameParam;

this.fileName = fileNameParam;

}

public void findGraph() {

char ch;

try (Scanner fileScanner = new Scanner(new File(fileName))) {

do {

ch = fileScanner.next().charAt(0);

if (ch == '#') {

if (fileScanner.hasNextInt()) {

vertexCount = fileScanner.nextInt();

//Создание массива и его обнуление

graph = new int[vertexCount][vertexCount];

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

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

graph[i][j] = 0;

//Чтение матрицы графа из файла

for (int i = 0; i < vertexCount; i++){

for (int j = 0; j < vertexCount; j++) {

if (fileScanner.hasNextInt()){

graph[i][j] = fileScanner.nextInt();

}

else {

if ('-' == fileScanner.next().charAt(0))

graph[i][j] = Integer.MAX_VALUE/100;//Примем бесконечность за сотую долю максимального значения, чтоб не иметь проблем при сложении максимальных чисел

}

}

}

}

}

} while (fileScanner.hasNext());

} catch (FileNotFoundException e) {

System.err.println("Ошибка! Данный файл не найден");

System.exit(-1);

}

}

public void getGraph() {

System.out.println("Исходный граф:");

for (int i = 0; i < vertexCount; i++){

for (int j = 0; j < vertexCount; j++){

if (graph[i][j] == Integer.MAX_VALUE/100) {

System.out.print("-\t");

}

else

System.out.print(graph[i][j] + "\t");

}

System.out.println();

}

}

//Алгоритм Флойда-Уоршера для нахождения минимального расстояния между всеми вершинами

public void floydAlgorithm() {

shortcut = new int[vertexCount][vertexCount];

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

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

shortcut[i][j] = graph[i][j];

for (int k = 0; k < vertexCount; k++)

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

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

if (shortcut[i][k] != 0 && shortcut[k][j] != 0 && i != j)

if (shortcut[i][k] + shortcut[k][j] < shortcut[i][j] || shortcut[i][j] == 0)

shortcut[i][j] = shortcut[i][k] + shortcut[k][j];

System.out.println("\n\n\nТаблица кратчайших расстояний между вершинами, найденная согласно алгоритму Флойда-Уоршера");

for (int i = 0; i < vertexCount; i++){

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

System.out.print(shortcut[i][j] + "\t");

System.out.println();

}

}

//Функция нахождения наибольших расстояний от вершин

public void CenterFinder() {

int max;

eccentricity = new int[vertexCount];

System.out.println("\n\n\nРасстояние от каждой из вершин до другой наиболее удаленной(ых) вершин(ы)");

for (int i = 0; i < vertexCount; i++){

max = shortcut[i][0];

for (int j = 0; j < vertexCount; j++){

if (shortcut[i][j] > max) {

max = shortcut[i][j];

}

}

eccentricity[i] = max;

System.out.println("MBB(" + (i+1) + ") = " + eccentricity[i]);

}

minEccentricity = eccentricity[0];

for (int i = 0; i < vertexCount; i++){

if (eccentricity[i] < minEccentricity)

minEccentricity = eccentricity[i];

}

System.out.println("\nРасстояние от центра графа до наиболее удаленных(ой) вершин(ы) - " + minEccentricity);

/*Минимальный эксцентриситет может быть не у одной вершины, а у нескольких.

* В таком случае все вершины, которые имеют такое же значение являются центрами графа

* */

System.out.print("\nЦентром графа явля(ю)тся вершина(ы): ");

for (int i = 0; i < vertexCount; i++){

if (eccentricity[i] == minEccentricity)

System.out.println((i+1) + " ");

}

}

}

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

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

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

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

5. Формальное описание выходных данных

После чтения матрицы вершин графа и проведения всех необходимых процедур согласно алгоритму, на экран выведется вершина, которая является центром графа. Кроме того, выводится расстояние от этого центра до наиболее удаленной вершины.

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



Описание диалога

В зависимости от введенных данных возможны несколько вариантов развития диалога с пользователем.

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

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

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

6. Описание процедур и функций

void main(String[] args) - главная функция, которая вызывает все остальные подпрограммы и функции. В качестве параметров принимает массив строк. В данном случае, на вход должна поступать одна строка, содержащая имя файла.

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

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

void floydAlgorithm() - данная функция применяет алгоритм Флойда-Уоршелла к исходной матрице. Этот алгоритм должен находить кратчайшие пути между всеми вершинами графа. Данная матрица проходит абсолютно по всем возможным путям, таким образом находит все возможные пути, сравнивает их между собой и сохраняет только кратчайшие пути. Перед завершением работы функция также выводит на экран получившуюся матрицу кратчайших расстояний для демонстрации ее пользователю.

void CenterFinder() - эта функция как раз и выводит искомый центр граф. Опишем ее работу. Во-первых, она создает массив наибольших расстояний эксцентриситетов. Этот массив содержит расстояния от каждой из вершнин до наиболее удаленной найденной из матрицы кратчайших расстояний, найденной в предыдущей функции.

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

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

7. Результаты тестирования программы

Тестирование программы осуществлялось на устройстве со следующими характеристиками:

ОС: Windows 10 x-64

Оперативная память: 8 гб

Процессор: Intel(R) Core(TM) i7-4510 2.00 ГГц.

Рис 1. Сообщение, выводящееся, если параметры запуска не указаны

Рис 2. Сообщение выводящееся, если указано слишком много параметров

Рис 3. Сообщение об ошибке именования файла.



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

Рис 5. Содержимое исходного файла.



Заключение

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

Перед началом работы были рассмотрены много вариантов относительно используемого языка. Помимо Java рассматривались так же и Python и C++. Так же стоял огромный выбор для одной из подзадач - нахождение кратчайших расстояний между вершинами. В литературе было представлено огромное множество возможных алгоритмов. В итоге был выбран алгоритм Флойда-Уоршелла, который проходит по абсолютно всем возможным путям. Данный алгоритм не отличается высокой скоростью, однако он очень надежен и гарантирует, что не будет пропущено ни единого пути как на больших количествах вершин, так и на малых.

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

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



Литература

1. Шилдт Г. Java: руководство для начинающих -- М.: Вильямс, 2012. -- 624с.

2. Брюс Экель Философия java - П.: Питер, 2012. - 1168c.



Аннотация

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

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

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

Данная программа находит центр графа, чтение исходного графа осуществляет из файла, указанного в качестве параметре запуска. В файле должно содержаться число, которое определяет количество вершин графа, а также матрица расстояний между всеми вершинами. Если между вершинами отсутствует прямой путь, то необходимо указать дефис «-».

Программа написана на языке Java.

Пояснительная записка содержит:

Печатных листов - 29шт.;

Рисунков - 5шт.;

Ключевые слова:

Программирование, Java, граф, центр графа, ООП, алгоритм Флойда-Уоршера, работа с файлами, функции.

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

...