Билет 1.

1. Инкапсуляция, наследование, полиморфизм. Классы, объекты и отношения между ними. Диаграммы логического уровня.

В разделах указывается имя класса, его атрибуты (поля) и операции (методы). Таким образом, класс объединяет данные, представленные атрибутами и алгоритмы по их обработке. И то и другое скрыто от внешних пользователей – других объектов. Сокрытие данных и методов в качестве собственных ресурсов класса получило название инкапсуляции (in capsule).

Переопределение методов реализует идею полиморфизма, позволяющую изменять поведение метода от родителя к потомку

Потомки наследуют характеристики родительских классов и добавляют свои структуры данных и методы их обработки

Диаграммы физического уровня предназначены для описания физической организации системы. К ним относятся диаграмма реализации и развертывания.

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

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

• диаграммы классов – классам и интерфейсам;

• диаграммы объектов – объектам;

• диаграммы компонентов – компонентам;

• диаграммы развертывания – узлам.

Поведенческие диаграммы разделяют в соответствии с основными способами моделирования динамики системы:

• диаграммы прецедентов описывают функциональное поведение системы, видимое конечным пользователем;

• диаграммы последовательности определяют временную упорядоченность сообщений;

• диаграммы кооперации определяют структурную организацию объектов, обменивающихся сообщениями;

• диаграммы состояний описывают изменение состояния объекта (системы) в ответ на получение событий;

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

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

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

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

Отношение обобщения связывает более общий элемент (родительский класс) с более частным (дочерний класс или подкласс) элементом(прям с незакр треуг)

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

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

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

Отношение зависимости является наиболее общей формой отношения, которое используется, когда изменение одного элемента модели может потребовать изменения другого зависимого от него элемента(пунктир со стрелкой)

Отношением реализации является отношением между двумя элементами, при котором один из них описывает некоторый сервис, а другой гарантирует его выполнение. Чаще всего реализация используется для определения отношений между интерфейсами и классами (или компонентами).(пунктир с незакр треуг)

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

2. Симметричные блочные криптоалгоритмы. Сеть Фейштеля.

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

Основные принципы блочного симметричного шифрования.

Как уже было отмечено, блочные шифры обрабатывают кодируемое сообщение блоками из нескольких байт(4-32 байт), при этом блок открытого текста X преобразуется в блок шифротекста Y того же размера с использованием некоторого ключа шифрования Key:

Y = Encrypt(X, Key)

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

X = Decrypt(Y, Key)

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

X = Encrypt((Encrypt(X, Key), Key)

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

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

Таблица 2.1

Основные обратимые операции
Название операции	Графическое обозначение	Формула преобразования	Обратное преобразование
Сложение		X’ = X + V	Вычитание
Сложения по модулю 2		X’ = X ⊕ V	Автообратима
Умножение по модулю 2N+1 (N - размер блока)		X’=(X·V) mod(2N+1)	Сомножитель можно найти по алгоритму Евклида
Циклические сдвиги вправо/влево		X’ = X ROR V X’ = X ROL V	Циклический сдвиг в обратном направлении
Табличная подстановка		X’ = SBox(X)	Обратная подстановка

Для преобразований параметров криптоалгоритмов, которые не требуют обратимости, используются необратимые операции, такие как логические сложение и умножение, арифметические сдвиги влево и вправо, получение остатка от целочисленного деления, умножение по модулю 2^N.

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

фиксированные числовые константы;

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

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

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

Популярной сегодня является сеть Фейштеля, схема которой представлена на рис.2.4.

При шифровании блок открытого текста разбивается на две равные части - левую и правую. На каждом цикле одна из частей подвергается преобразованию при помощиобразующей функции F и вспомогательного ключа k_i, полученного из исходного ключа. Результат преобразования складывается по модулю 2 с другой частью, после чего части меняются местами. Преобразования на каждом цикле идентичны и лишь после последнего раунда не выполняется перестановка частей блока.

Рис. 2.4. Схема сети Фейштеля на М раундов

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

Если размер блока шифрования криптоалгоритма слишком велик, возможны модификации сети Фейштеля с 4 ветвями, один из вариантов которых приведен на рис. 2.5.

Рис. 2.5. Сеть Фейштеля с 4 ветвями

3. Построить программу на языке С++ для работы со структурой Дата. Программа должна обеспечивать простейшие функции для работы с данными структуры: увеличение/уменьшение на 1 день, ввод значений, вывод значений.

unit STR_Date;

interface

Uses SysUtils;

type TUserDate = class

private

fNumber:Word;

fMonth:word;

fYear:Integer;

public

Function SetUserDate(ANumber:Word;AMonth:Word;AYear:Integer):Boolean;

Function GetUserDate:String;

Function ModifyDate(AModify:Integer):String;

end;

implementation

Function TUserDate.SetUserDate;

Begin

If AYear>0 Then

Begin

fYear:=AYear;

if (AMonth >0) and (AMonth<=12) Then

Begin

fMonth:=AMonth;

fNumber:=0;

if ((fMonth=1)or(fMonth=3)or(fMonth=5)or(fMonth=7)or(fMonth=8)or(fMonth=10)or(fMonth=12))and(ANumber>0)and(ANumber<=31) Then

fNumber:=ANumber;

if ((fMonth=4)or(fMonth=6)or(fMonth=9)or(fMonth=11))and(ANumber>0)and(ANumber<=30) Then

fNumber:=ANumber;

if (fMonth=2) Then

if (fYear mod 4 = 0) Then

if (ANumber>0) and (ANumber<=29) Then fNumber:=ANumber

else

if (ANumber>0) and(ANumber<=28) Then fNumber:=ANumber;

if fNumber<>0 Then Result:=True else Result:=False;

end

else Result:=False;

end

else

Result:=False;

End;

Function TUserDate.GetUserDate;

Var str,Itog:String;

Begin

Itog:='';

str:=IntToStr(fNumber);

If length(str)=1 Then Itog:=Itog+'0';

Itog:=Itog+str+'.';

str:=IntToStr(fMonth);

if length(str)=1 Then Itog:=Itog+'0';

Itog:=Itog+str+'.';

Itog:=Itog+IntToStr(fYear);

Result:=Itog

End;

//Данная функция очень утрирована

Function TUserDate.ModifyDate;

Begin

fNumber:=fNumber+ AModify;

Result:=GetUserDate;

End;

end.

Тело программы

program Zad_17;

{$APPTYPE CONSOLE}

uses

SysUtils,

STR_Date in 'STR_Date.pas';

var UsDate:TUserDate;

Y:Integer;

N,M:Word;

F:Boolean;

begin

repeat

Write('Vvedite YEAR = ');

Readln(Y);

Write('Vvedite MONTH = ');

Readln(M);

Write('Vvedite Number = ');

Readln(N);

UsDate:=TUserDate.Create;

F:=UsDate.SetUserDate(N,M,Y);

if F=False Then Writeln('ERROR Date');

Until F;

Writeln('Vvedena Date =>> ',UsDate.GetUserDate);

Write('Vvedite znachenie izmenenij = ');

Readln(Y);

Writeln('New date =>> ',UsDate.ModifyDate(Y));

Readln;

{ TODO -oUser -cConsole Main : Insert code here }

end.

Билет 2

1. Объявление и реализация классов на языке Паскаль.

Для объявления классов (объектных типов) используется зарезервированное слово class. Определим некоторый класс графических примитивов TFigure следующим образом:

TFigure = class

fColor: Byte;

fThickness: Byte;

fCanvas: TCanvas;

procedure SetColor(Value: Byte);

procedure SetThickness(Value: Byte);

procedure PrepareCanvas;

end;

По принятому соглашению имена классов начинаются с заглавной буквы «T», имена полей данных начинаются с буквы «F», и поля класса объявляются до методов. Класс объединяет данные, представленные атрибутами (полями) и алгоритмы (методы) по их обработке.

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

Методы класса определяют действия, выполняемые над данными. Их совокупность характеризует функциональный аспект поведения класса. Методы представляют собой процедуры и функции, принадлежащие классу. К методам класса относится метод PrepareCanvas, выполняющий подготовку полотна к работе и два метода задания значений полей данных – SetColor и SetThickness.

Таким образом, в одной информационной структуре TFigure оказались объединены как исходные параметры, так и необходимые средства по выполнению их реализации. Такое объединение (сокрытие) данных и методов в качестве собственных ресурсов класса получило название инкапсуляции.

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

unit figures;

Interface

type

TFigure = class

fColor: Byte;

fThickness: Byte;

fCanvas: TCanvas;

procedure SetColor(Value: Byte);

procedure SetThickness(Value: Byte);

procedure PrepareCanvas;

end;

Implementation

procedure TFigure.SetColor(Value: Byte);

begin

if fColor <> Value then

fColor:=Color;

end;

procedure TFigure.SetThickness(Value: Byte);

begin

if fThickness <> Value then

fThickness:=Value;

end;

procedure TFigure.PrepareCanvas;

begin

{ Подготовка полотна для рисования }

end;

end.

Методы SetColor и SetThickness выполняют присвоение внутреннему полю fColor и fThickness значения в том случае, если текущее значение отличается от передаваемого. К полям класса никогда не следует обращаться напрямую, а только посредством специальных методов, обеспечивающих корректность выполнения операции присваивания.

Теперь объявим переменную f класса TFigure:

var

f: TFigure;

Переменную f называют экземпляром класса, объектной ссылкой или просто объектом. Через объект f возможен доступ к методам и полям класса. Однако для начала необходимо создать сам объект. Для этого необходимо вызвать специальную процедуру Create, называемую конструктором:

f:=TFigure.Create;

Конструктор не объявлен в классе TFigure, однако присутствует в нем благодаря наследованию от класса TObject. В результате будет выделена область памяти в размере, необходимом для хранения объекта f. Обратите внимание, конструктор вызывается с помощью ссылки на тип, а не на экземпляр типа, в отличие от методов, которые всегда вызываются с помощью ссылки на экземпляр. Связано это с тем, что объект f на момент вызова конструктора еще не создан.

После создания объекта с ним можно работать:

uses figures;

var

f: TCircle;

begin

f:=TCircle.Create;

f.SetColor($FF);

f.SetThickness(1);

f.PrepareCanvas;

f.Free;

end.

После выполнения методов объект f следует удалить, чтобы он не занимал места в памяти. Удаление выполняет метод Destroy, определенный в классе TObject, но лучше использовать Free, т.к. он инкапсулирует вызов Destroy: в начале определяется, существует ли объект и только затем выполняется вызов Destroy. В противном случае метод Free ничего не делает.

Класс Figure можно несколько модифицировать. Например, можно явно добавить к методам конструктор Create с помощью зарезервированного слова constructor и деструктор Destroy с помощью зарезервированного слова destructor:

TFigure = class

...

constructor Create; virtual;

destructor Destroy; override;

end;

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

constructor TFigure.Create;

begin

fColor:=$FF;

fThickness:=1;

fCanvas:=TCanvas.Create;

end;

В деструкторе обычно выполняются действия, связанные с освобождением задействованных в течение работы объекта ресурсов:

destructor TFigure.Destroy;

begin

{ Освобождение ресурсов, используемых в работе объекта }

fCanvas.Free;

end;

2. Интерфейс. Пользовательский интерфейс. Классификация пользовательских интерфейсов.

Пользовательский интерфейс (ПИ) программы – совокупность элементов, позволяющих пользователю программы управлять ее работой и получать требуемые результаты.

Пользовательский интерфейс состоит из множества составляющих, таких как:

• набор задач пользователя, которые он решает при помощи системы

• используемая системой метафора (например, рабочий стол в MS Windows и т.п.)

• элементы управления системой

• навигация между блоками системы

• визуальный (и не только) дизайн экранов программы.

Структура и классификация пользовательских интерфейсов

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

В настоящее время оформилось два принципиально различных подхода к организации ПИ. Первый подход состоит в предоставлении пользователю командного языка, в котором запуск программ оформлен в виде отдельных команд. Этот подход известен как интерфейс командной строки (Command Line Interface - CLI).

Альтернативный подход состоит в символическом изображении доступных действий в виде картинок – икон (icons) на экране и предоставлении пользователю возможности выбирать действия при помощи мыши или другого координатного устройства ввода. Этот подход известен как графический пользовательский интерфейс (Graphical User Interface - GUI). Один из подклассов GUI (двухмерный) принято обозначать аббревиатурой WIMP (Windows-Icons-Menus-Pointing device), что отражает задействованные интерактивные сущности - окна, пиктограммы, меню и позиционирующее устройство (обычно мышь).

Аргументы в пользу CLI

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

Аргументы в пользу GUI

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

Недостатки WIMP-интерфейсов

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

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

В-третьих, WIMP GUI вместе с их 2D- интерфейсными элементами проектировались для работы с двухмерными же приложениями - такими, как обработка текстов, компоновка документов и электронные таблицы. Если же приложение является по своей сути трехмерным, то работа с ним с помощью 2D элементов управления становится не слишком естественной. Нынешние WIMP-интерфейсы для 3D-приложений обычно состоят из управляющих панелей с 2D-кнопками и слайдеров, окружающих 3D-мир, которые используются для управления 3D-курсором, для манипуляций с точкой зрения наблюдателя и для редактирования объектов. Понятно, что 3D-приложения, как правило, имеют много большую визуальную сложность, чем двухмерные, что еще более усиливает связанные с WIMP-интерфейсами проблемы.

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

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

Сегодня развиваются такие новые классы интерфейсов, как SILK (речевой), биометрический (мимический) и семантический (общественный).

Начал получать распространение и новый вид пользовательского интерфейса – тактильный. Тактильные устройства, в отличие от других интерактивных устройств, способны как "чувствовать", так и передавать информацию. Эти устройства имеют общую особенность: они снабжены средством силовой обратной связи - таким, как PHANToM, которое получает информацию о положении и жесте, а возвращает величину приложенной в точке силы. Таким образом, пользователь может ощущать форму жесткого объекта, в том числе через несколько слоев различного сопротивления при надавливании на внешнюю поверхность (что полезно, например, в хирургических симуляторах).

3. Написать программу на языке С++, реализующую телефонный справочник. В справочнике содержится следующая информация о каждом абоненте: имя и телефон. Реализовать вывод всей информации из справочника, поиск телефона по имени, поиск имени по телефону.

#include <iostream.h>

#include <conio.h>

#include <string.h>

#include <stdio.h>

void main()

{

struct Teleph

{

char FIO[20];

char Nomer[20];

} spisok [10];

int N,i,K;

char Str[20];

do

{

cout<<"\n 1. Cteate spravochnik";

cout<<"\n 2. Print spravochnik";

cout<<"\n 3. Find po FIO";

cout<<"\n 4. Find po Telephone";

cout<<"\n 5. Exit";

cout<<"\n Vvedite N ==";

cin>>N;

if(N==1)

{

cout<<"\n Vvedite kolichestvo ==";

cin>>K;

for (i=1;i<=K;i++)

{

cout<<"\n Vvedite FIO ==";

cin>>spisok[i].FIO;

cout<<"\n Vvedite Telephone ==";

cin>>spisok[i].Nomer;

}

}

if(N==2)

{

cout<<"\n Print...";

for(i=1;i<=K;i++)

{

cout<<"\n FIO = "<<spisok[i].FIO;

cout<<" Telephone = "<<spisok[i].Nomer;

}

}

if(N==3)

{

cout<<"\n Vvedite FIO == ";

cin>>Str;

for(i=1;i<=K;i++)

if (strcmp(spisok[i].FIO,Str)==0)

cout<<"\n Telephone = > "<<spisok[i].Nomer;

cout<<"\n";

}

if(N==4)

{

cout<<"\n Vvedite TELEPHONE == ";

cin>>Str;

for(i=1;i<=K;i++)

if(strcmp(spisok[i].Nomer,Str)==0)

cout<<"\n FIO => "<<spisok[i].FIO;

cout<<"\n";

}

} while (N!=5);

}

Билет 3.

1. Графы. Основные определения. Машинное представление графов в последовательной памяти и связанной памяти.

Граф - нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта, обладающая следующими свойствами:

на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

каждый элемент может иметь связь с любым количеством других элементов;

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

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

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

Граф, все связи которого ориентированные, называется ориентированным или орграфом. Граф со всеми неориентированными связями называется неориентированным, а граф со связями обоих типов - смешанным графом. Обозначение связей: неориентированных - (A,B), ориентированных - <A,B>. Примеры изображений графов приведены на рис. 6.1. Скобочное представление имеет вид: а). ((A,B),(B,A)) и б). (< A,B >,< B,A >).

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

(B)

(A)

(B)

(A)

а). б).

Рис. 6.1. Граф неориентированный (а) и ориентированный (б).

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

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

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

Существует несколько способов графического изображения деревьев (рис. 6.1).