Московский Авиационный
Институт
(Государственный
Технический Университет)
филиал «Восход»
Кафедра
МиПОИС
Лабораторная
работа
по
дискретной математике
«Графическое
представление графа»
(отчет)
Преподаватель ____________
/Крохина Н.В./
Студент группы ДМ 2-26 ___________
/Толоконников А.В./
г.
Байконур
2002 г.
1. Задача
Составить
алгоритм перехода к графическому представлению для неориентированного графа и
реализовать его программным путем, если граф задан матрицей смежностей.
2. Алгоритм решения,
поставленной задачи
1)
Вводится
количество вершин неориентированного графа.
2)
Если
количество вершин больше 7, то переходим к пункту 3; иначе переходим к пункту
4.
3)
Генератором
случайных чисел произвольно задаются связи между вершинами в матрице
смежностей, переходим к пункту 5.
4)
Вводятся
связи между вершинами, исходя из следующего условия: не существует пути длиной
в одно ребро из одной вершины в другую – ставим «0», существует путь между
двумя вершинами длиной в одно ребро – ставим «1», существует путь из вершины в
саму себя – ставим «2». Все введенные данные заносятся в матрице смежностей.
5)
В
зависимости от количества введенных вершин производится разбиение экрана на N секторов относительно центра
экрана.
6)
На граничных
линиях секторов на одинаковом удалении от центра экрана выводим вершины.
7)
Производим
чтение из матрицы смежностей. Если связь между вершинами есть, то выводим на
экран отрезок, соединяющий одну вершину с другой, если связи нет - рассматриваем
следующую связь. Если связь циклическая изменяем цвет вершины с зеленого на
коричневый.
3. Распечатка
программы решения задачи
Program Graphs;
Uses Crt,
Graph;
Const
M=25;
{Предельное число вершин графа}
R=200;
{Радиус окружности, на которой лежат вершины (центры окружностей)}
Type
Koor = Record
X,Y: Integer
End;
MasKoor = Array[1..M] Of Koor;
Smezno = Array[1..M,1..M] of Integer;
Var
Driver, Mode,
N,I,J:
Integer; {Количество вершин
графа}
A: MasKoor;
B: Smezno;
Procedure
Koordinata; {Процедура задания координат вершин в зависимости от количества
секторов}
Var
Q,W:
Real;
Begin
Writeln('Введите
количество вершин графа: ');
Readln(N);
If N>M Then Halt;
Q:=6.28/N;
{Задание
координат вершин графа}
For I:=1 To N Do
Begin
W:=I*Q;
A[I].X:=300+Trunc(R*cos(W));
A[I].Y:=235+Trunc(R*sin(W));
End
End;
Procedure Vivod; {Вывод
вершин
графа
на
экран
монитора}
Begin
For I:=1 To N Do
Begin
SetBkColor(0);
SetColor(2);
For J:=1 To 10 Do
Circle(A[I].X,A[I].Y,J)
End
End;
Procedure Smegnost; {Процедура
задания
матрицы
смежностей}
Begin
For I:=1 To N Do
For J:=1 To N Do
B[I,J]:=9;
If N>7 Then
For I:=1 To N Do
For J:=1 To N Do
B[I,J]:=Random(3)
else
Begin
For I:=1 To N Do
For J:=1 To N Do
If B[I,J]=9 Then
Begin
Write('Введите
связь
[',I,',',J,']:= ');
Readln(B[I,J]);
B[J,I]:=B[I,J]
End
Else Writeln('Cвязь
[',I,',',J,']:= ',B[I,J]);
End
End;
Procedure Linia;
Var K: Integer;
Begin
For I:=1 To N Do
For J:=1 To N Do
If (I=J) And (B[I,J]=2) Then {Циклическая
связь}
Begin
SetColor(Brown);
For K:=1 To 10 Do
Circle(A[I].X,A[I].Y,K)
End else
If B[I,J]=1 Then {Обычная
связь}
Begin
SetColor(Red);
Line(A[I].X,A[I].Y,A[J].X,A[J].Y)
End
End;
{------------------------------------------------------------------}
Begin
ClrScr;
WriteLn('Вывод изображения
графа на экран монитора');
Koordinata;
Smegnost;
Readln; {Задержка
экрана}
Driver:=Detect;
InitGraph(Driver,Mode,'Egavga.bgi'); {Подключение
графического
режима}
Vivod;
Linia;
Readln;
Closegraph;
{Отключение графического режима}
End.
неориентированный
граф вершина матрица
4. Результаты работы
программы для числа вершин равного 6
Матрица
смежностей вершин |
|
A |
B |
C |
D |
E |
F |
A |
0 |
0 |
1 |
0 |
0 |
1 |
B |
0 |
0 |
1 |
1 |
0 |
1 |
C |
0 |
1 |
0 |
0 |
1 |
1 |
D |
1 |
0 |
1 |
2 |
1 |
0 |
E |
0 |
0 |
1 |
0 |
2 |
0 |
F |
1 |
0 |
1 |
0 |
1 |
2 |
Другие работы по теме:
Графы Основные понятия
Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 1 Графы. Основные понятия
Решение нелинейных уравнений
Задание №1 Отделить корни уравнения графически и уточнить один из них: методом половинного деления; методом хорд; методом касательных; методом секущих;
Статистическое изучение вариации
Содержание Введение……………………………………………………………………….…..3 1. Понятие вариации и её значение…………………………………….………. .5 2. Характеристика закономерности рядов распределения и графическое изображение вариационного ряда……………………………………….………7
Тупейный художник
Автор: Лесков Николай. Рассказ этот автор слышит от няни своего младшего брата Любови Онисимовны, в прошлом красавицы актрисы орловского театра графа Каменского. На Троицу она водит автора на кладбище, где у простой могилы рассказывает историю «тупейного художника» Аркадия.
Александр Комин, граф Бюшан
Александр Комин (англ. Alexander Comyn, умер 1289), граф Бюшан. Он был англо-шотландским бароном и одной из наиболее важных фигур в истории Шотландии XIII века. Он был сыном Уильяма Комина, по праву жены (jure uxoris) графа Бюшана, и Марджори, графини Бюшан, наследницы последнего кельтского графа Бюшана, Фергюса.
Панин, Никита Петрович
Ники́та Петро́вич Па́нин (1770(1770)—1837) — русский дипломат, граф. Сын графа Петра Ивановича Панина и отец Виктора Никитича Панина.
Род Перси
Введение 1 1-й род Перси 2 2-й род Перси 3 3-й род Перси 5 Библиография Введение Род Перси (англ. Percy) — 3 английских дворянских рода. 1. 1-й род Перси Родоначальник — Вильям де Перси (ум. 1096), 1-й барон Перси соратник Вильгельма Завоевателя в Англию, получил большие владения в графствах Йорк и Линкольн.
Анна Невилл
(англ. Anne Neville, род. 11 июня 1456 года, Уорикский замок — ум. 16 марта 1485 года, Лондон) — королева Англии (1483—1485), супруга короля Ричарда III.
Эдуард Норичский, 2-й герцог Йоркский
и 1-й герцог Омаль (англ. Edward of Norwich, 2nd Duke of York and 1st Duke of Aumale; 1373—1415) — английский вельможа, сын Эдмунда Лэнгли, 1-го герцога Йоркского, внук короля Англии Эдуарда III.
Кемп, Уильям
Уильям Кемп (англ. William Kempe ум. 1603) — английский актёр и танцор. Известен прежде всего исполнением комических ролей в пьесах Шекспира. Считался преемником комика из труппы «слуг её Величества королевы» Ричарда Тарлтона. О ранних годах жизни Кемпа достоверных сведений нет. Считается, что он играл в труппе «слуг графа Лестера» — Кемп участвовал в представлении в доме графа в мае 1585 года, о чём свидетельствует документ о выплате ему вознаграждения.
Изабелла де Эно
Введение 1 Биография 2 Браки и дети Введение Изабелла де Эно (фр. Isabelle de Hainaut, 23 апреля 1170 — 15 марта 1190, Париж, Франция) — королева Франции в 1180 — 1190 годах. Изабелла была дочерью графа Бодуэна V де Геннегау и Маргариты Эльзасской, дочери графа Фландрии Тьерри Эльзасского. В 1180 году Изабелла сочеталась браком с Филиппом II Августом, королём Франции из династии Капетингов.
Дуглас, Маргарита
Маргарита Дуглас (англ. Margaret Douglas; 1515—1578) — дочь Маргариты Тюдор, старшей сестры английского короля Генриха VIII, и её второго мужа Арчибальда Дугласа, графа Ангуса.
Суассон, Людовик де Бурбон
Людовик де Бурбон, граф де Суассон (фр. Louis de Bourbon, comte de Soissons; 1 мая 1604(16040501) — 6 июля 1641) — французский принц крови, единственный сын 1-го графа Суассонского, троюродный брат Людовика XIII.
Адель Шампанская
Адель Шампанская [1] (фр. Adиle de Champagne) (ок. 1140 — 4 июня 1206, Дворец Сите, Париж) — королева Франции (1160 — 1180), регентша Франции (1190 — 1192), дочь Тибо II Великого, графа Шампани и Матильды Каринтийской.
Берта Бургундская
План Введение 1 Биография 2 Браки и дети Список литературы Введение Берта Бургундская (фр. Berthe de Bourgogne, ок. 964 — 16 января 1010) — королева Франции в 997 — 1001 годах. Берта была дочерью Конрада I Тихого, короля Бургундии и Матильды Французской и вдовой графа Эда I де Блуа. В 997 году Берта сочеталась браком с Робертом II Благочестивым, королём Франции из династии Капетингов.
Маргарита Анжуйская
Маргарита Анжуйская (фр. Marguerite d'Anjou, англ. Margaret of Anjou 23 марта 1429 — 25 августа 1482) — королева Англии, дочь Рене I Доброго, графа Анжуйского (1409—1480), троюродного брата французского короля Карла VII.
Суассон, Карл де Бурбон
Шарль де Бурбон, граф Суассонский (фр. Charles de Bourbon-Soissons; 3 ноября 1566(15661103) — 1 ноября 1612) — французский принц крови, младший сын 1-го принца Конде, видный полководец последних Религиозных войн. В разные годы наместничал в Бретани (1589), Дофине (1602) и Нормандии (1610), а также в Новой Франции.
Намюр графство
План Введение 1 История Введение Графство Намюр (фр. Comtй de Namur) — средневековое графство со столицей в Намюре, располагавшееся на территории современной Бельгии.
Генрих II граф Лувена
План Введение 1 Правление 2 Брак и дети Список литературы Введение Генрих II (фр. Henri II de Louvain, нем. Heinrich II von Lцwen, нидерл. Hendrik II van Leuven; около 1020—1078) — граф Лувена и Брюсселя (1062—1078), сын графа Ламберта II, графа Лувена и Брюсселя, и Уды Верденской, дочери Гозело I.
Декларация Бальфура 1926 года
Деклара́ция Ба́льфура 1926 го́да (англ. Balfour Declaration of 1926) — заключительный отчёт конференции стран Британской империи, состоявшейся в 1926 году. Документ получил своё название по имени лорда Артура Бальфура, первого графа Бальфурского.
Генрих III граф Лувена
Генрих III (фр. Henri III de Louvain, нем. Heinrich III von Lцwen, нидерл. Hendrik III van Leuven; до 1078 — февраль или март 1095) — граф Лувена и Брюсселя (1078 — 1095), ландграф Брабанта (с 1085 года), сын графа Генриха II, графа Лувена и Брюсселя, и Аделы, дочери Эберхарда, графа Бетюве.
Кречетников, Пётр Никитич
Пётр Никитич Кречетников (1727 — после 1800) — генерал-майор, Астраханский губернатор. Родился в 1727 году, старший брат генерал-аншефа графа Михаила Кречетникова.
Юлихский дом
Введение 1 История 2 Генеалогия Введение Юлихский дом (нем. Haus Jьlich, нидерл. Huis Gulik) — средневековый знатный род франксого происхождения, представители которого с 1003 года назначались герцогами Нижней Лотарингии графами в Юлихгау.
Генрих Донцель
Генрих Донцель (фр. Henri Donzel) или Генрих Щёголь (фр. Henri Damoiseau, ок. 1035(1035) — 1070/1074) — второй сын герцога Бургундии Роберта I Старого и Элии (Гедвиги) де Семюр, наследник герцогства Бургундия с 1059/1060 года.
Жан Бургундский граф Шароле
Жан Бургундский (фр. Jean de Bourgogne; ок. 1231 — 17 сентября 1267) — сеньор Шароле с 1248, сеньор де Бурбон (по праву жены) с 1267, второй сын герцога Бургундии Гуго IV от первого брака с Иоландой де Дрё, дочерью Роберта III, графа де Дрё и Аэнор, дамы де Сен-Валери.
Гастон Орлеанский
Гастон Жан Батист (фр. Gaston duc d'Orlйans, 25 апреля 1608, Фонтенбло — 2 февраля 1660, Блуа) — герцог Орлеанский, младший сын короля Генриха IV и Марии Медичи.
Ричард, герцог Йоркский
Ричард Плантагенет, 3-й герцог Йоркский (англ. Richard Plantagenet, Duke of York, 21 сентября 1411(14110921) — 30 декабря 1460, Уэйкфилд) — сын Ричарда Конисбурга, 3-го графа Кембриджа, и Анны Мортимер (1388—1411), глава партии Йорков в начале войны Алой и Белой Розы.
Дрого герцог Бретани
Введение 1 Правление 2 Наследство Список литературы Введение Дрого (брет. Drogon) (950(0950)—958) — граф Нанта и герцог Бретани (952—958). Единственный законный сын графа Нанта и герцога Бретани Алена II Кривая Борода и Юдит (Аделаиды) Блуаской, дочери графа Тура Тибо Старого.
Луи-Александр де Бурбон, граф Тулузский
(фр. Louis Alexandre de Bourbon, comte de Toulouse; 6 июня 1678(16780606), Версаль — 1 декабря 1737, замок Рамбуйе). Третий внебрачный сын короля Франции Людовика XIV и Мадам де Монтеспан.
Конрад I герцог Лотарингии
Конрад Рыжий (нем. Konrad der Rote; ок. 910(0910) — 10 августа 955, река Лех) — герцог Лотарингии из Салической (франконской) династии. Сын Вернера V, графа Нахгау, Шпейергау и Вормсгау, и дочери короля Конрада I.
Мария-Тереза Савойская
Мария-Тереза Савойская (фр. Marie Thйrиse de Sardaigne, итал. Maria Teresa di Savoia) (31 января 1756, Турин, Сардинское королевство — 2 июня [1] 1805, Грац, Австрийская империя) — принцесса Сардинская и Пьемонтская, супруга Шарля де Бурбона, графа де Артуа, самого младшего внука короля Франции Людовика XV, который через 19 лет после её смерти стал королём Франции Карлом X.
Разработка программ с использованием динамической памяти
Поиск источников ориентированного графа. Использование динамических структур при работе с графами. Способы представления графов, операции над ними, описание программной реализации. Процедуры и функции языка. Функции работы с динамической памятью, графами.