Нахождение всех гамильтоновых циклов заданного графа

Алгоритм и исходный код программы.

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

Рис. 6: Внешний вид программы.

Программа «Вычисление цикломатического числа» позволяет выполнять следующие действия:

1. с вершинами графа:

а) рисовать вершины;

б) переименовывать вершины;

в) перемещать вершины;

г) удалять вершины;        Рис. 7.

2) с ребрами графа:

а) рисовать ребра;

б) создавать ребра вручную при помощи специального диалога;

в) добавлять ребра при помощи матрицы смежности;

г) удалять ребра;        Рис. 8. 

3) экспортировать изображение графа в файл с расширением *.bmp.

4) просмотреть все вершин, а так же определить их количество  по списку вершин (левая часть  программы);

5) рассчитать цикломатическое  число графа;

6) просмотреть матрицу  смежности.

 

 

 

Рис. 9.

Доступ к вышеперечисленным действиям осуществляется двумя способами:

1) главное меню:

 

Рис. 10.

 

 

2) дополнительное меню, вызываемое правой клавишей мыши.

 

 

 

 

 

Рис. 11.

Примеры расчета цикломатического числа графа:

 

 

 

 

 

 

 

 

Рис. 12.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 13.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 14.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 15.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 16.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 17.

 

Рис. 18. 

 

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

 

 

 

Приложение 1.

 

Исходный код главной формы.

 

unit Unit1;

interface

uses

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

  Dialogs, StdCtrls, ExtCtrls, unit2, ComCtrls, Menus, XPMan, unit3;

type

  TForm1 = class(TForm)

    Panel1: TPanel;

    ListBox1: TListBox;

    Label1: TLabel;

    Button1: TButton;

    Button2: TButton;

    Timer1: TTimer;

gCanv: TImage;

    Label2: TLabel;

    StatusBar1: TStatusBar;

PopupMenuPoleIMG: TPopupMenu;

    N1: TMenuItem;

    N2: TMenuItem;

    N3: TMenuItem;

    N4: TMenuItem;

    N5: TMenuItem;

    N6: TMenuItem;

    N7: TMenuItem;

    SaveDialog1: TSaveDialog;

    PopupMenu1: TPopupMenu;

    N8: TMenuItem;

    N9: TMenuItem;

    N10: TMenuItem;

    N11: TMenuItem;

    N12: TMenuItem;

    MainMenu1: TMainMenu;

    N13: TMenuItem;

    N14: TMenuItem;

    N15: TMenuItem;

    N16: TMenuItem;

    N17: TMenuItem;

    N18: TMenuItem;

    N19: TMenuItem;

   N20: TMenuItem;

    N21: TMenuItem;

    N22: TMenuItem;

procedure Button1Click(Sender: TObject);

procedure Timer1Timer(Sender: TObject);

proceduregCanvMouseDown(Sender: TObject; Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

procedure N1Click(Sender: TObject);

procedureFormCreate(Sender: TObject);

proceduregCanvMouseMove(Sender: TObject; Shift: TShiftState; X,

      Y: Integer);

proceduregCanvMouseUp(Sender: TObject; Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

procedure N2Click(Sender: TObject);

procedure ListBox1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure N7Click(Sender: TObject);

procedure N8Click(Sender: TObject);

procedure N10Click(Sender: TObject);

procedure N5Click(Sender: TObject);

procedure N12Click(Sender: TObject);

procedure N15Click(Sender: TObject);

procedure N16Click(Sender: TObject);

procedure N17Click(Sender: TObject);

procedure N18Click(Sender: TObject);

procedure N22Click(Sender: TObject);

procedure N19Click(Sender: TObject);

procedure N20Click(Sender: TObject);

procedure N21Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

procedurepaint_system_vertex;{Процедураотрисовкивершин}

procedurepaint_system_ridge;{Процедураотрисовкиребер}

procedurepaint_system_graph; {Общаяпроцедураотрисовкивсегоизображения}

end;

const

vertex_count=99; {Максимальноеколличество  вершин}

ridge_color=$00AAFF; {Цветребер}

vertex_select_color=$FF0000; {цвет выделенной  вершины}

vertex_color=$FFFF00; {Цвет остальных (не выделенных) вершин}

background_color=$FFFFFF; {Цветфона}

text_color=$000000; {Цветтекста}

var

  Form1: TForm1;

mpress:boolean=false; {Регистрируем  нажатие левой кнопки мыши, этот  метод пригодится в процедурах, которые не определяют состояние  мышки}

vertex_select:integer=-1; {В данную переменную вносится номер выделенной вершины, если ничего не выделенно, то вносится -1}

vertex_list:array[0..vertex_count] oftpoint; {список  вершин, от 0 до максимального колличества. Тип данных - запись в виде координат  вершины на холсте (canvas) }

vertex_list_mass:array[0..vertex_count] ofstring; {Массив, так де имеет размер  от 0 до максимального колличества  разрешенных вершин.Вносятся наименования  точек}

vertex_add:boolean=false; {Тут отслеживаем, можно ли добавлять вершину.В дополнительном меню, в переменную записывается true, что бы в дальнейшем (при нажатии левой клавиши мыши) мы добавили вершины}

vertex_moves:integer=-1; {Изначально, при  работе с вершинами переменная=-1, и если мы начинаем перемещать  мышку с зажатой левой кнопкой, сюда вносится номер перемещаемой вершины.Сделано для того, что бы программа не запуталась, что именно ей надо перетащить}

massiv_of_connectivity:array[0..vertex_count,0..vertex_count] ofinteger; {Эта двухмерная матрица  сделана для того, что бы при отрисовки изображения отследить существование ребер от вершины к вершине}

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

ridge_add:boolean=false; {Как и в  случае с вершинами, программе  надо указать, можно ли добавлять  ребро или нет.Данная переменная  это сообщит программе}

ridge_add_1:integer=-1; {Тут вносится  номер первой вершины.А если  она не выбрана или ребра  не добавляются, в  переменной записана "-1"}

ridge_add_2:integer=-1;  {Тут вносится  номер второй вершины.Так же  если она не выбрана или  ребра не добавляются, в  переменной  записана "-1"}

implementation

{Теперь приступим к  самому главному, описанию тела  нашей программы}

uses unit4;

{$R *.dfm}

 

procedure TForm1.paint_system_ridge; {Эта  процедура рисует на картинке  ребра}

varms_i,ms_j:integer; {Для пересчета  всех позиций матрицы, объявляем  переменные}

begin

gCanv.Canvas.Pen.Color:= ridge_color; {Указываем  цвет ребер}

forms_i:=0 to ListBox1.Items.Count-1 do {При помощи двух циклов, мы проверяем - можно ли рисовать ребро}

forms_j:=0 to ListBox1.Items.Count-1 do

begin

ifmassiv_of_connectivity[ms_i, ms_j]=1 then {Ребро  разрешается рисовать лишь в  том случае, если в матрице  по искомым вершинам стоит единица.Но если стоит ноль, то рисование не допускается}

begin

gCanv.Canvas.MoveTo(vertex_list[ms_i].X+10, vertex_list[ms_i].Y+10);

gCanv.Canvas.LineTo(vertex_list[ms_j].X+10, vertex_list[ms_j].Y+10);

end;

end;

gCanv.Canvas.Pen.Color:= vertex_color;  {Возвращаемизмененныйцветлинийобратно}

end;

procedure TForm1.paint_system_vertex;

var

i:integer;

begin

for i:=0 to ListBox1.Items.Count-1 do

begin

ifstrtoint(vertex_list_mass[i])>-1 then

begin

ifi=vertex_select then gCanv.Canvas.Brush.Color := vertex_select_color else gCanv.Canvas.Brush.Color := vertex_color;

gCanv.Canvas.Rectangle(vertex_list[i].x,vertex_list[i].y,vertex_list[i].x+20,vertex_list[i].y+20);

gCanv.Canvas.Brush.Color:=background_color;

gCanv.Canvas.TextOut(vertex_list[i].x-(gCanv.Canvas.TextWidth(vertex_list_mass[i]) div 2)+10,vertex_list[i].y-15,vertex_list_mass[i]);

end;

end;

end;

procedure TForm1.paint_system_graph;

begin

gCanv.Canvas.Font.Color:=text_color;

gCanv.Canvas.Brush.Color := background_color;

gCanv.Canvas.Pen.Color:= vertex_color;

gCanv.Canvas.FillRect(gCanv.Canvas.ClipRect);

gCanv.Canvas.Pen.Width:=3;

paint_system_ridge;

paint_system_vertex;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

graph_index:integer;

begin

if Form2.ShowModal>=2 then

begin

if (Form2.Edit1.Text<>'') and (Form2.Edit2.Text<>'') then

begin

if Form2.Edit1.Text=Form2.Edit2.Text then

begin

Label2.Caption:='Номера графов  не должны совпадать';

Label2.Show;

end

else

begin

ifstrtoint(Form2.Edit1.Text)<=ListBox1.Items.Count-1 then

ifstrtoint(Form2.Edit2.Text)<=ListBox1.Items.Count-1 then

massiv_of_connectivity[strtoint(Form2.Edit1.Text),strtoint(Form2.Edit2.Text)]:=1;

///*

end;

end else begin

Label2.Caption:='Формазаполненнанекоректно';

Label2.Show;

end;

end;

Form2.Edit1.Text:='';

Form2.Edit2.Text:='';

paint_system_graph;

end;

procedure TForm1.Timer1Timer(Sender: TObject);

begin

Label2.Hide;

end;

procedure TForm1.gCanvMouseDown(Sender: TObject; Button: TMouseButton;

  Shift: TShiftState; X, Y: Integer);

labelst_ridge;

begin

ifvertex_moves<>-1 then

begin

mpress:=true;

vertex_select:=vertex_moves;

ListBox1.ItemIndex:=vertex_select;

end;

if Button=mbLeft then

begin

ifvertex_add=true then

begin

if Form3.ShowModal>=2 then

begin

vertex_list[ListBox1.Items.Count].X:=X-10;

vertex_list[ListBox1.Items.Count].Y:=Y-10;

vertex_list_mass[ListBox1.Count]:=Form3.Edit1.Text;

if Form3.Edit1.Text='' then vertex_list_mass[ListBox1.Count]:=inttostr(ListBox1.Count);

ListBox1.Items.Add('Вершина   -   '+inttostr(ListBox1.Items.Count)+'   =   '+vertex_list_mass[ListBox1.Count]);

vertex_add:=false;

Form3.Edit1.Text:='';

end;

end;

ifridge_add=true then

begin

if (ridge_add_1=-1) and (ridge_add_2=-1) then

begin

ridge_add_1:=vertex_select;

gotost_ridge;

end;

if (ridge_add_1<>-1) and (ridge_add_2=-1) then

begin

ridge_add_2:=vertex_select;

end;

st_ridge:

if (ridge_add_1<>-1) and (ridge_add_2<>-1) then

begin

massiv_of_connectivity[ridge_add_1, ridge_add_2]:=1;

ridge_add_1:=-1;

ridge_add_2:=-1;

ridge_add:=false;

end;

end;

end;

paint_system_graph;

end;

procedure TForm1.N20Click(Sender: TObject);

begin

Form2.Button1.Caption:='Удалить';

if Form2.ShowModal>=2 then

begin

massiv_of_connectivity[strtoint(form2.Edit1.Text),strtoint(form2.Edit2.Text)]:=0;

massiv_of_connectivity[strtoint(form2.Edit2.Text),strtoint(form2.Edit1.Text)]:=0;

end;

paint_system_graph;

end;

procedure TForm1.N1Click(Sender: TObject);

begin

ridge_add:=false;

vertex_add:=true;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

paint_system_graph;

end;

procedure TForm1.gCanvMouseMove(Sender: TObject; Shift: TShiftState; X,

  Y: Integer);

var i:integer;

begin

if (mpress=true) then

begin