ДМ_Конспект

Следствие

В импликации A B высказывание B называется следствием.

То же, что и заключение, консеквент.

Тавтология

Формула, которая принимает значение «истина» на всех интерпретациях (наборах значений переменных).

То же, что и тождественно истинная формула или общезначимая формула.

Теорема исчисления высказывания

Формула A называется теоремой исчисления высказывания (как аксиоматической теории), если в ней существует вывод, в котором последней формулой является A . Этот вывод называется выводом формулы A .

Терм

Любой аргумент предиката P(x1 , x2 ,...,xn ).

Тождественно истинная формула

Формула, которая принимает значение «истина» на всех интерпретациях (наборах значений переменных).

То же, что и тавтология или общезначимая формула.

Тождественно ложная формула

Формула, которая принимает значение «ложь» на всех интерпретациях.

То же, что и противоречивая формула или невыполнимая формула.

Универс

Множество значений M , которое может принимать x в предикате P(x) .

То же, что область определения предиката или предметная область.

Условие

В импликации A B высказывание A называется условием.

То же, что и антецедент, посылка.

Формула в логике высказываний

Сложное высказывание, которое можно построить из атомов с использованием логических связок.

То же, что и молекула.

Функциональный символ

Строчная буква латинского алфавита или осмысленные слова из строчных букв (например: минус( x, y ) – функциональный символ

« x y », отец ( x ) – функциональный символ «отец человека x »).

Эквиваленция высказываний A и B

Высказывание A ~ B , которое истинно тогда и только тогда, когда A и B либо оба истинны, либо оба ложны.

Элементарная формула логики предикатов

То же, что и атом.

Элементарное высказывание То же, что и атом, атомарная формула.

Язык исчисления высказываний

271

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

4. Элементы комбинаторного анализа

r-выборка

упорядоченная совокупность элементов вида: Pa Ei 1 , E j 2 ,..., En r

Композиция числа n

всякое представление n в виде упорядоченной суммы целых положительных чисел.

Неупорядоченная r-выборка

r-выборка с произвольным порядком размещения компонент. Обозначается

P , P ...

Перестановка Pn из n элементов (например, чисел 1,2,..., n )

всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n .

Правило произведения

Если дана последовательность k событий с n1 возможными исходами первого, n2 – второго, и т.д., вплоть до nk возможных исходов последнего, то общее число исходов последовательности k событий равно произведению n1 n2 ...nk .

Правило суммы

Если A и B – несвязанные события, и существует n1 возможных исходов события A , и n2 возможных исходов события B , то возможное число исходов

события « A или B » равно сумме n1 n2 .
Продуктивная функция
Если степенной ряд	a	a x a x2		... a xn ...	совпадает при некоторых	с
	0	1	2	n
функцией f (x) ,	то	f (x)	называется продуктивной функцией			для

последовательности a0 ,a1,a2 ,...,an ,....

Разбиение числа n

всякое представление n в виде неупорядоченной суммы целых положительных чисел.

Размещение Ank из n элементов по k

называется упорядоченный набор из k различных элементов некоторого n - элементного множества.

Сочетание Cnk из n по k

набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

272

Субфакториал (формула полного беспорядка)

представляется так:

D n! 1			1		1		1	...	( 1)n	,
n
		1!			2!		3!		n!
где выражение в [...] стремится к e 1 при неограниченном возрастании n .
Теорема о включениях и исключениях
Пусть имеется множество из N			объектов произвольной природы. На этом
множестве пусть задано n	свойств.				Каждый объект может обладать либо не

обладать некоторыми из этих свойств. Сами свойства обозначим: 1,2 ,...,n . Будем обозначать N (i ) – количество объектов точно обладающих свойствомi и может быть какими-то другими, а N (i , j ) – число объектов не обладающих ни свойством i , ни свойством j . Тогда число объектов, не обладающих ни одним из перечисленных свойств:

N (1,2 ,...,n ) N N (1) N (2 ) ...

N (n ) N (1 2 ) ... N (1 n ) N (2 3 ) ...N (n 1 n ) N (1 2 3 ) ... ( 1)n N (1 2 3... i )

Теоретико-множественное произведение (произведение r множеств

E 1 , E 2 , E 3 ,..., E r )

Множество всех выборок . Обозначается P E 1 E 2 E 3 ... E r .

5. Основы теории графов

Алгоритм Дейкстры (E.Dijkstra)

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

Алгоритм Краскала (J.B.Kruskal)

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

Алгоритм Прима (R.C.Prim)

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

Алгоритм Робертса-Флореса (S.M.Roberts, B.Flores)

алгоритм построения гамильтонова цикла, использующий технику поиска с возвратом.

273

Алгоритм Флери (Fleury)

алгоритм построения эйлерова цикла.

Алгоритм Флойда (R.W.Floyd)

матричный алгоритм определения кратчайших расстояний между всеми парами вершин в графе.

Антисимметрический граф (Anti-symmetric graph)

орграф, для которого выполнено следующее условие: если дуга (v,v) принадлежит орграфу, то в нем нет противоположно ориентированной дуги (v,v). Очевидно, что в А.г. нет петель.

Базис циклов (Cycle basis)

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

Бесконечная грань плоского графа (Unbounded face)

единственная неограниченная грань плоского графа. Другое название –

внешняя грань.

Биграф – то же, что и двудольный граф.

Бинарное дерево (Binary tree)

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

Другое название – двоичное дерево. Иногда под Б.д. просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. m-арное дерево.

Бихроматический граф (Bichromatic graph)

граф с хроматическим числом, равным 2. К бихроматическим графам относятся деревья и двудольные графы.

Величина потока (Value of a flow)

сумма дуговых потоков на дугах, исходящих из входа сети. Равна сумме дуговых потоков на дугах, заходящих в выход сети.

Величина разреза (Value of a cut)

сумма пропускных способностей дуг разреза. Другое название – пропускная способность разреза.

Вершина (Vertex)

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

Вершина, достижимая из a (Reachible from a vertex)

вершина в орграфе, для которой существует путь из a в нее.

274

Вершина изолированная (Isolated vertex)

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

Вершина, инцидентная ребру (Vertex incident to an edge)

одна из концевых вершин ребра.

Вершина конечная – см. Конечная вершина.

Вершина концевая (Terminal vertex)

одна из вершин a и b, соединенных ребром e = (a,b); для орграфа вершина b дуги e = (a,b); иногда концевые вершины ребра определяются с помощью инцидентора.

Вершина центральная (Central vertex)

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

Вес дуги (Weight of an arc)

число, приписанное дуге и играющее, например, роль длины дуги. В общем случае смысл веса должен оговариваться особо. См. для сравнения Пропускная способность дуги.

Взвешенный граф (Weighted graph)

граф (орграф), ребрам (дугам) которого приписаны веса. Иногда изображается в виде пары (G,w), где w – весовая функция, определенная на множестве ребер графа.

Висячая вершина (Terminal(pendant) vertex)

1.В неориентированном графе вершина степени 1.

2.В орграфе вершина с полустепенью захода, равной 1, и полустепенью исхода, равной 0.

Другое название – лист.

Внутренняя вершина (Inner vertex)

вершина дерева, имеющая сыновей, т.е. не являющаяся листом.

Высота вершины (в ордереве) (Height of vertex)

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

Высота дерева (Height of tree)

высота корня дерева (ордерева).

Гамильтонов граф (Hamiltonian graph)

граф, содержащий гамильтонов цикл или гамильтонову цепь, соединяющую некоторую пару вершин. К настоящему времени известны лишь достаточные условия гамильтоновости графов, принадлежащие В.Хваталу, О.Оре, Г.Дираку, Х.Уитни и др. Примерами гамильтоновых графов служат полные графы, графы каркасов, графы правильных многогранников. Слово "гамильтонов" в этом и других терминах связано с именем ирландского математика У.Гамильтона, который в 1859 г. предложил головоломку "Кругосветное путешествие", где требовалось обойти по ребрам все вершины додекаэдра.

Гамильтонов контур (Hamiltonian cycle)

контур, проходящий через каждую вершину орграфа в точности один раз.

275

Гамильтонов орграф (Hamiltonian directed graph)

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

Гамильтонов путь (Hamiltonian path)

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

Геодезическая цепь (Geodetic chain)

кратчайшая простая (v,w)-цепь. См. Кратчайший путь.

Гипотеза четырех красок (Graph colouring conjecture)

Каждый планарный граф 4-раскрашиваем. Первоначальная формулировка гипотезы гласит: любая карта на плоскости или на сфере может быть раскрашена четырьмя красками так, что никакие две смежные страны не были одного и того же цвета. Гипотеза имеет интересную историю, но в ее появлении остается много непонятного. Имеются сообщения, что Мебиус был знаком с этой проблемой в 1840 г., но точно известно лишь то, что о данной проблеме Гутри сообщал де Моргану примерно в 1850 г. Сформулировал гипотезу британский математик А.Кэли в 1879 г. в статье, посвященной проблеме раскраски карт в первом томе Трудов Лондонского географического общества. Первое из многих ошибочных "доказательств" было дано Кемпе в 1879г. Новую фазу в истории гипотезы открыло машинное доказательство Хакена и Апеля, появившееся в 1976г. Это доказательство не было принято математической общественностью и породило новую проблему – проблему методологии и корректности доказательств математических теорем с помощью ЭВМ.

Глубина вершины (Depth of a vertex)

длина пути из корня дерева в данную вершину.

Гомеоморфные графы (Homeomorphical graphs)

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

Грань (Face, facet)

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

Граф (неориентированный граф) (Graph (undirected graph)

1. Пара (V,E), где V – непустое множество объектов некоторой природы, называемых вершинами графа, а E – подмножество двухэлементных подмножеств множества V, называемых ребрами графа. Множества вершин и ребер графа G обозначают V(G) и E(G), соответственно. Если |V(G)| = n и |E(G)| = m, то говорят о (n,m)-графе G. 2. Пара (V,E), где V – множество вершин графа, а E – множество ребер – есть подмножество множества V / классов эквивалентности, на которые множество V = {(v,w) | v w } разбивается отношением эквивалентности:

276

(v,w) (v,w) (v,w) = (v,w) или (v,w) = (w,v)

3. Тройка (V,E,P), где V – множество вершин, E – множество объектов некоторой природы, отличной от природы вершин, называемых ребрами, P – инцидентор, сопоставляющий каждому ребру e E пару граничных вершин v и w из V. 4. Общее название как для неориентированного, так и для ориентированного графов.

Графы Куратовского (Graphs of Kuratowski)

графы K и K.

Двудольный граф (Bipartite graph)

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

полным двудольным.

Декартово произведение графов (Cartesian product of graphs)

граф = HH... H, множество вершин которого есть декартово произведение множеств вершин графов H и в существует ребро (v,w), где v = (v, ... , v) и w = (w, ... , w), тогда и только тогда, когда существует семейство ребер E = (v, w),..., E = (v, w), EH.

Дерево (Tree)

связный граф без циклов.

Диаметр (Diameter)

наибольшее расстояние между вершинами графа.

Длина цепи (Length of a chain)

(в невзвешенном графе) число ребер в цепи; (во взвешенном графе) сумма длин ребер.

Добавление ребра (Edge adding)

операция над графами, состоящая в соединении ребром e двух несмежных вершин графа G, порождая граф G + e.

k-дольный граф (k-partite graph)

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

Дополнение графа (Complementary graph)

граф G1, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G.

Достижимая вершина (Reachable vertex)

вершина w достижима из вершины v, если в орграфе существует путь из v в w.

Достижимое множество (Reaching set)

множество вершин, достижимое из заданной вершины.

Достижимость (Reachability)

бинарное отношение R на множестве вершин графа такое, что aRb тогда и только тогда, когда в графе существует путь из a в b.

Дуга (Arc)

277

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

Задание графа (Graph representation)

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

Задача китайского почтальона (Chinese postman's problem)

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

Задача коммивояжера (Traveling salesman problem)

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

Данная задача является NP-полной; для ее решения не существует эффективного алгоритма. Важность этой задачи связана с тем, что к ней сводятся многие другие задачи; в связи с чем она играет роль эталонной задачи.

Задача о кенигсбергских мостах (Koenigsberg's bridges problem)

задача обхода всех семи мостов города Кенигсберга (ныне Калининграда) таким образом, что каждый мост проходится в точности один раз. Задача была поставлена и решена Эйлером в 1736 г. в виде общей проблемы теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?

Замкнутый маршрут (Cycle)

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

Другое название – цикл.

Звездный граф (Starred graph)

полный двудольный граф K; в случае n = 3 используются названия "лапа" и "гроздь".

Изоморфизм графов (Graph isomorphism)

биекция : V(G) V(H) множества вершин графа G на множество вершин графа H, сохраняющая отношение смежности; другими словами, для любых вершин u и v графа G их образы (u) и (v) смежны в H тогда и только тогда, когда u и v смежны в G.

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

278

графы из разных классов не изоморфны. Задача установления изоморфизма графов есть NP-полная проблема.

Изоморфные графы (Isomorphic graphs)

графы, между которыми установлено отношение изоморфизма; другими словами, графы G и H изоморфны (G H), если существует изоморфизм графа G на граф H (и, следовательно, H на G.

Инцидентность (Incidenty)

отношение между ребром (дугой) и его концевыми вершинами, т.е. ребро e = (a,b) инцидентно вершинам a и b и вершины a, b инцидентны ребру e = (a,b).

Источник (Source)

1.То же, что и вход орграфа.

2.Вершина орграфа, из которой можно достичь все остальные вершины.

3.В теории потоков на сетях вершина, из которой потока выходит больше, чем заходит.

Каркас (Spanning tree)

для данного неориентированного графа суграф в виде дерева. Другие названия

– остов, остовное дерево, скелет, стягивающее дерево.

Клика (Clique)

подмножество V' графа G, в котором любые две вершины смежны, т.е. порожденный ими подграф G(V') является полным.

Кликовое число (Clique number)

число (G) вершин в наибольшей клике.

Другие названия – густота, плотность.

Код дерева (Code of a tree)

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

Кодерево (Cotree)

а) для заданного каркаса T – суграф в G, содержащий только те ребра графа G, которые не принадлежат T;

б) для данного графа G кодерево некоторого каркаса T.

Корень (Root)

некоторая выделенная вершина в графе (чаще в дереве).

Корневое дерево (Rooted tree)

дерево с выделенной вершиной – корнем.

Кратность ребра (Multiplicity of edge)

число ребер в мультиграфе, соединяющих две данные вершины.

Кратные дуги (Multiple arcs)

в ориентированном мультиграфе дуги, у которых общая начальная и общая конечная вершины.

Кратные ребра (Multiple edges)

279

в мультиграфе ребра, соединяющие одну и ту же пару вершин.

Кратчайший остов графа (Shortest spanning tree)

каркас (остов) взвешенного графа с наименьшей суммой весов ребер.

Кратчайший путь (Shortest path)

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

Кубический граф (Cubic graph)

регулярный граф степени 3.

Левостороннее дерево (Left linear tree)

бинарное дерево, определяемое рекурсивно следующим образом: а) одновершинное дерево есть Л.Д.;

б) бинарное дерево, у которого правое поддерево является пустым, а левое – Л.Д., есть также Л.Д.

Лемма о рукопожатиях (Handshake's lemma)

Сумма степеней всех вершин графа – четное число, равное удвоенному числу ребер.

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

Лес (Forest)

неориентированный граф без циклов. Компонентами связности леса являются деревья.

Лист (Leaf)

1. Максимальный связный подграф, не содержащий мостов. 2. Висячая вершина выходящего ордерева.

Маршрут (Sequence)

чередующаяся последовательность

a = v , e , v , e , ... , v, e , v = b

вершин и ребер графа такая, что e = (v ,v ), 1 i n. Говорят, что маршрут соединяет вершины a и b – концы маршрута. Очевидно, что маршрут можно задать перечислением лишь его вершин a = v , v , ... , v = b или его ребер e , e , ... , e. М. конечен, если число входящих в него ребер конечно, и бесконечен в противном случае. Бесконечный М., имеющий только одну концевую вершину (a или b), называется односторонне-бесконечным маршрутом; М. без концевых вершин называется двусторонне-бесконечным маршрутом.

Матрица весов (Weight matrix)

вариант матрицы смежности для взвешенного графа, представляет собой квадратную матрицу размером n n (n – число вершин), (i,j)-й элемент которой равен весу ребра / дуги (v , v), если таковое имеется в графе; в противном случае (i,j)-й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи.

280