Определение метрических характеристик графа

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

1.1 Теоретические понятия

1.2 Граф как основное средство для описания структуры сложных объектов и функционирования систем

2. Метрические характеристики

2.1 Размещение центров

2.2 Определение медиан

3. Практическая часть

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

3.2 Назначение программы

3.3 Входные и выходные данные

3.4 Язык программирования

3.5 Системные требования

3.6 Модульный состав программы

3.7 Описание структуры программы

3.8 Руководство пользователю

3.9 Блок — схемы

3.10 Контрольный пример

Заключение

Приложение. Листинг программы

Тема курсовой работы «Определение метрических характеристик графа» является весьма актуальной. Особое значение с практической точки зрения имеет теория графов, использующаяся при проектировании интегральных схем и схем управления, исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, при разработке вычислительных и информационных сетей, в схемотехническом и конструкторско-топологическом проектировании, и т. д. Обширное применение теория графов находит в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании ЭВМ, баз данных, систем логического управления.

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

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

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

1.1 Теоретические понятия

Графом называется пара (V, E), где V — конечное множество вершин, а E — набор неупорядоченных и упорядоченных пар вершин. Обозначим граф G=(V, E). Неупорядоченная пара вершин называется ребром, упорядоченная — дугой. Граф содержащий только ребра называется неориентированным, только дуги — ориентированным, или орграфом.

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

Для орграфа на рис. 3 входящие степени вершин 1,2,3,4,5 равны соответственно 0,1,1,1,0, исходящие — 2,0,0,1,0. Степени вершин, получаемые сложением входящих и исходящих степеней равны 2,1,1,2,0. Таким образов, вершина 5 — изолированная.

Ребро, соединяющее вершину саму с собой называется петлей. Если одну пару вершин соединяют два или более ребер, то такие ребра называют кратными. Граф называется простым, если он не содержит ни петель, ни кратных ребер, иначе граф называется мультиграфом. (В некоторых источниках граф с кратными ребрами называют мультиграфом, с петлями — псевдографом.) Простой граф, любая пара вершин которого соединена ребром, называется полным. В полном графе n*(n-1)/2 ребер.

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

Подграфом графа G=(V, E) называется граф G'=(V', E') такой, что V' V, E' E.

Путем из вершины u в вершину x называется последовательность вершин (v0,v1,…, vk), в которой v0=u, vk=x и (vi-1,vi) E. Длина этого пути равна k. Такой путь проходит через вершины v0, v1,…, vk, а также ребра (v0,v1), (v1,v2),…,(vk-1,vk). Вершина v0 — начало пути, vk — конец пути. Говорят, что путь ведет из v0 в vk. Если существует путь из вершины u в вершину x, говорят, что x достижима из u.

Пример. На рис. 4 последовательность вершин (5,1,3,4) является путем.

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

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

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

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

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

Граф, в котором нет циклов называется ациклическим.

Связный граф без циклов называется деревом.

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

Графы G1=(V1,E1) и G2=(V2,E2) изоморфны, если существует такое взаимно однозначное отображение ѓ:V1?V2, что для произвольных v и uV1 имеем (v, u) E1(ѓ(v),ѓ(u)) E2. Отображение ѓ называется изоморфизмом (или изоморфным отображением) графов G1 и G2. При изоморфизме каждая вершина переходит в вершину с той же степенью. Пример изоморфных графов на рис. 6 (1->2, 2->4, 3->5, 4->3, 5->1).

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

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

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

Список ребер Наиболее очевидный способ — хранить список пар вершин, соединенных ребрами. Для его хранения необходим двумерный массив размерности M2 (M — количество ребер). Строка массива описывает ребро. Для взвешенных графов такой способ создает необходимость дополнительно завести массив весов ребер.

Пример для орграфа на рис. 4:

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

Матрица смежности A представляет собой двумерный массив размерности NN (N — количество вершин). A[i, j]=1, если существует ребро (i, j) (дуга ), A[i, j]=0 — в противном случае. Для неориентированных графов матрица смежности симметрична относительно главной диагонали.

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

Список связей Третий способ — хранение списка всех ребер инцидентных каждой из вершин. Для этого необходим массив, содержащий N элементов, где N — количество вершин в графе. i-ый элемент этого массива содержит список всех ребер, смежных с i-ой вершиной (ребро представлено номером второй инцидентной ему вершины). [2]

1.2 Граф как основное средство для описания структуры сложных объектов и функционирования систем

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

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

Специальный тип графа, широко используемый в искусственном интеллекте и программировании, а также в задачах теории принятия решений, исследовании операций и системном анализе, получил название И/ИЛИ граф. И/ИЛИ граф описывает развитие некоторого процесса от начальной вершины графа к множеству конечных вершин (рис.10). Все остальные (не начальная и не конечные) вершины делятся на два типа: вершины И и вершины ИЛИ. Вершина первого типа возбуждается только при наличии сигналов активизации на всех ее входах, а вершина ИЛИ — при появлении хотя бы одного сигнала активизации на любом из ее входов. Активизированная вершина передает сигналы активизации на все сопряженные с ней вершины. Внешние сигналы активизации порождаются внешними источниками, которыми, в частности, могут быть выходные вершины других И/ИЛИ графов.

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

Пример графа И/ИЛИ

На рисунке 9 изображена шахматная мини-доска размером 33 клетки, а на ней четыре коня — два белых и два чёрных. Задача — переставить фигуры так, чтобы одинаковые кони оказались в противоположных углах доски (рис. 10). Перемещать их можно только ходом шахматного коня и нельзя ставить фигуру на уже занятое поле.

Позиция 1. Позиция 2.

Все попытки совершить такую перестановку терпят неудачу. Почему? Давайте начертим граф возможных ходов коней по доске (рис. 11).

Граф возможных ходов коней по доске.

Затем построим изоморфный ему граф без самопересечений в двух вариантах: на одном отметим первоначальное положение коней, а на другом — требуемое (рис. 12). Вот теперь понятно, почему задача не решается. Движение коней по графу означает переходы в соседние вершины, и перейти из позиции, а в позицию б невозможно без «перескока» через коня другого цвета.

Движение коней по графу.

Вообще, граф игры — это граф, вершины которого — ситуации, возникающие в процессе игры, а ребра связывают вершину с теми вершинами-ситуациями, которые могут сложиться после очередного хода. Так, в шахматах из начальной позиции первым ходом можно получить 20 позиций: каждая пешка может пойти на одну или две клетки вперёд, и каждый конь может пойти на одно из двух полей. После хода чёрных число возможных позиций становится равным 2020 = 400 и в дальнейшем быстро увеличивается. Это обстоятельство и стало основной трудностью при создании шахматных программ.

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

Нарисуем граф всевозможных продолжений игры (рис. 13).

Видно, что после первого хода на столе остаётся 3 или 4 спички. Если тот, кто начинает, оставит на столе 3 спички, то он выиграет: ведь его партнёр вынужден будет оставить 1 или 2 спички, которые начинавший и заберёт на следующем ходу. Если же начинающий игру оставит 4 спички, то он проиграет, так как партнёр, взяв 1 спичку, оставит ему 3, что, как мы уже видели, ведёт к проигрышу игрока, делающего очередной ход. Конечно же, второй игрок может оставить 2 спички и тут же проиграть, но надеяться на это не приходится. Можно сделать вывод: начинающий проигрывает, если исходное число спичек делится на 3, и выигрывает в остальных случаях, оставляя партнёру всякий раз количество спичек, которое делится на 3.

Граф возможных продолжений игры «в спички».

Одна из классических задач теории графов называется «задачей коммивояжера» или «задачей о бродячем торговце».

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

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

Интересно, что алгоритм нахождения оптимального варианта строительства довольно прост (чего нельзя сказать о других задачах теории графов). Продемонстрируем его на примере дороги, соединяющей пять городов: A, B, C, D и E. Стоимость прокладки пути между каждой парой городов указана в таблице.

Сначала строим ту дорогу, которая имеет наименьшую стоимость. В нашем случае это маршрут B — E. Теперь найдем самую дешевую линию, соединяющую город B или E с каким-то из остальных городов. Это путь между E и C. Включаем его в схему. Далее поступаем аналогично: ищем самый дешевый из путей, соединяющих один из городов B, C, E с одним из оставшихся — A или D. Это дорога между C и A. Осталось подключить к железнодорожной сети город D. Дешевле всего соединить его с C. Получим сеть, изображенную на рисунке 14.

Схема железнодорожной сети.

Описанный алгоритм относится к категории «жадных»: на каждом шаге мы выбираем самое дешевое продолжение пути. Для данной задачи он подходит как нельзя лучше. Но в других случаях «жадные» алгоритмы могут не давать оптимальное решение, например, в задаче коммивояжера.

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

2. Метрические характеристики

Пусть G=(X, U) — связный граф, а xi и xj — две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины xi и xj (пути из xi в xj) называется расстоянием между вершинами xi и xj и обозначается d (xi, xj). Положим d (xi, xj) =, если вершины xi и xj не соединены маршрутом (путем). Расстояние d (xi, xj) удовлетворяет следующим аксиомам метрики:

1) d (xi, xi) = 0;

2) d (xi, xj)? 0;

3) d (xi, xj) = 0 тогда и только тогда, когда xi = xj;

4) d (xi, xj) = d (xj, xi) для симметрических графов;

5) d (xi, xj) + d (xj, xk)? d (xi, xk) (неравенство треугольника).

Расстояние для графа G удобно задавать матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n, элементы которой определяются следующим образом:

Для фиксированной вершины xi величина называется эксцентриситетом (отклоненностью) вершины .

Максимальный среди эксцентриситетов вершин называется диаметром графа G.

Минимальный из эксцентриситетов вершин связного графа называется его радиусом.

Вершина, имеющая минимальный эксцентриситет, называется центром графа.

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

Степенью или валентностью вершины, а неорграфа G называется число ребер, инцидентных вершине а, т. е. число ребер, концом которых является вершина, а (при этом петли считаются дважды). Если G — орграф, то степени его вершин определяются как степени вершин в соответствующем неорграфе F (G). Аналогично вводится понятие степени вершины в мультиграфах. Степень вершины, а будем обозначать через degGа или просто deg a. Вершина степени 0 называется изолированной, вершина степени 1 — концевой или висячей. [4]

2.1 Размещение центров

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

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

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

Для любой вершины хi графа G = (X, Г) пусть R0(xi) есть множество тех вершин хj — графа G, которые достижимы из вершины xi с помощью путей со взвешенными длинами vjd (хi, хj), не превосходящими величины. Через Rt (xi) будет обозначаться множество тех вершин xj графа G, из которых вершина хi может быть достигнута с использованием путей, имеющих взвешенные длины vjd (хi, хj).

Таким образом,

(1)

Для каждой вершины хi определим следующие два числа:

(2)

Числа so (хi) и st (xi) называются соответственно числом внешнего разделения и числом внутреннего разделения вершины хi. Следует отметить, что so (хi) является наибольшим числом в строке xi матрицы D'(G), полученной в результате умножения каждого столбца j матрицы расстояний D (G) = [d (хi, хj)] на vj и st (хi) является наибольшим числом в столбце хi матрицы D''(G), полученной после умножения каждой строки j матрицы расстояний D (G) на vj.

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

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

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

Если 0 — наименьшая длина, такая, что для вершины xi

R0(xi) = X

(т. е. все вершины графа G достижимы из хi с использованием путей, взвешенные длины которых не превосходят 0, причем 0 — наименьшее из таких чисел), то из соотношений (1) и (2) следует равенство

s0(хi) = 0. (3)

Аналогично, если t — такая наименьшая длина, что

Rt = X,

то st (xi) = t.

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

Центр и радиус

Вершина х0*, для которой

, (4 (а))

называется внешним центром графа G; и аналогично вершина хt*, для которой

, (4(б))

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

У графа может быть несколько (больше, чем один) внешних и внутренних центров. Таким образом они образуют множества внешних и внутренних центров соответственно.

Число внешнего разделения вершины хo*, являющейся внешним центром, называется внешним радиусом: o = so (xo*); число внутреннего разделения внутреннего центра называется внутренним радиусом: t =st (хt*).

У графа, изображенного на рис. 15, с матрицей расстояний, приведенной выше, имеются только один внешний центр (вершина х5) и четыре внутренних центра, образующих множество {х2, х3, х5, х6}. Внешний радиус графа равен 2, а внутренний 3.

Абсолютный центр

Соотношение (3) определяют числа разделения для любой вершины xi X. Мы обобщим теперь это определение на случай «искусственных» точек, которые можно помещать на дугах. Итак, если, а = (хi, хj) (см. рис. 16) представляет дугу графа с весом (длиной) сij, то точка у, помещаемая на этой дуге, может быть определена посредством задания длины l (хi, у) участка (хi, у) причем должно выполняться равенство

l (хi, у) + l (у, xj) = cij. (5)

Размещение на дуге.

Числа разделения so (у) и st (у) точки у независимо от того, является она вершиной графа G или искусственной точкой дуги графа G, определяются следующим образом:

, (6)

а для st (у) соответствующее выражение получается из соотношения (2).

Точка уo*, для которой

, (7)

называется абсолютным внешним центром графа; и аналогично определяется уt* - абсолютный внутренний центр.

Число внешнего разделения абсолютного внешнего центра называется абсолютным внешним радиусом: ro = so (уo*), и число внутреннего разделения абсолютного внутреннего центра называется абсолютным внутренним радиусом: rt = st (уt*).

Метод Хакими Этот метод очень прост и для неориентированного графа состоит в следующем (для ориентированного графа метод остается таким же, надо только каждое «неориентированное» понятие заменить его «ориентированным двойником»).

(i) Для каждого ребра аk графа найти точки (или точку) уk* на аk, которые имеют наименьшее число разделения.

(ii) Из всех точек уk* (k = 1, 2, …, m) в качестве абсолютного центра графа G выбрать точку с наименьшим числом разделения.

Возьмем ребро аk графа G (см. рис. 17). Имеем (из соотношения (6)):

(8)

поскольку расстояние d (yk, хi) равно либо длине маршрута, проходящего через вершину х, либо длине маршрута, проходящего через х, l (yk, х) и l (уk, х) являются длинами соответствующих частей ребра аk.

Первый шаг метода осуществляется следующим образом.

Пусть l (уk, х) = 1. Поскольку l (уk, х) = с — l (уk, х) = с —, то соотношение (8) примет вид

. (9)

Для фиксированной вершины хi и при каждом значении (0 с) можно найти наименьшие значения выражений, заключенных в соотношении (9) в квадратные скобки. Для этого выпишем отдельно два указанных выражения:

(10)

и, рассматривая их относительно, строим нижнюю «огибающую» для соответствующих им прямых линий.

Повторяя эту процедуру для всех вершин xi X, мы построим на одном и том же чертеже все остальные нижние «огибающие». Далее вычертим верхнюю «огибающую» для всех ранее полученных нижних «огибающих», которая (в силу соотношения (9)) дает числа разделения s (уk) для всех значений параметра, т. е. для всех точек yk ребра аk. Построенная огибающая (она составлена из линейных кусков) может иметь несколько минимумов. Точка уk, соответствующая наименьшему из этих минимумов, является (в силу соотношения (7)) абсолютным центром yk*, отвечающим дополнительному ограничению: он должен лежать на ребре аk. Абсолютным центром графа будет такая точка yk*, которой соответствует наименьший из минимумов, определяющих указанные выше абсолютные центры на ребрах аk (k = 1, 2, …, m).

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

Всякому локальному центру, расположенному на ребре (хi, xj), соответствует (как видно из соотношения (8), если положить все длины l равными нулю) его абсолютный локальный радиус (скажем, rij), который не меньше, чем рij, где

. (11)

Таким образом, рij есть нижняя оценка абсолютного радиуса графа, если абсолютный центр лежит на ребре (xi, xj). Следовательно, величина

(12)

(где, А — множество ребер графа) является обоснованной нижней оценкой абсолютного радиуса графа.

Допустим, что абсолютный центр расположен в середине ребра (xi, xj). Тогда, в силу соотношения (8), абсолютный радиус равен pij + vs*cij, где vs* - вес той вершины хs, в которой достигается наибольшее значение величины рij, указанной в соотношении (11). Следовательно,

(13)

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

Для графа, приведенного на рис. 18, у которого vi = 1 для всех хi X, получаем (используя формулу (11)) следующие результаты:

центр на а1 = (х3, х1) дает р3,1 = mах (2, 6, 2) = 6,

центр на а2 = (х2, х3) дает р2,3 = mах (8, 10, 6) = 10,

центр на а3 = (х5, х2) дает р5,2 = mах (2, 2, 4) = 4,

центр на а4 = (х1, х5) дает р1,5 = mах (6, 8, 4) = 8,

центр на а5 = (х1, х4) дает р1,4 = mах (8, 8, 2) = 8,

центр на а6 = (х4, х5) дает р4,5 = mах (2, 6, 8) = 8.

Верхняя оценка Н равна, следовательно (в силу соотношения (13)),

min (6 + 4, 10 + 1, 4 + 3, 8 + 1, 8 + 3, 8 + 2) = 7,

и поэтому ребра а2, а4, а5 и а6, для которых рij > 7, могут быть исключены из списка кандидатов на размещение абсолютного центра. Поиск абсолютного центра нужно вести только на двух оставшихся ребрах (так, как это было продемонстрировано раньше и показано на рис. 5 (а) и 5 (в)). Используя верхние и нижние оценки, удалось уменьшить поиск в 3 раза. Наименьшая нижняя оценка Р, вычисленная по формуле (12), равна Р = min (6, 10, 4, 8, 8, 8) = 4.

Эта оценка не является точной, поскольку истинная величина абсолютного радиуса r данного графа (найденная в разд. 2) равна 3. [5]

а) Размещение на ребре а1. б) Размещение на ребре а2.

в) Размещение на ребре а3. г) Размещение на ребре а4.

д) Размещение на ребре а2. е) Размещение на ребре а3.

2.2 Определение медиан

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

Алгоритм нахождения медианы:

1) построить матрицу кратчайших путей для заданного графа;

2) для каждой вершины определить суммы путей;

3) среди определенных сумм найти наименьшую. Вершина с номером, соответствующим этой минимальной сумме и будет медианой графа. [3]

3. Практическая часть

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

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

§ степеней вершин;

§ эксцентриситетов;

§ диаметра и радиуса;

§ периферийных вершин;

§ центральных вершин, включая абсолютный центр.

a. Назначение программы

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

3.2 Входные и выходные данные

Входные данные:

§ Количество вершин графа: целое положительное число из диапазона от 1 до 30.

§ Матрица весов ребер графа: двумерный массив целых чисел максимальной размерности 3030 элементов.

Выходные данные:

§ центры;

§ радиус;

§ диаметр;

§ эксцентриситеты вершин;

§ степени вершин;

§ периферийные вершины.

Все приведенные выше значения выходных данных принадлежат к целому типу данных.

Кроме того определяется абсолютные центры графа (если таковые имеются) которые представляют собой вещественное значение — расстояние от вершины.

Диапазон изменения значений входных и выходных данных ограничен пределами используемого типа integer (32 000).

3.3 Язык программирования

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

Среда проектирования Delphi — является ярчайшим примером реализации новейших мировых тенденций в развития технологий создания пользовательских Windows-приложений.

Еще совсем недавно о написании своих собственных программ под Windows рядовому программисту оставалось только мечтать. Это было связано с тем, что практически единственным инструментом разработки таких программ был язык Borland C++ for Windows, явно предназначенный для профессионалов.

Благодаря появлению Delphi, которая также является продуктом фирмы Borland, возможность несравнимо более легкого создания своих программ под Windows стала реальностью.

Вышеизложенное утверждение основывается на таких известных фактах как:

OS Windows является на сегодня самой массовой (популярной) и самой распространенной графической оболочкой, общепринятой во всем мире и несравнимо более перспективной, современной и мощной по сравнению с MS DOS;

Технология объектно-ориентированного программирования (ООП) и визуального проектирования, лежащие в основе среды Delphi, также отражает современные тенденции развития средств разработки;

Delphi — одно из наиболее развитых и совершенных средств разработки на сегодняшний день;

В основе среды Delphi лежит язык программирования Object Pascal, являющийся развитием языка Turbo Pascal той же фирмы Borland;

Изучение проектирования интерфейса стандартного вида (с использованием библиотеки стандартных компонент), является естественным после знакомства с библиотекой Turbo Vision, рассчитанной на работу в MS DOS;

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

Следует также помнить, что Delphi, являясь замечательным, удобным инструментом проектирования, является одновременно и весьма сложной системой. Эта сторона «медали» проявляется, в частности, в явной зависимости пользователя от полноты и корректности конкретной инсталляции Delphi на конкретном компьютере (рабочем месте). Отсутствие доступа к каким-либо из многочисленных ресурсов Delphi, разработанных и поставляемых фирмой Borland, порой может привести к полной невозможности дальнейшей работы над проектом.

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

Перечислим ключевые особенности среды Delphi:

Интегрированная среда разработки приложений (IDE — Integrated Development Environment) — позволяет создавать, компилировать, тестировать и редактировать проект или группу проектов в единой среде программирования.

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

Технология Two Ways Tools делает более эффективной работу с компонентами. При изменении программного кода в окне редактора кода Delphi соответствующим образом изменяются и сами компоненты. С другой стороны, изменения свойств компонентов при помощи инспектора объектов Delphi (Object Inspector) или изменения в окне формы немедленно отражаются в окне редактора кода.

Библиотека компонентов содержит множество стандартных компонентов, которые можно использовать при создании приложений. Сюда относятся, в частности, элементы управления в стиле Windows 95, а также шаблоны для форм и экспертов.

32-битовый компилятор Delphi генерирует исполняемые EXE-файлы. При этом существует возможность подключения DLL-библиотек. Во всех случаях компилирование занимает весьма незначительное время.

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

Совместимость приложений, обеспечиваемая средой Delphi, в условиях бурного развития технических средств (Hardware), становится все более актуальной задачей.

Возможность обработки ошибок с помощью механизма обработки исключительных ситуаций (Try … except, try … finally и др.), встроенного в Object Pascal и являющегося нововведением.

Подводя итоги, с точки зрения пользователя, можно выделить два аспекта успешного применения Delphi:

Реализация имеющихся функциональных возможностей.

Способ, которым эти функциональные возможности реализуются.

3.4 Системные требования

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

Требования к операционной системе компьютера:

Windows XP с пакетом обновления 2 (SP2);

Windows Vista или Windows Vista с пакетом обновления 1 (SP1);

Windows 7;

Windows 8.

Требования к составу технических средств.

Память: минимальные — 512 МБ, рекомендуемые — 1 ГБ;

Быстродействие процессора: минимальные — 1,0 ГГц, рекомендуемые 2,0 ГГц и выше.

Тип процессора: процессор, совместимый с Pentium III или выше.

Жесткий диск: требуется как минимум 10 МБ свободного места на диске.

Монитор: Super VGA с разрешением 800 600 пикселей или более высоким.

3.5 Модульный состав программы

Программа состоит из следующих файлов:

metric.dpr — главный файл проекта, размер 466 байт;

U1.pas — главный модуль, размер 5 547 байт;

U2.pas — модуль ввода исходных данных, размер 858 байт;

U3.pas — модуль вывода решения, размер 379 байт;

U4.pas — модуль настроек программы, размер 602 байта;

UCALC.PAS — вычислительный модуль, размер 4 293 байт;

metric.exe — исполняемый модуль программы, размер 722 944 байт.

3.6 Описание структуры программы

Константы.

nmax = 30 — максимальное число вершин графа (модуль UCALC).

_BIG_ = 10 000 — машинная бесконечность (модуль UCALC).

Типы.

matrica — двумерный массив размерности nmax*nmax (модуль UCALC).

vector — одномерный массив размерности nmax (модуль UCALC).

Программа состоит из следующих процедур и функций.

Процедура Floid (a, n, d)

Назначение: алгоритм Флойда определения матрицы кратчайших расстояний (модуль UCALC).

входные параметры:

a — матрица смежности графа, тип Matrica;

n — число вершин, тип integer;

выходные параметры:

d — матрица кратчайших расстояний, тип Matrica.

Функция deg (a, N, nv)

Назначение: определение степеней вершин (модуль UCALC).

входные параметры:

a — матрица смежности графа, тип Matrica;

n — число вершин, тип integer;

nv — номер вершины для которой определяется степень, тип integer.

Функция Excentr (a, n, nv)

Назначение: определение эксцентриситета вершины (модуль UCALC).

входные параметры:

a — матрица смежности графа, тип Matrica;

n — число вершин, тип integer;

nv — номер вершины для которой определяется эксцентриситет, тип integer.

Процедура DRG (eu, n, D, R)

Назначение: определение диаметра и радиуса графа (модуль UCALC).

входные параметры:

eu — массив эксцентриситетов вершин, тип Vector;

n — число вершин графа, тип integer;

выходные параметры:

D — диаметр графа, тип integer;

R — радиус графа, тип integer.

Процедура AbsCenter (D, N)

Назначение: определение абсолютного центра графа (модуль UCALC).

входные параметры:

D — матрица смежности графа, тип Matrica;

N — число вершин, тип integer.

Процедура Grafdraw

Назначение: построение графа на экране (модуль U1).

Локальные переменные:

R — радиус образующей граф окружности, тип integer;

k — параметр преобразования строки в число, тип integer;

N — число вершин графа, тип integer;

i, j — счетчики, тип integer;

x, y — массивы экранных координат вершин, тип array [1.100] of integer;

v — матрица смежности графа, тип matrica.

Процедура GrafClick

Назначение: ввод исходных данных (модуль U1).

Процедура VyhodClick

Назначение: выход из программы (модуль U1).

Процедура FormShow

Назначение: загрузка тестового примера в строки ввода (модуль U1).

Константа р1 задает матрицу тестового примера.

Локальные переменные:

N — число вершин графа, тип integer;

i, j — счетчики, тип integer.

Процедура MetricalClick

Назначение: управляющая процедура расчета метрических характеристик (модуль U1).

Локальные переменные:

Duv — матрица кратчайших путей, тип Matrica;

Mg — матрица смежности графа, тип Matrica;

n — число вершин графа, тип integer;

eu — массив эксцентриситетов вершин, тип Vector;

R — радиус графа, тип integer;

D — диаметр графа, тип integer;

i, j — счетчики, тип integer;

f — текстовый файл для вывода информации.

Процедура SpinEdit1Change

Назначение: изменение числа вершин графа (модуль U2).

Локальные переменные:

N — число вершин графа, тип integer;

i — счетчик, тип integer.

3.7 Руководство пользователю

После компиляции проекта на диске компьютера будет получен исполняемый файл с именем METRIC.EXE.

Порядок запуска программы из операционной системы Windows.

1. Кнопка «Пуск» «Выполнить» «Обзор», найти файл METRIC. EXE и установить на него указатель, нажать кнопку «Ввести» и в завершении кнопку «ОК».

2. С помощью окна «Мой компьютер». Выбрать в строке «Адрес» диск, на котором расположена программа — дважды щелкнуть папку с программой — установить указателя на файл METRIC. EXE и дважды щелкнуть его мышью.

После запуска на экране монитора компьютера появляется главное окно программы (рис. 19).

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

Главное окно

Назначение кнопок (слева направо).

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

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

§ вывод окна настроек программы.

§ выход из программы.

Рассмотрим последовательность работы пользователя. Нажимаем кнопку. На экран выводится окно диалога (рис. 20).

Вначале вводится число вершин — целое число от 1 до 30 в строку ввода, расположенную в нижней части окна.

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

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

Ввод графа

Далее необходимо выбрать список характеристик, которые будут рассчитаны. Нажимаем кнопку. В окне диалога (рис. 26) ставим флажки для расчетных параметров.

Задание характеристик

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

3.8 Блок - схемы

Структурная схема процедуры формирования матрицы кратчайших расстояний

Процедура определения степеней вершин

Процедура определения эксцентриситета вершины

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

3.9 Контрольный пример

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

Матрица расстояний

Результат работы программы приведен на рис. 27.

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

Заключение

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

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

§ вводить граф с клавиатуры;

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

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

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

1. Архангельский А. Я. Delphi 7. Справочное пособие. -М.: Бином, 2003. -453 с.

2. Басакер Р., Саати Т. Конечные графы и сети. -М.: Наука, 1997. -388 с.

3. Белоусов А. И., Ткачев С. Б. Дискретная математика: Учеб. для вузов / Под ред. В. С. Зарубина, А. П. Крищенко. -М.: Изд — во МГТУ им. Н. Э. Баумана, 2002. -744 с.

4. Горбатов В. А. Основы дискретной математики. — М.: Высшая школа, 1986. 311 с.

5. Емеличев В. А. Лекции по теории графов. -М.: Наука, 1990. -384 с.

6. Кофман А.

Введение

в прикладную комбинаторику. -М.: Наука, 1975, -479 с.

7. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978, -432 с.

8. Нечепуренко М. И. Алгоритмы и программы решения задач на графах и сетях. -Новосибирск: Наука, 1990. -515 с.

9. Окулов С. М. Программирование в алгоритмах. -М.: Бином, 2004. -341 с.

Приложение. Листинг программы

Вычислительный модуль

Unit UCalc;

Interface

const

Nmax = 30; //максимальное число вершин графа

_BIG_ = 10 000;

type

Matrica = array [1.Nmax, 1. Nmax] of longint;

Vector = array [1.Nmax] of longint;

Procedure Floid (a: Matrica; n: integer; var d: Matrica);

Function deg (a: Matrica; N, nv: integer): integer;

Function Excentr (a: Matrica; n, nv: integer): integer;

Procedure DRG (eu: Vector; n: integer; var D, R: integer);

Procedure AbsCenter (D: Matrica; N: integer);

var

f: text;

Implementation

Uses Math;

Procedure Floid (a: Matrica; n: integer; var d: Matrica);

{Алгоритм Флойда определения матрицы кратчайших расстояний

a — матрица смежности графа

n — число вершин

d — матрица кратчайших расстояний}

var

i, j, k: integer;

begin

d := a;

for i := 1 to n do

for j := 1 to n do

if d[i, j] = 0 then

d[i, j] := _BIG_;

for k := 1 to n do

for i := 1 to n do

for j := 1 to n do

d[i, j] := min (d[i, j], d[i, k] + d[k, j]);

for i := 1 to n do

d[i, i] := 0;

end;

Function deg (a: Matrica; N, nv: integer): integer;

{определение степеней вершин

a — матрица смежности графа

n — число вершин

nv — номер вершины для которой определяется степень}

var

i, k: integer;

begin

k := 0;

for i := 1 to N do

if a[i, nv] <> 0 then

Inc (k);

deg := k;

end;

Function Excentr (a: Matrica; n, nv: integer): integer;

{определение эксцентриситета вершины

a — матрица смежности графа

n — число вершин

nv — номер вершины для которой определяется эксцентриситет}

var

i, max: integer;

begin

max := -_BIG_;

for i := 1 to n do

if (A[nv, i] <> _BIG_) and (A[nv, i] > max) then

max := A[nv, i];

Excentr := max;

if max = _BIG_ then

Excentr := 0;

end;

Procedure DRG (eu: Vector; n: integer; var D, R: integer);

{определение диаметра и радиуса графа

eu — массив эксцентриситетов вершин

n — число вершин

D — диаметр графа

R — радиус графа}

var

i: integer;

begin

D := eu[1];

R := eu[1];

for i := 2 to n do

begin

if eu[i] > D then

D := eu[i];

if (eu[i] < R) and (eu[i] <> 0) then

R := eu[i];

end;

end;

Procedure AbsCenter (D: Matrica; N: integer);

{определение абсолютного центра графа}

var

P: Matrica;

ma, mai, maj, di, dj, k, i, j: integer;

mima, dist: real;

s, s1: string[80];

begin

for i := 1 to N do

for j := 1 to N do

if (i <> j) and (D[i, j] = 0) then

D[i, j] := _BIG_;

P := D;

{построение матрицы достижимости}

for k := 1 to N do

for i := 1 to N do

for j := 1 to N do

if P[i, j] > P[i, k] + P[k, j] then

P[i, j] := P[i, k] + P[k, j];

{начинается выбор места}

mima := MaxInt;

for i := 1 to N do

begin

ma := P[i, 1];

for j := 2 to N do

if P[i, j] > ma then {эксцетриситет}

ma := P[i, j];

if ma < mima then {центр}

mima := ma;

end;

di := 0;

dj := 0;

for i := 1 to N — 1 do

for j := i + 1 to N do

begin

if D[i, j] = MaxInt then

Continue;

mai := 0;

maj := 0;

for k := 1 to N do

begin

if (k = i) or (k = j) then

Continue;

if P[i, k] < MaxInt then

di := P[i, k];

if P[j, k] < MaxInt then

dj := P[j, k];

if di > dj then

begin

if dj > maj then

begin

maj := dj;

end;

end

else

begin

if di > mai then

begin

mai := di;

end;

end;

end;

dist := (mai + D[i, j] + maj) / 2;

if (dist < mima) and (dist — mai > 0) and

(dist < mai + D[i, j]) then

begin

mima := dist;

Str (j, s);

s1 := 'Абсолютный центр между вершинами ' + s;

Str (i, s);

s1 := s1 + ' и ' + s + ' на расстоянии от ' + s

+ ' равном ';

Str ((dist — mai):3:1, s);

WriteLn (f, s1 + s);

end;

end;

end;

end.

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

//главный интерфейсный модуль

unit U1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ImgList, ComCtrls, ToolWin, Math, ExtCtrls, XPMan, Menus,

ArrowCha, TeEngine, Series, TeeProcs, Chart;

type

TForm1 = class (TForm)

ToolBar1: TToolBar;

Graf: TToolButton;

Metrical: TToolButton;

Vyhod: TToolButton;

ImageList1: TImageList;

ToolButton1: TToolButton;

Chart1: TChart;

Series2: TPointSeries;

Series1: TArrowSeries;

procedure GrafClick (Sender: TObject);

procedure VyhodClick (Sender: TObject);

procedure FormShow (Sender: TObject);

procedure MetricalClick (Sender: TObject);

procedure Grafdraw (Sender: TObject);

procedure Params (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

uses U2, U3, UCalc, U4;

{$R *.dfm}

procedure TForm1. Grafdraw (Sender: TObject);

//построение графа

var

R, k, N, i, j: integer;

x, y: array [1.100] of integer;

v: matrica;

begin

N := Form2. SpinEdit1.Value;

R := 100;

for i := 1 to N do

if Odd (i) then

begin

x[i] := 125 + Round (R * Cos ((i — 1) * 2 * PI / N));

y[i] := 125 — Round (R * Sin ((i — 1) * 2 * PI / N));

end

else

begin

x[i] := 125 + Round (0.7 * R * Cos ((i — 1) * 2 * PI / N));

y[i] := 125 — Round (0.7 * R * Sin ((i — 1) * 2 * PI / N));

end;

Chart1.Series[0]. Clear;

Chart1.Series[1].Clear;

for i := 1 to n do

Series2.AddXY (X[i], Y[i], IntToStr (i));

// вывод циклов

for i := 1 to n do

for j := 1 to N do

begin

Val (Form2.StringGrid1.Cells[j, i], v[i, j], k);

if v[i, j] <> 0 then

Series1.AddArrow (X[i], Y[i], X[j], Y[j]);

end;

end;

procedure TForm1. GrafClick (Sender: TObject);

//ввод исходных данных

begin

Form2.ShowModal;

Grafdraw (Sender);

end;

procedure TForm1. VyhodClick (Sender: TObject);

//выход из программы

begin

Close;

end;

procedure TForm1. FormShow (Sender: TObject);

//загрузка тестового примера

const

p1: array [1.12,1.12] of integer =

((0, 4, 0,7,2,5, 0,0,0, 0, 6, 0), {a}

(4, 0,20,0,0,7, 0,0,3, 0,10, 0), {b}

(0,20, 0,0,0,8, 2,0,0, 0,14, 0), {c}

(7, 0, 0,0,8,0, 0,2,0, 0, 0, 0), {d}

(2, 0, 0,0,0,0, 0,6,0, 6, 0, 0), {e}

(5, 7, 8,0,0,0,11,0,0, 0, 0, 0), {f}

(0, 0, 0,0,0,0, 0,0,0,12, 0, 2), {g}

(0, 0, 0,0,0,0, 0,0,3, 0, 0, 9), {h}

(0, 3, 0,0,0,3, 0,0,0, 8, 0, 3), {i}

(0, 0, 0,0,0,0, 0,0,0, 0, 0,15), {j}

(6,10,14,0,0,0, 0,0,0, 0, 0, 0), {s}

(0, 0, 0,0,0,0, 2,9,3,15, 0, 0)); {t}

var

n, i, j: integer;

begin

n := 12;

for i := 1 to n do

begin

for j := 1 to n do

Form2.StringGrid1.Cells[j, i] := IntToStr (p1[i, j]);

Form2.StringGrid1.Cells[0, i] := IntToStr (i);

Form2.StringGrid1.Cells[i, 0] := IntToStr (i);

end;

Grafdraw (Sender);

end;

procedure TForm1. MetricalClick (Sender: TObject);

//расчет метрических характеристик

var

Duv, //матрица кратчайших расстояний

Mg: Matrica; //матрица смежности графа

eu: Vector; //эксцентриситеты

R, //радиус графа

D, //диаметр графа

j, i, //счетчики

N: integer; //число вершин

begin

AssignFile (f, 'mh'); Rewrite (f);