Файл: Diskretnaya_matematika.doc

а) монотонной функции, которая одновре­менно была бы линейной;

б) самодвойственной функции, кото­рая одновре­менно была бы линейной;

в) линейной и монотонной функций.

15. Покажите, что функции Шеффера и Пирса не явля­ются ни ли­нейными, ни монотонными, ни самодвойственными.

16. Докажите полноту системы функций  = {, ~ , 0}, состоящей из дизъюнкции, эквивалентности и константы 0.

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

На практике часто бывает полезно изобразить некоторую си­туацию в виде рисунков, составленных из точек (вершин), представ­ляющих основные ситуации, и линий (ребер), соединяющих опреде­ленные пары этих вершин и представляющих связи между ними. Таким способом удобно представлять структуру системы, в которой вершины – это блоки, а ребра – связи между блоками. Такие рисунки известны под общим названием графов. Графы встречаются в разных областях под разными названиями: «структуры» в гражданском строительстве, «сети» в электротехни­ке, «социограммы» в социологии и экономике, «молекулярные структуры» в химии и т.д. Удобны графы и при исследо­вании систем методом пространства состояний. В этом случае вер­шины – состояния системы, процесса, ребра – действия, которые могут изменить состояние. При решении оптимизационных задач вершинами могут быть предполагаемые решения, ребрами – прави­ла для их нахождения.

Начало теории графов как математической дисциплины было положено Эйлером в 1736 г., когда им была написана статья о Кенигсбергских мостах. Однако она была единственной в течение почти ста лет. Интерес к этой науке возродился около сере­дины XIXв связи с развитием естественных наук (исследования электрических сетей, моделей кристаллов и структур молекул), формальной логики. Кроме того, оказалось, что многие математические голово­ломки могут быть сформулированы в терминах теории графов.

Последние 35-40 лет ознаменовали новый период интенсив­ных разработок теории графов. Появились новые области прило­жения: системы телекоммуникаций, биология, психоло­гия и другие.

3.1. Основные определения

3.1.1. Общие понятия

Граф Gзадается множествомвершин(точек) Х = {х₁, ..., х_n} и множествомребер(линий) А = {а₁, .., а_n}, соединяющих между собой все или часть этих вершин. Таким образом, графGполностью определяется заданием двух множеств (Х, А).

Другое часто употребляемое описание графа состоит в задании множества вершин Xи соответствия (отношения)G, которое показывает, как ме­жду собой связаны вершины. То есть граф задается следующим об­разом.

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

Пример.Для графа, изображенного на рис. 3.1: множество вершинX= {х₀,х₁,х₂,х₃,х₄,х₅} и закон соот­ветствия между вершинами:

G(x ₀) = {x₁, x₂},

G(x₁) = {x₀, x₂, x₄},

G(x₂) = {x₀, x₁, x₅},

G(x₃) = {x₄},

G(x₄) = {x₁, х₃},

G(x₅) = {x₂},

G(x₆) = .

Рис. 3.1. Пример задания графа

Ребра графа– линии, соединяющие вершины, указывают на соответствие между вершинами в графе.

Запись g= (x_i,x_j) говорит, что реброgинцидентновершинам х_iиx_j, а вершины х_i,x_jинцидентныребруg. Две вершины х_i,x_jназы­ваютсясмежными, если они определяют ребро графа. Два ребра графа называютсясмежными, если их концы имеют общую верши­ну.

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

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

Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не прини­мается во внимание.

Ребро графа называетсяориентированным, если этот порядок существенен. В этом случае говорят, что для ребраg= (x_i,x_j):x_i– начальная,ax_j– конечная вершины ребра.

Ориентирован­ное ребро называют дугой графа (рис. 3.2).

Рис. 3.2. Дуга ориентированного графа

Граф называется неориентиро­ванным или неорграфом, если каждое ребро его не ориентированно, иориентирован­ным или орграфом, если каждое ребро его ориенти­рованно. Если граф содержит ори­ентированные и неориентирован­ные ребра, он называетсясмешанным.

Полным неориентированным графомназывается графU(X), ребрами которого являются всевозможные пары (x_i,x_j) для всех возможных вершинx_i,x_jX,ij. В таком графе все вершины являются смежными (рис. 3.3).

Рис. 3.3. Полные неориентированный и

ориентированный графы

Полным ориентированным графом U₀(X) называ­ется граф, у которого любые две вершины соединены хотя бы в одном направле­нии.

Петлей называется ребро g = (x_i, x_i), у которого начальная и конечная вершины совпадают (рис. 3.4) Петля обычно считается неориентиро­ванной.

Рис. 3.4. Петля

Мультиграфомназывается граф, в котором пара вершин соединяется несколькими различными ребра­ми или дугами (рис.3.5).

Рис. 3.5. Неориентированный и ориентированный мультиграфы

Дополнением графа G(X) является такой граф G_d(X), ко­торый совместно с графом G(X) образуют полный граф: U(X) = G(X)  G_d(X).

3.1.3. Маршруты в графах

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

Для неориентированных графов справедливы следующие понятия.

Цепь– последовательность реберS= (g₁,g₂, ...,g_n), в которой у каждого ребраg_kодна из вершин явля­ется вершиной ребраg_k-1, а другая - вершиной ребраg_k+1. При этом одно и то же ребро или вершина может встречаться несколько раз. Пример цепи для графа (рис. 3.6):

S = (g₀, g_l, g₂, g₃, g₄, g₅, g₂, g_б) = ((x₀, х₁), (х₁, х₂), (х₂, х₃), (х₃, х₁), (х₁, х₄), (х₄, х₃), (х₃, х₂), (х₂, х₅)).

Рис. 3.6. Пример цепи

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

Цепь назы­вается элементарной, если в ней ни одна из вершин не повторяется.

Циклом называется конечная цепь, начинающаяся на некото­рой вершине х_i, и окачивающаяся на ней же. Простые, сложные и элементарные циклы определяются по аналогии с цепями.

Для ориентированных графоввведены следующие дополни­тельные понятия.

Путемв графеG(X) называется такая последовательность дуг (g_l,g₂, …), что конец каждой предыдущей дуги является началом следующей. Существуют простые, сложные и элементар­ные пути.

Х|

Длина пути есть число дуг L(s) в последовательности дуг пути s. В случае бесконечного пути L(s) = .

Граф называетсясимметрическим,еслиx_i,x_j из того, чтоx_iG(x_j)x_jG(x_i), то есть две смеж­ные вершиныx_i,x_jвсегда соединены противоположно ориентирован­ными дугами (рис.3.7).

Рис. 3.7. Симметрический граф

Граф называется антисимметрическим, еслиx_i,x_j x_iG(x_j)x_jG(x_i), то есть каждая пара смежных вершин соединена только в одном направлении.

Граф называется конечным, если число его вершин конечно ибесконечным,если число вершин бесконечно. ГрафG(X) называетсяG – конечным, если для каждой его верши­ны хXмножествоG(x) конечно.

3.1.4. Частичные графы и подграфы

Граф Н(х) называется частичным для графа G(X), если все ребра Н(Х) являются ребрами G(X) и множество вершин графа Н(Х) совпадает с множеством вершин графа G(X), то есть Н(х)  G(x)  х  X (рис.3.8).

Рис. 3.8. Граф G(X) и частичный для него граф Н(Х)

Частичный граф содержит часть ребер(дуг). Он также может быть ориентированным или неориентированным в зависимости от исходного графа.

Отметим, что ноль-граф графа G(X) считается его частичным гра­фом. Все частичные графы Н(Х) дляG(X) можно получить, выбирая в качестве ребер Н(Х) всевозможные подмноже­ства множества ребер графаG(X).

ПодграфомG_A(A) графаG(X), где АX, называется граф, вершинами которого являются элементы множества АX, а ребра­ми ­– все ребра изG, концевые вершины которых лежат в А (рис.3.9).

Хо

Рис. 3.9. ПодграфG_A(A) графа G(X)

Таким образом, под­граф содержит часть вершинвместе с ребрами, со­единяющими эти вершины. Иначе,G_A(A) – подграф графаG(X), если АXиG_A(x) =G(x)Ах Х.

Если А = X, тоG_A(A) =G(X). Для единственной вершины А = {а} подграфG_A(a) со­стоит из петель вокруг а. Под­графомG_A(A) графаG(X) будет ноль-граф, если АXесть подмножество изолированных вершин графа.

Под­граф будет ориентированным или неориен­тированным в зависимо­сти от исходного графа.

Рис. 3.10. Частичный подграф Н_А(А) графа G(X)

Частичным подграфом Н_А(А), А  X графа G(X) называется подграф (рис. 3.10), ребрами которого являются некоторые ребра из G(X), оба конца которых лежат в А. Иначе, Н_А(А) – частичный под­граф графа G(X), если А  X и Н_А(х)  G(x)  A  х  Х.