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

Результат выполнения данной последовательности операций по подготовке исходных данных будет иметь следующий вид (рис.2.5.2).

Рис.2.5.2 Исходные данные для изображения неориентированного графа

Для записи текста программы изображения структуры неориентированного графа, удобно создать новый модуль, для чего необходимо выполнить в редакторе VBA операцию главного меню: Insert (Вставка) / Module (Модуль). В результате выполнения этой операции в редакторе Visual Basic появится рабочее окно с пустым содержимым созданного модуля, которому по умолчанию будет присвоено имя Module 2. В созданный модуль введем следующий текст, программы оформленной в виде отдельной подпрограммы с именем GraphPainter без выходных параметров или аргументов (листинг2.5.2).



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

Во-первых, при спецификации переменных и массивов следует для данной программы задавать количество вершин графа, указывая его после знака равенства константы N, которая служит в последующем для управления циклами. Все массивы задаются явно, при этом указывается также их тип данных. Массив Vert(N) предназначен для задания и хранения графической информации о вершинах графа, а переменная Sh--для создания изображения ребер графа. Тип данных Shape указывает на способ изображения графа не в форме диаграммы MS Excel, а в форме рисунка формата MS Office System. Массив Dis (N, N) служит для хранения значений смежности или весов ребер, а массивы Xvert (N) и Xvert(N) --- для хранения значений горизонтальных и вертикальных координат вершин исходного графа.

Далее следует блок операторов,которые выполняют чтение данных из рабочего листа Изображение графа (рис.2.5.2), который должен быть активным для работы данной программы. Обращение к ячейкам осуществляется с помощью свойства Cells объекта ActiveSheet.при этом в языке VBA принадлежность свойств и методов объекту указывается через точку в форме: ActiveSheet.Cells. Соответствующее свойство Cells является массивом, что позволяет обращаться к его значениям поэлементно. После ввода и формирования матрицы смежности следует операторы, которые изображают вершины исходного графа в форме кружков, внутри которых помещаются номера этих вершин. Поскольку общее число вершин равно N, данную операцию удобно реализовать в цикле, который выполняется N раз. Для изображения вершины в форме небольшого круга предназначен оператор: Set Vert(I) =ActiveSheet.Shapes.AddShape (msoShapeOval, Xvert(I), Yvert(I) + 60,16,16, который добавляет на рабочий лист объект Vert(I) типа графической формы, а сама форма круга указывается константой msoShapeOval. Размещение вершины происходит в точке с координатами Xvert(I), Yvert(I) + 60,при этом значение второй координаты подбирается опытным путем посредством изменения некоторого целочисленного значения, в данном случае--это число 60. Величина круга также подбирается пользователем и устанавливается с помощью двух чисел, каждое из которых равно 16.

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

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

Sh = ActiveSheet.Shapes.AddConnector(msConnectorStraight,0,0,0,0)

в котором специальная константа msConnectorStraight специфицирует связь в форме отрезка прямой линии. После создания линии связи устанавливаются ее начало Vert(I) и конец Vert(J). Mетод RerouteConnections определяет способ изображения связи как кратчайшую линию от начальной вершины к конечной.

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

Set Sh = ActiveSheet.Shapes.AddLabel(msoTextOrientationHorisontal, (Xvert (I)+Xvert(J))/2-5, (Yvert (I)+Yvert(J))/2+60,60,150)

Если две вершины расположены на одной вертикали, и оператор

Set Sh = ActiveSheet.Shapes.AddLabel(msoTextOrientationHorisontal, (Xvert (I)+Xvert(J))/2, (Yvert (I)+Yvert(J))/2+50,60,150)

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

Sh.TextFrame. Characters. Text = CStr(Dis(I,J)),а размер шрифта устанавливается оператором:

Sh.TextFrame. Characters. Font. Size = 12

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

Set Vert(I) =ActiveSheet.Shapes.AddShape (msoShapeRectangle, 200, 380, 200, 20)

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

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

После написания текста программы она может быть запущена непосредственно из редактора Visual Basic, для чего следует выполнить операцию главного меню:Run / Run,нажать функциональную клавишу <F5> или соответствующую кнопку на главной панели инструментов редактора.

Запуск подпрограмм из рабочего листа MS Excel так же, как запуск макросов в общем случае, может быть выполнен с помощью специального диалогового окна программы MS Excel которая вызывается посредством выполнения операции главного меню: Сервис/Макрос/Макросы или нажатия комбинацию клавиш:<Alt>+<F5>(рис.2.5.2).

Рис.2.5.2 Диалоговое окно запуска подпрограммы или макроса

В этом окне следует выбрать подпрограмму GraphPainter и нажать кнопку ОК. Если текст программы не содержит ошибок, то она будет выполнена, и на данном рабочем листе появиться рисунок с изображением структуры исходного графа (рис.2.5.3)

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

Листинг 2.5.2 Программа изображения структуры неориентированного графа

Public Sub GraphPainter ()

`----- Спецификация переменных и массивов

Const N = 7' количество вершин графа

Dim I, J As Integer

Dim Vert(N), Sh As Shape

Dim Dis(N, N) Xvert(N), Yvert(N) As Integer

`----- Ввод и формирование матрицы смежности

For I =1 To N

Xvert (I,)= ActiveSheet.Cells(I+2, N+2)

Yvert (I,)= ActiveSheet.Cells(I+2, N+3)

For J =1 To N

Dis (I, J)= ActiveSheet.Cells(I+2, J+1)

Next J

Next I

` -----Изображение вершин графа

For I= 1 To N

Set Vert(I) =ActiveSheet.Shapes.AddShape (msoShapeOval, Xvert(I), Yvert(I) + 60,16,16)

Vert(I). TextFrame.Characters.Text = Cstr(I)

Vert(I). TextFrame.Characters.Font.Size = 10

Vert(I). TextFrame.Characters. Font.Bold = True

Next I

-- Изображение ребер графа

For I= 1 To N-1

For J= I+1 To N

If Dis (I, J)<> 0 Then `--- изображаем только те ребра, для которых связь не равна 0

Set Sh = ActiveSheet.Shapes.AddConnector(msConnectorStraight,0,0,0,0)

With Sh. ConnectorFormat

.BeginConnect ConnectedShape:=Vert(I), ConnectionSite: =1

EndConnect ConnectedShape: = Vert(J), ConnectionSite: =1

Sh.RerouteConnections

End With

`--Изображение веса рядом с соответствующим ребром

If Xvert (I)= Xvert(J) Then'--две вершины расположены на одной вертикали

Set Sh = ActiveSheet.Shapes.AddLabel(msoTextOrientationHorisontal, (Xvert (I)+Xvert(J))/2-5, (Yvert (I)+Yvert(J))/2+60,60,150)

Else'---- Две вершины не расположены на одной вертикали

Set Sh = ActiveSheet.Shapes.AddLabel(msoTextOrientationHorisontal, (Xvert (I)+Xvert(J))/2, (Yvert (I)+Yvert(J))/2+50,60,150)

End If

Sh.TextFrame. Characters. Text = CStr(Dis(I,J))

Sh.TextFrame. Characters. Font. Size = 12

End If

Next J

Next I

`--Изображение подписи под рисунком

Set Vert(I) =ActiveSheet.Shapes.AddShape (msoShapeRectangle, 200, 380, 200, 20)

Sh. TextFrame.Characters.Text = “Изображение исходного графа”

Sh. TextFrame.Characters. Font. Size = 11

Sh. TextFrame.Characters. Font. Bold =True

Sh. TextFrame. HorizontalAlignment = x1HAlignCenter

Sh. TextFrame. VerticaleAlignment = x1VAlignCenter

End Sub.

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

Public Sub MaxTreePainter()

`--Спецификация переменных и массивов

Const N = 7'--это количество вершин графа

Dim I, J, K, Im ,Jm, YSdving, Rec As Integer

Dis S As String

Dim Vert(N), Sh As Shape

Dim Dis (N,N), Tree (N, N), Xvert (N,N), Yvert(N,N), Vlink (N) As Integer

YSdvig = 60 `--это сдвиг рисунка по вертикали

`--Ввод и формирование матрицы смежности

For I =1 To N

Xvert(I) = ActiveSheet.Cells(I + 2, N + 2)

Yvert(I) = ActiveSheet.Cells(I + 2, N + 3)

For I =1 To N

Dis (I,J) = ActiveSheet.Cells(I + 2,J + 1)

Next J

Next I

`--Подготовка исходных массивов

For I =1 To N

Vlink(I) = 0 `<--этот массив хранит номера вершин, добавляемых к дереву

For I =1 To N

Tree (I, J) = 0 ` этот массив хранит структуру оптимального дерева

Next J

Next I

K = 1

Vlink(1) = 1

`Нахождение ребра с минимальным весом

While K <= N

Rec = 0

For I =1 To N

For J =1 To N

If Dis (I,J)<>0 And Rec <Dis (I, J) And Vlink (I)=1 And Vlink (J)=0 Then

Rec = Dis (I,J)

Im = I

Jm = J

End If

Next J

Next I

`--Добавление найденной вершины к покрывающему дереву

Vlink (Jm)=1

Tree (Im, Jm) = 1

Tree (Jm, Im) = 1

K = K+1

Wend

`--Расчет значения суммы весов ребер оптимального дерева и структуры дерева

Rec = 0

K = 0

For I =1 To N-1

For J = 1+1 To N

If Tree (I, J) = 1 Then

K = K+1

Rec = Rec + Dis (I,J)

End If

Next J

Next I

S = “Максимальное покрывающее дерево:”+ S+” Fmin = “ + CStr (Rec)

`--Изображение вершин графа

For I =1 To N

Set Vert(I)= ActiveSheet Shapes. AddShape(msShapeOval, Xvert (I), Yvert(I)+Ysdvig,16, 16 )

Vert(I). TextFrame.Characters.Text = CStr(I)

Vert(I). TextFrame.Characters.Font.Size = 10

Vert(I). TextFrame.Characters.Font.Bold = True

Next I

`--Изображение ребер графа

For I =1 To N-1

For J = 1+1 To N

If Tree (I, J) <>0 Then `--изображаем только те ребра, для которых связь не равна 0

Set Sh = ActiveSheet Shapes. AddConnector(msConnectorStraight, 0, 0, 0, 0)

With Sh. ConnectorFormat

BeginConnect ConnectedShape:= Vert(I), ConnectionSite:=1

EndConnect ConnectedShape:= Vert(J), ConnectionSite:=1

Sh.RerouteConnections

End With

`--Изображение веса рядом с соответствующим ребром

If Xvert (I)= Yvert(J)Then `--две вершины расположены на одной вертикали

Set Sh = ActiveSheet Shapes. AddLabel (msTextOrientationHorizontal, Xvert (I)+Yvert(J))/2-5,( Xvert (I)+ Yvert(J))/2+Ysdvig, 60,150)

Else `--две вершины не расположены на одной вертикали

Set Sh = ActiveSheet Shapes. AddLabel (msTextOrientationHorizontal, Xvert (I)+Yvert(J))/2-5,( Xvert (I)+ Yvert(J))/2+Ysdvig, 10, 60,150)

End If

Sh.TextFrame.Characters.Text = CStr(Dis(I,J))

Sh. TextFrame.Characters.Font.Size = 12

End If

Next J

Next I

`--Изображение подписи под рисунком

Set Sh= ActiveSheet Shapes. AddShape(msShapeRectangle, 150,380,300,20)

Sh .TextFrame.Characters.Text = S

Sh.TextFrame.Characters.Font.Size = 11

Sh. TextFrame.Characters.Font.Bold = True

Sh. TextFrame. HorizontalAlignment = x1HaAlignCenter

Sh. TextFrame.VerticalAlignment = x1VAAlignCenter

End Sub

Microsoft Excel 10.0 Отчет по результатам

Рабочий лист: [макспот.xls]Максимальный поток

Отчет создан: 27.04.2006 11:33:40

Целевая ячейка (Максимум)

Ячейка Имя Исходное значение Результат

$F$2 Значение ЦФ: 11 11

Изменяемые ячейки

Ячейка Имя Исходное значение Результат

$D$2 Переменные: 6 6

$D$3 Переменные: 5 5

$D$4 Переменные: 1 3

$D$5 Переменные: 4 0

$D$6 Переменные: 1 3

$D$7 Переменные: 5 5

$D$8 Переменные: 0 0

$D$9 Переменные: 4 0

$D$10 Переменные: 6 8

$D$11 Переменные: 5 3

Ограничения

Ячейка Имя Значение Формула Статус Разница

$E$2 Ограничения: 5,9206E-12 $E$2=0 не связан. 0

$E$3 Ограничения: -8,88178E-12 $E$3=0 не связан. 0

$E$4 Ограничения: 0 $E$4=0 не связан. 0

$E$5 Ограничения: 5,9206E-12 $E$5=0 не связан. 0

$E$6 Ограничения: 5,32907E-12 $E$6=0 не связан. 0

$E$7 Ограничения: 0 $E$7=0 не связан. 0

$E$8 Ограничения: 0 $E$8=0 не связан. 0

$E$9 Ограничения: 0 $E$9=0 не связан. 0

$E$10 Ограничения: 0 $E$10=0 не связан. 0

$E$11 Ограничения: 0 $E$11=0 не связан. 0

$D$2 Переменные: 6 $D$2<=$C$2 связанное 0

$D$2 Переменные: 6 $D$2=целое связанное 0

$D$3 Переменные: 5 $D$3=целое связанное 0

$D$4 Переменные: 3 $D$4=целое связанное 0

$D$5 Переменные: 0 $D$5=целое связанное 0

$D$6 Переменные: 3 $D$6=целое связанное 0

$D$7 Переменные: 5 $D$7=целое связанное 0

$D$8 Переменные: 0 $D$8=целое связанное 0

$D$9 Переменные: 0 $D$9=целое связанное 0

$D$10 Переменные: 8 $D$10=целое связанное 0

$D$11 Переменные: 3 $D$11=целое связанное 0

$D$3 Переменные: 5 $D$3<=$C$3 связанное 0

$D$4 Переменные: 3 $D$4<=$C$4 не связан. 10

$D$5 Переменные: 0 $D$5<=$C$5 не связан. 4

$D$6 Переменные: 3 $D$6<=$C$6 не связан. 4

$D$6 Переменные: 3 $D$6<=$C$6 не связан. 4

$D$7 Переменные: 5 $D$7<=$C$7 не связан. 4

$D$8 Переменные: 0 $D$8<=$C$8 не связан. 11

$D$9 Переменные: 0 $D$9<=$C$9 не связан. 4

$D$10 Переменные: 8 $D$10<=$C$10 связанное 0

$D$11 Переменные: 3 $D$11<=$C$11 не связан. 2

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