Логика предикатов

Высказывания, которые нельзя формализовать на языке логике высказываний: 1. Каждый любит сам себя. Значит кто-то кого-то любит. 2. Перья есть только у птиц. Ни одно млекопитающее не является птицей. Значит, все млекопитающие лишены перьев.

Введём специальные обозначения: Специальные переменные, значениями которых являются объекты из соответствующих предметных областей:x и y. Свойства объектов и бинарные отношения между объектами:,. Фраза вида «Все х обладают свойством Р» записывать символически: «некоторые х обладают свойством P» записывать символически Введём специальные обозначения: Специальные переменные, значениями которых являются объекты из соответствующих предметных областей:x и y. Свойства объектов и бинарные отношения между объектами:,. Фраза вида «Все х обладают свойством Р» записывать символически: «некоторые х обладают свойством P» записывать символически

Субъект – это то, о чем что-то утверждается. Предикат – это то, что утверждается о субъекте. Логика предикатов – это расширение логики высказываний за счет исполнения предикатов в роли логических функций. Предикатом называется функция, определённая на множестве M и принимающая значение «истина» или «ложь», то есть Множество M – контекст, или предметная область, или область определения предиката. Множество всех, при которых, называется множеством истинности предиката

Примеры: 1) Луна есть спутник Венеры – ложное высказывание, не являющееся предикатом, так как в нем нет аргумента – переменного х. 2) - то же самое. 3) - предикат. Здесь:

Операции логики предикатов Предикат Р(х), определенный на множество M называется тождественно истинным, если область определения предиката, и называется тождественно ложным, если Говорят, что предикат Р(х) является следствием предиката Q(x) (Q(x)Р (x)), если, и предикаты P(x) и Q(x) равносильны ( ), если

Конъюнкция Конъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x)^Q(x), который принимает значение «истина» при тех и только тех значениях x єM, при которых каждый из предикатов принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Областью истинности предиката P(x)^Q(x) является

Дизъюнкция Дизъюнкцией двух предикатов P(x),Q(x) называется новый предикат P(x)vQ(x), который принимает значение «ложь», при тех и только тех значениях x єM, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката P(x)vQ(x) является

Отрицание Отрицанием предиката P(x) называется новый предикат P(x), который принимает значение «истина» при всех значениях x єM, при которых P(x) принимает значение «ложь» и наоборот. Областью истинности предиката P(x) является

Импликация Импликацией предикатов P(x) и Q(x) называется новый предикат P(x)Q(x), который являются ложными при тех и только тех значениях x єM, при которых P(x) одновременно принимает значение «истина», а Q(x) – значение «ложь», во всех остальных случаях это «истина».

Эквиваленция Эквиваленцией предикатов P(x) и Q(x) называется новый предикат P(x)Q(x), который являются истинным при тех и только тех значениях x єM, при которых одновременно P(x) и Q(x) принимает одинаковые значения значение «истина» или «ложь», и ложным во всех остальных случаях.

Примеры 1) На множестве M={3,4,5,6,7,8} заданы два предиката P(x):«х – простое число»,Q(x):«х – нечетное число». Составить их таблицы истинности. Равносильны ли предикаты P(x) и Q(x) на множествах L={2,3,4,5,6,7,8},K={3,4,5,6,7,8,9} ? Очевидно,что,. Таким образом, на множестве М P(x)=Q(x). На L и K предикаты не равносильны, ибо на L, например, 2 – простое число и четное, а на К число 9 – нечетное, но составное число. x P(x) Q(x)101010

2) Найти область истинности предиката и изобразить на плоскости. Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенной между ветвями параболы y=x 2.

3 ) На множестве M={1,2,3…20} заданы предикаты A(x): «х не делиться на 5», B(x): «х –четное число»,C(x): «х – число простое», D(x): «х кратно трем». Найти множества истинности предикатов A(x)^B(x)^C(x), A(x)vB(x),D(x)C(x). 1. A(x)^B(x)^C(x)= {х не делится на 5 и х – четное число и х кратно трем} = {х не делится на 5 и х делится на 6}. Действительно, 2. A(x)vB(x)= {х не делится на 5 или х – четное число}. 3. D(x)C(x)= D(x)vC(x). = {х не кратно трем или х – непростое число}. Здесь рассуждения сложнее, однако, если перебрать все элементы множества М, то легко установить, что

Кванторные операции Кванторные операции могут рассматриваться как обобщение операций конъюнкции и дизъюнкции в случае бесконечных областей. Квантор всеобщности (all - всякий) Под выражением xP(x) понимают высказывание, истинное, если P(x) истинно для каждого x єM, и ложное в противоположном случае. Словесная интерпретация: «для каждого х P(x) истинно». Переменная х в предикате P(x) является свободной (х – любое из М), в высказывании хP(x) является связанной переменной, т.е. переменную, к которой относится квантор наз. связной, остальные переменные наз. свободными. Рассмотрим предикат P(x), определенный на множестве M:{a1,…,an}. С праведлива равносильность

В обычных выражениях квантор всеобщности выражается следующим образом: P(x), при произвольном х; P(x), при какого бы не было х; для каждого х верно P(x); всегда имеет место P(x); каждый обладает свойством P; всё удовлетворяет P.

Квантор существования Ǝ (exist - существовать) Пусть P(x)- предикат,x єM. Под выражением Ǝ x P(x) понимают высказывание, истинное, если существует x єM, для которого P(x) истинно, и ложное в противоположном случае. Переменная х в предикате является свободной (х – любое из М), в высказывании Ǝ x P(x)- х является связанной переменной. Словесная интерпретация: «существует х, при котором P(x) истинно». С праведлива равносильность

В обычных выражениях квантор существования выражается следующим образом: для некоторых х имеет место P(x); для подходящего х верно P(x); имеется х, для которого P(x); у некоторых вещей есть признак Р; кто-нибудь относится к (есть) Р.

Если предикат является функцией нескольких переменных, то он называется n-местным или n- арным предикатом. Кванторные операции могут применять и к многоместным предикатам. Например, применение кванторной операции к предикату P(x,y) по переменной х ставит в соответствие ему одноместный предикат xP(x,y) или Ǝ xP(x,y), зависящий от y и не зависящий от x. К двухместному предикату при применении кванторов по обеим переменным получается 8 высказываний: x yP(x,y) y xP(x,y) Ǝ x yP(x,y) Ǝ y xP(x,y) x Ǝ yP(x,y) y Ǝ xP(x,y) Ǝ x Ǝ yP(x,y) Ǝ y Ǝ xP(x,y)

В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логических значений, то есть, например, высказывания и различны. Квантор существования можно выразить через квантор всеобщности применительно к предикату A(x) следующим образом Квантор всеобщности можно выразить через квантор существования применительно к предикату A(x)следующим образом

Пример: 1) Пусть P(x,y) означает что х является матерью для у. Тогда выражение означает, что у каждого человека есть мать – это истинное утверждение. Выражение означает, что существует мать всех людей. Истинность этого утверждения зависит от множества значений, которые могут принимать y: если это множества братьев и сестер, то оно истинно, в противном случае ложно.

2) Установить истинность или ложность высказывания Исходное высказывание преобразуем к виду: Исходное высказывание истинно.

Формулы логики предикатов и интерпретация В логике предикатов используется символика: Символы p 1, q 2, r 3, … – переменные высказывания; Предметные переменные и предметные константы;,n i єN, - предикатные символы, – ni-местный предикатный символ;, - функциональные символы, – nj- местный функциональный символ; Символы логических операций: Символы кванторных операций:, Ǝ Вспомогательные символы: скобки, запятые.

Формулой логики предикатов называется всякое выражение, содержащее символику 1…7 и удовлетворяющее следующим требованиям: атомарная формула есть формула; если A и B – формула, то AB,AB,AvB,A^B - тоже формулы при условии, что одна и та же предметная переменная не является в А свободной, а в В связанной или наоборот; если А – формула, то и Ā - тоже формула; если A(x)- формула, то Ǝ xA(x) и xA(x) являются формулами, причем если в A(x) х – свободная переменная, то в Ǝ xA(x) и xA(x) будет уже связанной переменной.

Формулы имеют смысл тогда, когда имеется какая-нибудь интерпретация входящих в неё символов. Под интерпретацией понимается всякая пара, состоящая из непустого множества М, названного областью интерпретации, и какого-либо отображения, относящему каждому предикатному символу арности N некоторое n-местное отношение на M.

Пример: 1 ) Является ли данное выражение формулой логики предикатов? – не является формулой, так как квантор существования употреблен для уже связной квантором всеобщности переменной y. - является формулой; x – связанная переменная; y – свободная; - не является формулой, ибо в первом логическом слагаемом х – связанная переменная, а во втором слагаемом свободная.

2) Даны следующие утверждения A(n): «число n делится на 3»;B(n): «число n делится на 2»; С(n): «число n делится на 4»;D(n): «число n делится на 6»; E(n): «число n делится на 12». Указать, какие из следующих утверждений истинны, а какие ложны: а) A(n)^B(n): «число n делится на 6», A(n)^B(n)E(n): «если n делиться 6, то оно делится на 12». При n=6 импликация ложна, следовательно, исходная формула в общем ложна. б) B(n)^C(n):«число делится на 4»,B(n)^C(n)¬D(n): «если число делиться на 4, то оно не делиться на 6». Такое может быть, например, при n=16. Следовательно, B(n)^C(n)¬D(n) - не тождественно ложная формула, а тогда - истинная формула алгебры предикатов.

Формула содержит только связанную переменную х. Эта формула является тождественно истинным высказыванием в любой интерпретации. Напротив, формула - тождественно ложная формула в любой интерпретации.

Применение языка логики предикатов для записи математических предложений Определение экстремума функции (минимума в точке х 0), где

Определение выпуклости (вогнутости) функции f(x) Если во всех точках интервала (a,b) вторая производная, то f(x) на (a,b) выпукла.

Теория графов

Основные определения Граф - совокупность двух множеств V(точек) и E (линий), между элементами которых определено отношение инцидентности, причем каждый элемент е Е инцидентен ровно двум элементам v, v V. Элементы множества V - вершинами графа G, элементы множества Е – его ребрами ( v G и е G) Число вершин графа G называется его порядком IVI = n. Если IVI = n и IЕI= m, то граф можно обозначить G mxn.

Две вершины U и V графа смежные, если множество { U, V } является ребром. Если Е={ U,V } –ребро, то вершины U и V называют его концами. Два ребра называются смежными, если они имеют общий конец. Каждому ребру можно приписать направление от первой из инцидентных вершин ко второй. Направленные ребра называют дугами, а содержащий их граф – ориентированным. Первая по порядку вершина, инцидентная ребру, называется его началом, вторая его концом.

Изображение графов Неориентированные графы

v1 v3 v2 v4 Ориентированный граф v2v2 v1 v4v4v3v3 Линии, изображающие ребра графа, могут пересекаться, но точки пересечения не являются вершинами. Каждому неориентированному графу можно поставить в соответствие ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющими противоположные направления. Такое соответствие называется каноническим.

Граф G называется полным, если любые две его вершины смежны. V1V1 V2V2 V1V1 V2V2 V3V3 V1V1 V4V4 V3V3 V2V2 V1V1 V2V2 V5V5 V4V4 V3V3 V2V2 Граф называется пустым, если в нем нет ребер. Пустой граф порядка n обозначается через 0 n. V1V1 v1 v4 v3 v5 v2

Если для каждой вершины смежны два ребра, то такой граф называется циклом (замкнутым графом) - Cn Трицикл -C 3 Пятициклы - С 5 Четырецикл-С4 Незамкнутый граф, где вершины имеют не более 2 смежных ребер, но не менее одного называют цепями – Р n P2P2 P3P3 P5P5 P4P4 P6P6 Некоторая последовательности смежных дуг называется путем, а последовательность смежных ребер называется цепью

Дополнительный граф или дополнение : v = VG, и любые две несовпадающие вершины смежны в тогда и только тогда, когда они не смежны в G. Две вершины могут соединяться более чем одним ребром, такой граф называется мультиграфом V1V1 V2V2 e2e2 e1e1 Паре вершин {V1,V2} инцидентны ребра e1 и e2, в этом случае ребра e1 и e2 называются кратными.

Ребра, соединяющие вершину саму с собой, называют петлями

Степени вершин графа Пусть G- неориентированный граф. Количество (v) ребер, инцидентных вершине V G, называется ее локальной степенью или просто степенью. Граф называется однородным степени К, если степени всех его вершин равны К. Максимальная степень вершин графа G обозначается (G) и минимальная степень вершины G обозначается символом (G). Список степеней вершин графа называется постепенной последовательностью.

Вершина степени 0 называется изолированной, вершина степени 1 наз. концевой. Теорема: Сумма степеней всех вершин графа- четное число, равное удвоенному числу ребер. В любом графе число вершин нечетной степени четно. Для вершин ориентированного графа определяются две локальные степени: 1 (V)- (P - )число ребер с началом в вершине V - количество выходящих из V ребер, и 2 (V)- (P + )количество входящих в V ребер, для которых эта вершина является концом. Петля дает вклад 1 в обе эти степени. P(V)= P - (V)+ P + (V)

Части, суграфы и подграфы. Граф Н называется частью графа G, Н G, если множество его вершин V(H) V(G), а множество Е(Н) Е(G). Если V(H)=V(G),часть графа называется суграфом. Подграфом G(U) графа G с множеством вершин U V называется часть, которой принадлежат все ребра с обоими концами из U. Звездный граф для вершины V G состоит из всех ребер с началом или концом в вершине V. Множество вершин звездного графа состоит из V и других, инцидентных его ребрам вершин.

V 1 V 3 Подграф G U={V 1, V 2, V 3, V 5 } Граф G V5 V5 V 2 V 3 V 4 V 6 V 1 Часть H Графа G V1V1 V2V2 V5V5 Суграф G V4V4 V 5 V1V1 V6V6 V2V2 V3V3 V2V2 V5V5 V 2 V 5 V 3 Звездный граф для вершины V 2 V1V1

Операции с частями графа. Дополнение Н части Н определяется множеством всех ребер графа, не принадлежащих Н. V 1 V 2 V 3 V 4 V 6 V 5 Сумма Н 1 Н 2 и пересечение Н 1 Н 2 частей Н 1 и Н 2 графа G определяется естественно : V(Н 1 Н 2 )= V(Н 1 ) V(Н 2 ); E(Н 1 Н 2 )= E(Н 1 ) E(Н 2 ); V(Н 1 Н 2 ) = V (Н 1 ) V(Н 2 ); E(Н 1 Н 2 ) = E(Н 1 ) E(Н 2 ); Две части Н1 и Н2 не пересекаются по вершинам, если они не имеют общих вершин, а,значит, и общих ребер. Сумма Н1 Н2 не пересекающихся по вершинам частей называется прямой суммой ( верно для любого числа частей). Части Н1 и Н2 не пересекаются по ребрам, если E(Н1) E(Н2)=Ǿ. Например, для любой части Н и ее дополнения Н сумма G = H H прямая по ребрам.

Операции над графами 1Объединение графов G a (V a,E a ) и G b (V b,E b ) называется граф G(V,E), множество V которого соответствует V a V b и множество Е соответствующее E a E b U = Объединение F и G называется дизъюнктивным, т.е. у двух графов не должно быть общих вершин. a b U = a b 1 2 3

2. Сумма графов Суммой графов F и G называется граф, образованный F G. Дополнительно к уже существующим ребрам графов F и G, проводятся ребра от каждой вершины графа F до каждой вершины графа G. a b = a b F G

3. Произведение графов Произведением графов F и G FxG=U называется граф, для которого VU=VFxVG – декартово произведение множеств вершин исходных графов. EU- определяются следующим образом, вершины (f1,g1) и (f2,g2) смежны в графе U тогда и только тогда, когда f1 = f2, а g1 и g2 смежны в G, или g1 = g2, а f1 и f2 смежны в F. Класс графа |U|=|F|x|G| (у нас |F|=2; |G|=3 |U|=2x3=6). Число ребер графа U определяется |E(FxG)| = |F|x |EG| + |G|x|EF|. |EG|=3, |EF|=1, |E(FxG)|=2x3 + 3x1 = 6+3=9. a b x = (a,1) (b,1) (a,3) (b,3) (b,2)

Маршруты, цепи, циклы Чередующая последовательность V 1, e 1, V 2, e 2…… e I, V I+1 вершин и ребер графа, такая, что e I = V I V I+1 называется маршрутом, соединяющим вершины V 1 и V I+1. Маршрут можно задать последовательностью V 1, V 2,…… V I+1 его вершин, и e 1, e 2,……… e i его ребер. Одно и то же ребро может встречаться в маршруте несколько раз. Конечная последовательность ребер (e 1, e 2,,,,,,,,,,,,,, e n ) образует конечный маршрут. Вершина V 0, инцидентная ребру e 1 и не инцидентная e 2, называется началом маршрута. Если же ребра e 1 и e 2 – кратные, необходимо специальное указание, какую из двух инцидентных им вершин считать началом маршрута. Аналогично определяется конец маршрута. Вершины, инцидентные ребрам маршрута, кроме начальной и конечной, называются внутренними или промежуточными.

Число ребер называется длиной маршрута. Отрезок (e i, e i+1, …..,e j ) конечного или бесконечного маршрута М сам является маршрутом. Маршрут М называется цепью, если каждое ребро встречается в нем не более одного раза, и простой цепью, если любая вершина графа G инцидентна не более чем двум его ребрам. Циклический маршрут называется циклом V 1 =V I+1, если он является цепью, и простым циклом, когда это простая цепь. Фактическим циклом считают циклически упорядоченное множество ребер, в котором любые два соседних ребра имеют общую инцидентную вершину. Последовательности (е 1 е 2,е 3,е 4 ), (е 2, е 3,е 4,е 1 ), (е 3, е 4,е 1,е 2 ),(е 4, е 1,е 2,е 3 ) представляют один и тот же цикл. Простой цикл длины L называется L-циклом. Минимальная из длин циклов графа называется его обхватом.

Для ориентированного графа вводится понятие ориентированного маршрута, это последовательность, в которой еi=(vi,vi+1). Вершина v называется достижимой из вершины u, если существует (u,v) путь. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Всякий максимальный связный подграф графа G называется связной компонентой или просто компонентой. Утверждения: 1. При u v всякий (u,v) маршрут содержит простую (u,v) цепь. 2. Всякий цикл содержит простой цикл. 3. Объединение двух несовпадающих простых цепей (u,v) содержит простой цикл. 4. Если C и D - два несовпадающих простых цикла, имеющих общее ребро е, то граф (C D) – также содержит простой цикл. 5. Для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины U и каждой другой вершины V существовал (U, V)-маршрут. 6. Для любого графа либо он, либо его дополнение является связным.

Расстояния. Пусть G-связный неориентированный граф, V и V-любые две его вершины. Поэтому существует связывающая V и V цепь с минимальным количеством ребер. Минимальная длина простой цепи с началом V и концом V называется расстоянием d(V, V) между этими вершинами. Расстояние d(V, V) удовлетворяет аксиомам метрики: d(V, V) 0, причем d(V, V) = 0 тогда и только тогда, когда V= V d(V, V) = d(V, V) d(V, V) + d(V, V) d(V, V).

До этого момента мы считали длину ребра = 1, а общее расстояние между вершинами V / и V // = числу ребер из маршрута (V /, V // ). Пусть каждому ребру (V /, V // ) поставлено в соответствие действительное число L(V /,V // )- длина ребра. Длина ребра проставляется на ребре. Длина пути L(V i0, V i1, …, V ip ) определяется как сумма длин входящих в него рёбер. Расстоянием d(V i, V J ) между двумя вершинами V i и V j называется нижняя грань длин путей L(V i, …, V J ) с началом в первой и концом во второй из этих вершин; протяжённостью g (Vi, Vj) – верхняя грань этих длин.

Матрицы для графов Матрицей смежности данного графа G называется квадратная матрица порядка n, где n – мощность множества V, элемент которой определяется следующим образом Для графа, две вершины которого соединены не более чем одной дугой одного направления, матрица смежности состоит из единиц и нулей (K=1).

Граф, имеет следующую матрицу смежности: Единицы, стоящие на главной диагонали матрицы смежности, соответствуют петлям при данной вершине. Изолированной вершине соответствуют строка и столбец, состоящие из нулей. Число единиц в матрице смежности равно числу дуг графа

матрица смежности для графа суммы есть булева сумма матриц смежности складываемых графов: cij=aij+bij,причем 0+0=0; 0+1=1; 1+0=1; 1+1=1. Матрица смежности для графа- пересечения может быть получена поэлементным умножением dij=aij×bij, причем 0×1=0; 1×0=0; 0×0=0; 1×1=1, т.е. матрица смежности графа-пересечения содержит единицы только в качестве тех элементов, которые равны единицам в обеих матрицах смежности перемножаемых графов.

Транспонированной матрице смежности соответствует граф с противоположной ориентацией. Матрица смежности полностью задает ориентированный граф. Любая квадратная матрица, состоящая из единиц и нулей, может быть рассмотрена как матрица смежности, задающая некоторый граф G.

Матрица инциденций Матрицей инциденций ориентированного графа G(X,U) называется прямоугольная матрица порядка [n * m], где n – мощность множества x, m – мощность множества u, каждый элемент которого a ij определяется следующим образом:

Пример Написать матрицу инциденций для графа матрица инциденций будет иметь следующий вид:

Матрицы достижимостей и контрадостижимостей Пусть задан граф G. Говорят, что вершина x j достижима из вершины x i, если существует по крайней мере один путь из x i в x j. Матрицей достижимостей R=(r ij ) называется квадратная матрица порядка n (n – число вершин графа), элементы которой определяются следующим образом: Вершина графа G, достижимая из вершины xi, может быть достижима с использованием путей длины 0, или 1, или 2,…, или p, следовательно множество R(xi) вершин, достижимых из xi, можно представить в следующем виде:

Пример. Для графа G построить матрицу достижимостей Г p (x) является множеством вершин, которые достижимы из x i с помощью путей длины p. Находим множества достижимостей :

Матрицей контрадостижимостей (обратных достижимостей) Q=(q ij ) называется квадратная матрица порядка n, такая, что: где Q(x i ) – множество таких вершин, что из любой вершины этого множества можно достигнуть вершину x i. Контрадостижимое множество Q(x i ) строится на основании следующего выражения: где Г -р (x i ) – множество вершин, из которых достижима вершина x i с использованием пути длины р;

Пример. Для предыдущего графа G построить матрицу контрадостижимостей.

ДЕРЕВЬЯ Неориентированный граф с числом вершин n>1 называется деревом, если он связен и не содержит циклов. Для графа G, имеющего n вершин (n>1), равносильны следующие свойства (определения): 1. G связен и не содержит циклов; 2. G не содержит циклов и имеет (n-1) ребро; 3. G связен и имеет (n-1) ребро; 4. G не содержит циклов, но добавление ребра между любыми его вершинами приводит к образованию цикла; 5. Всякая пара вершин G соединена только одной цепью.

Ориентированное дерево называется прадеревом. Несвязный граф, компонентами связности которого являются деревья, называется лесом. Подграф G(X,U), содержащий все вершины графа G(X,U), называется частичным графом. Теорема. Граф G(X,U) тогда и только тогда содержит частичный граф, являющийся деревом, когда он связен.

Постановка задачи Предположим, что имеется n городов, которые нужно соединить нефтепроводом (электролинией, газопроводом). Стоимость строительства нефтепровода между городами xi, xj задана. Как построить самый дешевый нефтепровод, связывающий все города? Построим граф, вершинами которого обозначены города, а ребрами возможные нефтепроводы между ними. Каждому ребру графа (xi,xj) поставим в соответствие число l(xi,xj)0, равное стоимости строительства нефтепровода на участке (xi,xj). Задача строительства самого дешевого нефтепровода сводится к следующей задаче на графе. Задан конечный неориентированный связной граф G(X,U) каждому ребру которого (xi,xj)=u k, u k U, поставлено в соответствие число l(u k )0, называемое длинной ребра. Требуется найти такой частичный граф-дерево графа G (частичное дерево), общая длина ребер которого минимальна. Решение этой задачи может быть получено с помощью следующего алгоритма.

Алгоритм Краскала 1. Выбираем самое короткое ребро графа u 1, затем ребро u 2, самое короткое из оставшихся; 2. Из оставшихся ребер выбираем самое короткое ребро u 3 так, чтобы оно не образовывало цикла с выбранными ребрами; 3. Продолжаем эту процедуру. На k-м к выбранным ребрам u 1,…, u к-1 добавляем самое короткое ребро из оставшихся U-(к-1) ребер так, чтобы оно не образовывало цикла с выбранными ребрами; 4. При k=n-1 процесс заканчивается. Получим граф без циклов с (n-1)-м ребром. Построенный граф есть дерево, обозначим T(n-1).

Пример Требуется построить газопровод, соединяющий 10 городов Возможные соединения городов обозначены ребрами, длины которых l(x i,x j ), представляющие собой стоимость строительства газопровода на участке (x i,x j ), заданы и обозначены на графе. Как построить самый дешевый газопровод? Задача сводится к отысканию частичного дерева заданного графа, общая длина ребер которого минимальна.

Решение Частичное дерево должно содержать (n-1) ребер, т.е. 9 общее число ребер исходного графа

Заданные длины ребер удобно поместить в симметричную таблицу. На пересечении строки x i и столбца x j стоит число, равное длине дуги т.е. l(x i,x j ). Число заполненных клеток равно числу ребер графа. Следуя алгоритму, выбираем самые короткие ребра u 1 =(x 1,x 2 ), u 2 =(x 4,x 6 ), l(u 1 )=l(u 2 )=

Сумма длин ребер построенного дерева L=34. Стоимость строительства самого дешевого газопровода по исходным данным составляет 34 денежные единицы.

Экстремальные задачи на графах Задача о кротчайшем пути между двумя вершинами ориентированного графа Постановка задачи состоит в следующем. Задан конечный ориентированный граф G(X,U). Каждой дуге графа u поставлено в соответствие некоторое число l(u)0 - длина дуги u. Длинной пути μ называется сумма длин дуг, составляющих данный путь. Требуется для двух фиксированных вершин x o и x n графа G(X,U) найти самый короткий соединяющий их путь.

К данной задаче может быть сведена следующая задача экономического содержания. Задана сеть дорог, соединяющих пункты x i (i=0,1,…,n). Найти путь, соединяющий пункты x o и x n, по которому можно доставить груз в кратчайшее время. При этом время доставки груза из пункта x i в x j (i,j=0,…,n) задано и равно l(u ij )=l( x i x j )0. Если под длинной дуги l(x i x j ) понимать стоимость перевозки груза из пункта x i в x j, то содержание задачи составит определение такого пути из пункта x i в x j, на котором затраты на транспортировку были бы минимальными.

Пример Имеем 6 пунктов Х (x 0,…,x 6 ). Время доставки груза из i-го пункта в j-й, т.е. l(x i,x j ), задано и изображено числом в кружке. Так, l(x 0,x 1 )=2, l(x 0,x 2 )=4, l(x 0,x 3 )=5, l(x 1,x 4 )=3… Требуется определить путь, по которому из пункта x 0 в пункт x 5 можно доставить груз в кратчайшие время, и само кратчайшее время доставки.

Алгоритм 1. На первом шаге ставим следующие метки: для вершины x 0 λ 0 =0, для любой другой вершины x i λ i =+ (i=1,…,n); 2. Ищем на графе такую дугу (x i,x j ), для которой λ j -λ i >l(x i,x j ). Причем разность - считаем равной 0. Если такая дуга найдется, меняем метку вершины x j на λ j =λ i +l(x i,x j ). λ j =min{λ i +l(x i,x j )}.(*) 3. Повторяем процедуру пункта 2 до тех пор, пока метки вершин не перестанут меняться.

пример Для вершины x0 полагаем λ 0 =0. Для остальных вершин λ i =+ (i=1…,5). Затем ищем дугу, для которой λ j -λ 0 >l(x0,xj). Начнем с вершины x1. λ 1 -λ 0 =>l(x0,x1)=2 меняем метку вершины x1 на λ 1 =λ 0 +l(xo,x1)=2. Аналогично определяем метку вершины X2 λ 2 =λ 0 +l(xo,x2)=4. Чтобы найти изменившуюся метку вершины x3, следует воспользоваться формулой (*), т.к. в вершину x3 направлены две дуги, идущие из двух разных верши x0 и x1: λ 3 =min{[λ 1 +l(x1,x3)],[λ 0 +l(x0,x3)]}=min{(2+4),(0+5)}=5

Аналогично определяем новые метки для вершин x4 и x5: λ 4 =min{λ 1 +l(x1,x4),λ 3 +l(x3,x4)}=min{2+3,5+6}=5 λ 5 =min{λ 2 +l(x2,x5),λ 3 +l(x3,x5),λ 4 +l(x4,x5)}= =min{4+7,5+4,5+2}=7. Кратчайший путь из вершины x0 в x5 проходит через вершины x0,x1,x4,x5. Искомый путь µ есть (x0,x1,x4,x5); l(µ)=7.

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

Сети. Отношение порядка между вершинами ориентированного графа Ориентированный граф без циклов, имеющий одну вершину без входящих дуг (вход графа) и одну вершину без выходящих дуг (выход графа), называется сетью. В любом ориентированном графе без циклов можно установить отношение порядка между его вершинами. Вершина xi предшествует вершине xj, xi xj, если существует дуга из xi в xj. Это отношение порядка удовлетворяет аксиомам порядка: 1) если xi предшествует xj, то xj не предшествует xi; 2) если xi предшествует xj, а xj предшествует xk, то xi предшествует xk.

Правильная нумерация вершин графа заключается в том, что если xi предшествует xj, то номера i и j должны удовлетворять неравенству i

Задача о пути максимальной длины между двумя вершинами ориентированного графа в сетевом планировании Постановка задачи Задан конечный ориентированный граф без контуров G(X,U). Каждой дуге графа u ставится в соответствие длина дуги l(u). Требуется определить длиннейший путь, соединяющий две вершины графа x0 и xn и его величину (длину пути). Одну из основных задач сетевого планирования составляет отыскание путей максимальной длины между входом и выходом графа-сети.

Алгоритм Каждая вершина графа получает числовую метку, которая может меняться конечное число раз. Установившаяся метка – величина длиннейшего пути из вершины x0 в данную вершину xj. В частности, установившаяся метка вершины xn есть величина длиннейшего пути из x0 в xn. 1. Полагаем λ0 = 0; λi = - (i = 1,…,n). 2. Ищем дугу (xi, xj) такую, что λj-λi λj +l(xi,xj). Если такой дуги нет, то не существует пути, соединяющего x0 и xn. Если такая дуга найдется, то изменяем метку λj на λj=λj +l(x0,xj). или, если установлена «правильная» нумерация, то находим по формуле

Пример. Определим длиннейший путь на графе G, а также его длину. x0 - λ0=0 и λj=- для вершин xi (i=1,…,5). т.к. λ1-λ0=-

Путь максимальной длины называют критическим путем. Следовательно, критический путь в рассмотренном примере есть μ=(x0,x1,x3,x4,x5), а его длина l(μ)=14. Сетевое планирование. Скорейшее время завершения проекта Рассмотрим некоторый проект – совокупность операций (работ). Примером может служить строительство некоторого объекта. Считаем известными все работы, которые предстоит совершить, их последовательность и время. Проект может быть изображен в виде графа-сети. Зададимся целью определить кратчайший срок завершения проекта. Пусть данные о строительстве приведены в следующей таблице

Эту информацию о проекте представим в виде графа-сети. Дугами графа будем изображать работы, а вершинами графа – некоторые события. Назовем элементарными событиями начало и конец каждой работы, а некоторую совокупность элементарных событий – событием. Вход графа – событие, заключающееся в начале всего проекта. Оно является событием, стоящим в начале одной или нескольких работ, а именно тех, которые не следуют ни за какими другими, т.е. работ, с которых может быть начато строительство. (в примере 1,4,5 (их нет во 2-ом столбце)). Выходом графа будет являться событие, заключающееся в окончании работ, за которыми не следуют никакие другие работы, т.е. в окончании всего проекта (это работы 7,8,9). Все другие вершины графа есть события, заключающиеся в окончании одних и начале других работ

Номер работы обозначен числом вне кружка. Число, обведенное кружком, есть продолжительность данной работы. Вход графа, вершина x0 – начало проекта. Выход графа, вершина x5 – окончание проекта. Скорейшее время наступления события 5 есть скорейшее время окончания проекта в целом и равно длине пути максимальной длины из вершины x0 в x5. В приведенном примере критический путь, проходящий через вершины x0,x1,x3,x4,x5, имеет длину, равную 14 l(μ)=14, т.е. критическое время данного проекта равно 14. Работы, составляющие критический путь, называются критическими работами

Базы и антибазы База В графа есть множество вершин, из которого достижима любая вершина графа и которое является минимальным в том случае, что не существует собственного подмножества в В, обладающего таким свойством достижимости. Базой является такое множество В вершин графа G которое удовлетворяет следующим двум условиям: 1. каждая вершина графа G достижима хотя бы из одной вершины множества В; 2. в В нет вершины, которая достижима из другой вершины множества В. Сильная компонента (СК) графа G - подграф, 2-е любые несовпадающие вершины соединены маршрутом. В ориентированном графе существует одна и только одна СК, содержащая вершину Vi.

Антибаза В есть такое минимальное возможное множество вершин, что какова бы ни была вершина графа G, из нее достижима некоторая вершина в В. Сильная база Вр – объединение всех баз графа.