Если множество вершин графа конечно, то он называется конечным графом. Конечный граф G = (V, Е), содержащий р вершин и q ребер, назывзется (р, q)-гpaфoм.
Пусть V == {v1, v2, …, vp} и Е == {е1, е2, …, eq} — соответственно множества вершин и ребер (р, q)-графа. Каждое ребро ek < Е соединяет пару вершин vi, vj < V, являющихся его концами (граничными вершинами). Для ориентированного ребра (дуги). различают начальную вершину, из которой дуга исходит, и конечную вершину, в которую дуга заходит. Ребро, граничными вершинами которого является одна и та же вершина, называется петлей. Ребра с одинаковыми граничными вершинами являются параллельными и называются кратными. В общем случае граф может содержать и изолированные вершины, которые не являются концами ребер и не связаны ни между собой, ни с другими вершинами.
Число ребер, связанных с вершиной vi (петля учитывается дважды), называют степенью вершины и обозначают через (vi) или deg(vi). Так, для графа на рисунке 2.2, а (v1) == 1, (v2) = 4 и т. д. Очевидно, степень изолированной вершины равна нулю ((v4)= 0). Вершина степени единицы называется концевой или висячей вершиной ((v1) = 1). Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно. В орграфе различают положительные +(vi) и отрицательные -(vi) степени вершин, которые равны соответственно числу исходящих из vi и заходящих в vi дуг. Например, для вершины d орграфа (см. рисунок 2.1, а) имеем +(d) = 2 и —(d) = 3. Очевидно, суммы положительных и отрицательных степеней всех вершин орграфа равны между собой и равны также числу всех дуг.
Граф без петель и кратных ребер называют простым или обыкновенным. Граф без петель, но с кратными ребрами называют мультиграфом. Наиболее общий случай графа, когда допускаются петли и кратные ребра, называют псевдографом. Так, граф на рисунке 2.2, б — это мультиграф, а на рисунке 2.2, а — псевдограф. Если граф не имеет ребер , то все его вершины изолированы, и он называется пустым или нуль-графом. Простой граф, в котором любые две вершины соединены ребром, называется полным (на рисунке 2.2, б приведен пример полного графа с шестью вершинами). Если множество вершин V простого графа допускает такое разбиение на два непересекающихся подмножества V1 и V2 что не существует ребер, соединяющих вершины одного и того же подмножества, то он называется двудольным или би-графом (рисунок 2.2, в). Ориентированный граф считается простым, если он не имеет строго параллельных дуг и петель.
Граф, степени всех вершин которого одинаковы и равны r, называется однородным (регулярным) r-й степени. Полный граф с n вершинами всегда однородный степени n2 — 1, а пустой граф — однородный степени 0. Граф третьей степени называют кубическим. Он обладает рядом интересных свойств и, в частности, всегда имеет четное число вершин.
Часто связи между объектами характеризуются вполне определенной ориентацией. Например, на некоторых улицах допускается только одностороннее автомобильное движение, в соединительных проводах электрической цепи задаются положительные направления токов, отношения между людьми могут определяться подчиненностью или старшинством. Ориентированные связи характеризуют переход системы из одного состояния в другое, результаты встреч между командами в спортивных состязаниях, различные отношения между числами (неравенство, делимость) [2].
Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными ребрами — ориентированным графом или короче орграфом (рисунок 2.1, а).
Если пара вершин соединяется двумя или большим числом дуг, то такие дуги называют параллельными. При этом две дуги, одинаково направленные по отношению к данной вершине, называют строго параллельными, а различно направленные — нестрого параллельными. Ясно, что нестрого параллельные дуги, отображающие ориентацию связи в обоих направлениях, по существу равноценны неориентированной связи и могут быть заменены ребром. Произведя такую замену в орграфе, придем к смешанному графу, который содержит ребра и дуги (рисунок 2.1, б). Обратно, любой неориентированный или смешанный граф можно преобразовать в ориентированный заменой каждого ребра парой нестрого параллельных дуг.
В настоящее время для разработки сложных программных комплексов, каковым является подсистема автоматизированного проектирования ЛВС существует не так много вариантов в выборе языка программирования, их всего три: С, С++ и Basic.
Рассмотрим их по очереди.
Язык С является разработкой 1971 года [3], но тем не менее не теряет актуальности и сейчас из-за своих мощных средств поддержки структурного программирования, актуальных типов данных, наличия большого выбора компиляторов, высокой скорости исполняемого кода и переносимости. Однако, не смотря на свою популярность, данный язык не является объектно-ориентированным и в настоящее время сдал позиции более продвинутому в этом отношении языку С++.
Язык С++ является надмножеством языка С и при определенных условиях поддерживает его как свою составную часть. Его достоинства такие же как и у языка С, при этом он лишен многих его недостатков. В данном языке существует поддержка объектно-ориентированного программирования, что несколько увеличивает размер исходного кода, однако упрощает создание сложных программ. Так же есть возможность вводить свои типы данных и операции над ними, что позволяет реализовать не нем математические модели довольно высокого уровня абстракции [3].
Одним из самых серьёзных достоинств языка следует считать наличие продвинутых средств RAD (RAD – Rapid Application Development – Быстрая разработка приложений) и библиотеки STL (STL – Standard Template Library). Средства RAD позволяют в значительной мере абстрагироваться от рутинной программистской работы и в значительной мере автоматизирует ее, в то время как библиотека STL позволяет пользоваться набором готовых стандартизированных классов, таких как контейнеры, итераторы, словари, хеш-таблицы и т.д.
К недостаткам данного языка следует отнести несколько меньшую, чем у С скорость кода.
Язык Basic существует уже несколько десятков лет и с тех пор не стоит на месте. В настоящее время для этого языка реализованы несколько компиляторов, сотни интерпретаторов, включена поддержка большого списка различных циклов и объектов.
К недостаткам данного языка следует отнести весьма посредственную скорость работы и трудность реализации больших проектов.
Очевидно, для работы над данной системой лучше всего подходит язык С++.
В качестве оболочки компилятора была использована среда Developer Studio версии 4 фирмы Microsoft.
В режиме 3 реально работает только таймер / счетчик Т/С0; установка режима 3 таймера / счетчика Т/С1 приводит к его останову с сохранением содержимого TH1 и TL1.
При установке в режим 3 таймера / счетчика Т/С0 цепи обоих устройств принимают конфигурацию в соответствии с рис. 16. Таймер / счетчик Т/С0 разделяется на два устройства, лишая таймер/ счетчик Т/С1 цепи управления по TR1 и возможности формировать запрос на прерывание. TH0 и TL0 функционируют в этом режиме как два независимых восьмибитных устройства, одно из которых (TH0) может использоваться только в качестве таймера, а другое (TL0) – и в качестве таймера и в качестве счетчика внешних событий с управлением, аналогичным режимам 0, 1 и 2.
В режиме 2 таймеры / счетчики работают с автоперезагрузкой в соответствии с конфигурацией регистров TH и TL, показанной на рисунке 15; конфигурация остальных цепей при этом идентична рисунку 14. В этом режиме для счета используется только один восьмиразрядный регистр – счетчик TL0 (TL1), который в момент перехода из состояния FFH в состояние 00H загружается содержимым регистра TH0 (TH1). Режим 2 используется, как правило, для организации циклических процессов с фиксированным значением времени цикла. Так, например, если запрограммировать Т/С0 как таймер в режиме 2, например, последовательностью команд:
В режимах 0 и 1 таймеры / счетчики конфигурируются в соответствии с рис. 14. Работа таймеров / счетчиков в режимах 0 и 1 идентична за исключением того, что в режиме 0 TL0 (TL1) работает в режиме пятиразрядного счетчика (в целях совместимости с предшествующим поколением микропроцессоров семейства MCS 48), а в режиме 1 – восьмиразрядного.
Для управления прерываниями используются соответствующие биты регистров приоритета IP и разрешения IE. Запрет всех прерываний осуществляется сбросом в 0 бита EA; если бит EA установлен в единицу (прерывания разрешены), то разрешено обслуживание только тех прерываний, биты разрешения которых (EX0 для прерываний INT0, EX1 для INT1, ET0 – для T/C 0, ET1 – для T/C 1 и ES – для последовательного порта) установлены в единицу. Биты EX0 и EX1 могут быть установлены / сброшены программой в любой момент; биты ES, ET0 и ET1 могут быть установлены в единичное значение только тогда, когда соответствующие им устройства полностью сконфигурированы программно.
Параллельный порт Р0 в целом аналогичен по структуре портам других процессоров фирмы INTEL: он имеет двунаправленную архитектуру, и обмен информацией по линиям порта с внешней памятью сопровождается стандартным набором сигналов чтения (RD), записи (WR) и строба адреса (ALE). Если режим обращения к внешней памяти не используется, работа порта Р0 происходит аналогично портам P1…P3, за исключением того, что запись единиц в разряды порта устанавливает соответствующие этим разрядам выводы ОМЭВМ в режим холостого хода (в отличие от портов Р1…Р3, на выводах которых в этом случае устанавливается потенциал высокого логического уровня).
Как было отмечено ранее, обмен информацией с внешними устройствами может быть осуществлен через четыре восьмиразрядных параллельных порта и один последовательный. Структура портов ОМЭВМ семейства МК51 имеет ряд особенностей по отношению к портам других процессоров.
В процессе выполнения операций формируются признаки:
C – перенос;
AC – частичный перенос (перенос между тетрадами);
Z – нулевое значение содержимого аккумулятора;
OV – переполнение;
P – четность.
Для хранения признаков используется регистр PSW, содержимое которого иллюстрируется рисунком 11. В отличие от других признаков, ОМЭВМ семейства МК51 не сохраняют признака Z, поэтому он интерпретируется не как признак нулевого результата операции, а как признак нулевого значения содержимого аккумулятора.