Дан файл, содержащий различные даты. Каждая дата – это число, месяц и год. Найти самую позднюю дату.

program lab14;

type

date = record

day: 1..31;

mounth: 1..12;

year: 1900..2100;

end;

var

j,i: integer;

tmp: date;

a: array [1..30] of date;

c: char;

begin

j:=0; { }

repeat

inc(j);

write(' : ');

readln(a[j].day);

write(' : ');

readln(a[j].mounth);

write(' : ');

readln(a[j].year);

write(' ?(y/n): ');

readln(c);

until not (c in ['y','Y']);

{ }

tmp:=a[1];

for i:= 2 to j do

if a[i].year>tmp.year then

tmp:=a[i]

else

if a[i].year=tmp.year then

if a[i].mounth>tmp.mounth then

tmp:=a[i]

else

if a[i].mounth=tmp.mounth then

if a[i].day>tmp.day then

tmp:=a[i];

writeln(' : ',tmp.day,' ',tmp.mounth,' ',tmp.year);

end.

БИЛЕТ №29

1.Основные понятия теории графов. Изоморфизм графов. Связные графы. Деревья.

Графом G(V,E) называется совокупность 2х множеств- непустого множества V(множества вершин) и множества E неупорядоченных пар различных элементов множества V(E-множество ребер).

G(V,E)=<V;E>, V ,E V V, E=E^-1. Число вершин графа G обозначим p, а число ребер - q:

P:=p(G):=|V|, q:=q(G):=|E.|

Если элементами множества Е являются упорядоченные пары, то граф назы вается ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.

Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф назы­вается графом с петлями (или псевдографом).

Если Е является не множеством, а набором, содержащим несколько одинако­вых элементов, то эти элементы называются кратными ребрами, а граф назы­вается мулътиграфом.

Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называ­ются гипердугами, а граф называется гиперграфом.

Если задана функция F: V -> М и/или F: Е -> М, то множество М называ ется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа

Количество ребер, инцидентных вершине v, называется степенью(или валентностью) вершины v и обозн. d(v):

.

Обозн. минимальную степень вершины графа G через (G), а макс.- через (G):

, .

Если степени всех вершин равны k, то граф наз-ся регулярным степени k:

.Степень регулярности яв-ся инвариантом графа и обоз-ся r(G). Для нерегулярных графов r(G) не определено.

Связные графы

Пусть G=(V,U) — некоторый неориентированный граф. Если для лю­бых вершин х, у ? V, существует цепь, соединяющая эти вершины, то граф О называется связным.

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

Задав отношение связности на множестве V вершин графа, можно с помощью такого отношения определить разбиение множества V, причем, такое, что каждое подмножество этого разбиения является множеством вершин некоторого связного подграфа графа G. Такие подграфы называ­ются компонентами связности или просто компонентами графа G, т.е. в общем случае граф может состоять из нескольких компонент. На рис. 5 изображен граф с двумя компонентами.

Ориентированный граф связен, если соответствующий ему неориен­тированный граф связен, то есть компоненты ориентированного графа оп­ределяются отношением связности для соответствующего ему неориенти­рованного графа. В то же время для ориентированного графа вводится еще понятие «сильно связный». Ориентированный граф называется сильно связным, если для каждой пары различных вершин v и w существует путь

РёР· v РІ w Рё РёР· w РІ v

Деревья

Связный граф без циклов называется деревом. Граф, состоящий из нескольких Деревьев, называется лесом. Для леса можно дать и такое определение: граф, не имеющий циклов и состоящий из k- компонент связности, называется лесом из к деревьев. Легко проверяются такие утверждения:

Граф является деревом тогда и только тогда, когда каждая пара вершин соединена одной и только одной цепью.

Дерево, имеющее п-вершин, содержит n-1 ребро,

Проверим, например, второе утверждение.

Действительно, удаление одного ребра из дерева превращает его в граф из двух деревьев, удаление из графа второго ребра превращает его в лес из трех деревьев и т.д., удалив из графа n—1 ребер, мы получим п ком­понент связности (n изолированных вершин). Учитывая, что леса, состоя­щего из более чем n-компонент не может быть, поскольку количество вершин ограничено числом п, то мы получим, что дерево содержит п-1 ребро.

Пусть задан граф G=(V,U) и пусть G'-подграф графа G. G' называ ется покрывающим деревом, если:

1. G' содержит все вершины графа ;

2. G' связно и не содержит цикла.

На рис.ба изображен граф, его покрывают деревья как на рис.66, так инарис.бв. ' ' _:

Задача.

Построить для данного графа покрывающее дерево,

Алгоритм.

Рассматривается произвольный цикл в графе. Из этого цикла удаля­ется одно ребро.

Проверяется, имеется ли еще цикл, если нет, то переходим к пункту 3, если имеется еще цикл, то возвращаемся к пункту 1.

Имеем покрывающее дерево.

Связный (ориентированный, неориентированный) граф G=(V, U) на­зывается двудольным графом, если множество его вершин V можно раз­бить на два подмножества: V= V1 V2 так, что вершины V1 соединены ребрами с вершинами V2, но вершины одного подмножества V1 или V2 не соединены ребрами между собой.

На рис.7 изображен двудольный граф на множестве вершин {1,2,3,4,5,6,7}

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

Понятие алгоритма.

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