Тема 3. Графы.

План:

1. Основные понятия теории графов.

2. Деревья,  лес.

3. Способы задания графов

4. Применения графов и сетей

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

Теоретически сведения

Теория графов – один из универсальных и нагляд­ных языков: графический, который применяется во многих облас­тях науки и техники.

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

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

1. Основные понятия теории графов.

Понятие графа

Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг. Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана еще в 1736 г. С помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, си­стемы различных бинарных отношений, структурные химические формулы и другие диаграммы и схемы.

Применяются графы для решения задач химии, экономики, электротехники и автоматики. Также они широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.

Графом G = (V, X) называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек

Примеры графов изображены на рисунке, где:

а – граф со смежными вершинами;              б – полный граф;

в – граф со смежными ребрами;                  г – граф  с петлей

Основные понятие графов и их определения

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

Если задан граф G = (V, X), то V – конечное непустое множество его вершин, X – множество его ребер.

Ребро называется  инцидентным по отношению к тем вершинам, которые оно соединяет.

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

Два ребра называются смежными, если они имеют общую вершину.

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

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

Если вершине инцидентна петля, то степень ее  равна двум: оба конца такого ребра приходят в эту вершину.

Вершина называется изолированной, если степень ее  равную нулю.

Граф на­зывается нуль – графом, если он состоит из изолированных вершин,.

Вершина графа называется висячей, если степень ее 1.

Терема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа. Эта теорема доказывается в других курсах математики.

Пример. Пусть граф содержит 5 ребер, тогда степень этого графа равна r=5·2=10

Вершина называется четной, если  ее степень есть четное число и нечетной, если степень ее есть нечетное число.

Теорема 2. Число нечетных вершин любого графа – четно.

Следствие. Невозможно начертить граф с нечетным числом нечетных вершин.

Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Примером полного графа есть рисунок 1б.

Полный граф опре­деляется только своими вершинами.

Степень любой вершины полного графа, очевидно, равна k= п – 1, где п – число его вершин. Число ребер этого графа равно числу сочетаний из п по 2, т. е. т = .

Дополнением графа G(V, X) называется граф G‘(V, X^‘), которой состоит из вершин первого графа и ребер, которые дополняют первый граф до полного графа. На рисунки показаны графы, которые дополняют друг друга до полного графа.

Граф называется ориентированный, если он состоит упорядоченных пар вершин (кортежи длины 2). Такой  граф называется  также направленным графом или орграфом.

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

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

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

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

Маршрутом называется последовательность попарно инцидентных вершин V₁, V₂, …, V_i неориентированного графа, т.е. последовательность ребер не­ориентированного графа, в которой вторая вершина предыдуще­го ребра совпадает с первой вершиной следующего.

Длиной маршрута называется число ребер этого маршрута.

Маршрут принято задавать как последователь­ность ребер, поскольку это более удобно при наличии кратных ребер.

Маршрут называется замкнутым или циклом, если начальная вершина маршрута совпадает с конечной,

Расстоянием между двумя вершинами называется минималь­ная длина из всех возможных маршрутов между этими вершина­ми при условии, что существует хотя бы один такой маршрут. Расстояние обозначается символами  d( A;B)= min|A;B|=k, где  вершины  A и B начало и конец маршрута, k – число, равное наименьшей длине маршрута.

Поскольку рассматриваются конечные графы, минимум мож­но найти всегда. Формально можно ввести расстояние d(VV) = О,  между любой вершиной и ей же самой, что соответствует нулевому маршруту, у которого начало и конец в одной вершине.

В маршруте одно и то же ребро может встретиться несколько раз.

Если ребро встретилось только один раз, то маршрут называ­ется цепью. Запись вида 3-цепь означает, что между двумя точками имеется  цепь – маршрут, длина которого равна 3.

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

•  направление каждой дуги должно совпадать с направлением пути;

•  ни одно ребро пути не должно встречаться дважды.

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

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

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

Две вершины называются связными, если существует маршрут между ними.

Понятно, что связность между вершинами является бинарным отношением. Это отноше­ние будет отношением эквивалентности. Оно: рефлексивно – каждая вершина (включая изолированные) связна сама с собой;  симметрично – любой маршрут  можно предста­вить в обратном порядке:; транзитивно – если существует маршрут  АB и маршрут BC, то существует маршрут AC.

Граф G можно разбить на непересекающиеся подмножества (графы) по признаку связности, которые называются подграфами.

Вершины одного множества являются связ­ными между собой, а вершины различных множеств – несвязны.

Все подграфы Vj (классы эквивалентности) графа G назы­вают связными компонентами, или компонентами связности. Связ­ный граф имеет одну компоненту связности.

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

Разработаны специальные алго­ритмы обхода ребер графа, которые можно использовать при ре­шении задач вида “поиска выхода из лабиринта”.

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

Ребро связного графа G на­зывается мостом, если после его удале­ния G станет несвязным и распадется на два связных графа G‘ и G“.

Теорема.4. Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.

Графы G‘ и G” называются изоморфными, если существует вза­имно-однозначное соответствие между их ребрами и вершинами, причем соответствующие ребра соединяют соответствующие вер­шины.

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

Изоморфизм графов является отношением эквива­лентности.

Это можно заметить исходя из свойств подста­новок. На практике такие различные по внешним признакам изо­морфные графы не различают, рассматривая их с точностью до изоморфизма.

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

Областью назовем подмножество плоскости, пересека­ющееся с планарным графом только по некоторому простому циклу графа, являющемуся границей области. На рисунке обозначены такие области: A,B,C.

Теорема .5 (Эйлера) Связный плоский граф с n вершинами и k ребрами разбивает плоскость на r областей (включая внешнюю), причем n – k + r =2.

На рисунке n=4, k=5, r=3, поэтому 4-5+3=2.

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

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

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

Теорема.6. Граф G является эйлеровым тогда и только тогда, когда G – связный граф, имеющий все четные вершины.

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

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

Путь графа на рисунке V₄V₁V₂V₅ – гамильтонов путь. Путь V₂V₄V₁V₂V₅ – не является  гамильтоновым путем

Граф, содержа­щий гамильтонов цикл, называется гамильтоновым.

T ф с мостами 2.2. Операции над графами

Над графами, как и над любыми множествами можно выполнять операции объединения и пересечения.

Объединением графов G₁ = (A;B) и G₂ = (C;D) называется граф G= G₁ U G₂, множество вершин которого К= AUC, а мно­жество ребер X=(BUD)

Пересечением графов G₁ = (A;B) и G₂ = (C;D) называется граф G= G₁∩G₂, множество вершин которого К= A∩C, а мно­жество ребер X=(B∩D).

Подграфом данного графа называется граф все вершины  и ребра которого являются подмно­жествами множества вершин и ребер этого графа.

Обозначения подграфа, его вершин  и ребер можно  так, как это принято для обозначения подмножеств или ввести другие буквы. А именно, если граф A=(N;M) есть подграф графа G=(V, X), то A ÌG, причем NÌV и MÌX

Кольцевой суммой G₁ = (A;B) и G₂ = (C;D) называется граф G= G₁ U G₂, множество вершин которого К= AUC, а мно­жество ребер X=(BUD)\ (B∩D).

2.3. Деревья. Лес. Бинарные деревья

Деревом называют конечный связный граф с выделенной вер­шиной (корнем), не имеющий циклов Вершины графа – дерева, называются узлами.

Для каждой пары вершин дерева – узлов - существует един­ственный маршрут, поэтому вершины удобно классифицировать по степени удаленности от корневой вершины. Расстояние до кор­невой вершины К₀ называется ярусом s вершины, s= d(V₀ V).

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

Каждая висячая вершина дерева называется его листом.

Каждая не висячая вершина дерева, содержит не менее двух ребер, которые часто  называются  поддеревьями.

Теорема 7. Граф является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

граф G(V, X) связен и не содержит циклов;

граф G(V, X) не содержит циклов и имеет п-1 ребро;

граф G(V, X) связен и имеет п-1 ребро;

граф G(V, X) не содержит циклов, но добавление ребра между несмежными вершинами приводит к появлению одного и только од­ного элементарного цикла;

граф G( У, X) связный, но утрачивает это свойство после удале­ния любого ребра;

в графе G(V, X) всякая пара вершин соединена цепью, и только одной.

Дерево с п вершинами имеет п-1 ребро, поэтому оно будет минимальным связным графом.

Висячие вершины, за исключением корневой, называются листьями.

Лесом называется граф, полученный в результате упорядоченного объединения не пересекающихся деревьев. Так, если   графы  A,S.D.F – деревья, то  граф G= A∪S∪D∪F есть лес

Компонентами связности леса являются деревья. Остовом связно­го графа G называется любой его подграф F, содержащий все вер­шины графа G и являющийся деревом (говорят: покрывающим его деревом»).

Если граф F есть остов леса G, то дополнения F’ до G является кодеревом.

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

При описании деревьев принято использовать термины: отец, сын, предок, потомок.

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

Очевидно, что узел без поддеревьев называется листом и является висячей вер­шиной.

Узел k-го яруса называется отцом узла (k+ 1)-го яруса, если они смежные.

Узел (k+ 1)-го яруса называется сыном узла k-ro яруса.

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

Вполне очевидно, что отца можно назвать предком, а сыновей – потомками.

Упорядоченным деревом называется дерево, в котором поддере­вья каждого узла образуют упоря­доченное подмножество.

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

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

Например для бинарного дерева можно указать, что  отец A, сыновья В и С, при­чем В – левый, а С – правый потомки ( по алфавиту и запись слева направо по строчке (ярусу дерева)

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

Бинарное дерево уровня п называется полным, если каждый его узел уровня п является листом, а каждый узел уровня мень­ше, чем n, имеет непустое левое и правое поддеревья.

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

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

Цикломатическим числом графа называется число v = m + c – n, где:

m – количество ребер;

c - количество связных компонент графа;

п – количество вершин.

Цикломатическое число дерева равно нулю. Цикломатическое число леса равно сумме цикломатических чисел составных связных компонент – деревьев и, следовательно, тоже равно нулю. Для остальных гра­фов цикломатические числа – положительные.

Например, для полного графа, имеющего пять вершин и 10 ребер цикломатическое число равно v = 10 + 1 – 5 = 6.

4. Способы задания графа. Изоморфные графы

Графы могут задаваться следующими способами:

1. Геометрическим способом – рисунки, схемы, диаграммы,

2. Алгебраическим способом – перечислением вершин и ребер,

3. Табличным способом.

4. Матричным способом.

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

Для машинной обработки удобнее за­дать граф в алгебраической форме – перечислением (списком) вершин или ребер.

При переходе от алгебраического способа к геометриче­скому одному и тому же графу могут соответствовать различные изображения – изоморфные графы, при этом от правильного изоб­ражения зависит, например, свойство плоской реализуемости. Для этого нужно правильно задать сам граф.

Основным способом задания графа является перечисление всех его вершин и ребер. Но такое представление, во-первых, несим­метрично (с ним трудно работать, особенно ЭВМ), во-вторых, для указания каждого ребра нужно еще раз выписывать соответ­ствующие вершины, что плохо с точки зрения сжатия и хранения информации.

При задании графа таблицей составляется таблица, состоящей из п строк (вершины) и т столбцов (ребра). На пересечении строк и столбцов пишутся соответствующие знаки, которые показывают отношение  (инцидентность) вершины и ребра. Это может быть знаки “+” и “-”, числа 0,1,-1 и др.

Главным во всех способах задания графа (диаграммой, матрицей, таблицей) является указание соответствия между множествами п вершин V_t к т ребер X-_t.

Пусть дан граф G(V, X), где V= {V₁, V₂ …V_n} – вершины, а Х= {Х₁, Х₂ .,., Х_m} – ребра, среди которых могут и кратные  ребра (есть  вершины, которые  соединяет несколько ребер).

Матрицей инцидентности данного графа будет таблица, состоящая из n строк (вершины) и т столбцов (ребра).

При рассмотрении неориентированного графа на пересечении строк и столбцов ставится число 1, если соответствующие вершина и ребро  инцидентны и ставится число 0,  они не инцидентны.

При рассмотрении ориентированного графа на пересечении строк и столбцов ставится число 1, если из  вершины выходит  соответствующее ее ребро.  Если в вершину входит ребро, то ставят число -1. Если вершина не инцидентна ребру и, то ставится число 0

Очевидно, что в каждом столбце матрицы инцидентности долж­но быть только два ненулевых числа, так как ребро инцидентно двум вершинам. Число ненулевых элементов каждой строки – сте­пень соответствующей вершины.

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

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

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

Хотя формально каждая вершина всегда смежная сама с собой, в матрице смежности мы будем ставить 0, если у нее нет петли, и 1, если есть одна петля.

Если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули.

Задание Составить таблицу и матрицу  инцидентности  для орграфа, изображенного на рисунке, который имеет 3вершины и  4 ребра.

Ответ.

Матрица  инцидентности

Таблица инцидентности орграфа

Вершины	Ребра
	s	t	г	и
V1	-1	0	1	0
V2	0	1	-1	1
V3	1	-1	0	-1

Задание Для графа, изображенного на рисунке записать таблицу и матрицу смежности

Ответ

Таблица смежности
Вершины	A	B	C	D
A	0	1	0	1
B	1	0	1	1
C	0	1	0	0
D	1	1	0	0

Матрица смежности

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

Сетевые модели представления информации и сети.

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

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

Например, последовательность работ для монтажа каркаса зда­ния изображена в виде графа, изображенного на рисунке

Числами обозначены технологические операции:

1  – рытье котлована;

2  – монтаж фундамента;

3  – завоз металлоконструкций;

4  – монтаж подъемного крана;

5  – монтаж каркаса здания.

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

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

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

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

Понятия, входящие в сети, можно описать с помощью фрейма.

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

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

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

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

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

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

6. Применение графов и сетей

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

Одним из первых применений сетевого изображения было создание аме­риканскими учеными баллистических ракет “Поларис” для ос­нащения атомных подводных лодок военно-морского флота США. В реализации этого грандиозного проекта участвовали 600 фирм из 48 штатов. Сам сетевой граф содержал 10000 событий.

В основе системы планирования и управления лежат в США система “Перт”, а в нашей стране – “СПУ”, широко и успешно применяющие графы, так как они позволяют обрабатывать на ЭВМ проекты с большим количеством событий.

С помощью графов-деревьев решают задачи планирования (де­рево целей, дерево переборов вариантов).

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

Примеры блок схем

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

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

Например, почтовый адрес представляет собой «путь в дереве», аналогичный административно-территориальному. В разделе “Кому” указывается страна, республика, область, район, населенный пункт, улица, дом, квартира.

Аналогично классифицируют объекты в любой науке. Получаемая классификация служит примером иерар­хической структуры. Например, в биологии: класс, отряд, семей­ство, род, вид.

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

Иногда связи между объектами образуют не дерево, но все же их можно представить в виде графа. Это бывает в тех случаях, ког­да, например, происходит подчинение не одному, а нескольким независимым службам (соподчинение между собой).

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

Задание. Изобразить с помощью блок-схемы иерархическое представление видов вычислительных машин. Вычислительные машины делятся на аналоговые, цифровые, комбинированные. Цифровые  машины делятся смешанные, оптоэлектрические, механические, электронные

Бинарный поиск.

Бинарные деревья применяются в информа­тике для одной из самых распространенных в прикладных науках операций – поиску. К нему прибегают, когда необходимо найти в некотором упорядоченном массиве (множестве) определенную информацию. Например, в телефонном справочнике – номер ка­кого-нибудь абонента, в словаре – определенное слово, в файле – сведения о зарплате сотрудников некоторого предприятия, сведе­ния о зарплате отдельного работника и т.д.

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

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

Пусть надо найти дубликаты всех чисел в некотором списке. Можно применить сравнение каждого числа с предшествующим на предмет «был – не был». Но тогда необходимо большое число сравнений. Использование бинарных деревьев (БД) укорачивает процедуру сравнения. Считывается новое число и помещается в узел – будущий корень нового БД. Каждое последующее число из списка сравнивается с числом в корне БД. Если эти значения со­впадают, то дубликат найден, если число меньше корня, то про­цесс продолжается в правом поддереве, если больше – в левом поддереве.

Различные виды графов и деревьев находят широкое приме­нение в учебном процессе. Поэтому первоначальные сведения о них необходимы для успешного обучения в различных областях, так как с их помощью часто передается учебная информация. Например, основные классы ЭВМ можно изобразить в виде гра­фа.

На процедуре бинарного поиска с использованием графа-дерева основана работа ЭВМ с базой данных. Информация о базе может быть представлена несколькими способами, в том числе матричным. Так называемые реляционные базы хранят различную информацию в форме таблиц, причем порядок строк и столбцов задается при вводе данных. В базах возможна дли­тельная работа с информацией, ее реорганизация и обновле­ние. С помощью автоматического поиска данных происходит их отбор на основании запроса по определенным характерным при­знакам.

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

Логикой называют науку о законах и формах правильного мыш­ления.

А разве можно научиться мыслить правильно? Что значит пра­вильное и неправильное мышление? Возможно ли постичь секреты идеально точных рассуждений?

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

Так ли уж важно определять новые понятия и требовать точно­сти формулировок?

На эти и другие неожиданные вопросы попытаемся ответить в следующей главе, которая приоткроет дверь в хранилище челове­ческой мудрости – первоначальные представления об основах логики как классической, так и математической. Причем связь между логикой и математикой не случайна: на протяжении двух с половиной тысячелетий они не только параллельно развивались, но и обогащали друг друга. Недаром над входом в философскую школу Платона – Академию – было начертано: «Пусть сюда не входит тот, кто не знает геометрии». Построение математики, в первую очередь геометрии, как точной науки, имеющей досто­верные выводы, дает возможность учиться на ее примерах логи­чески мыслить. И это делали еще древнегреческие философы. Зна­ние законов логики, философских законов, например диалекти­ки, помогает при изучении самой математики, так как способствует установлению предельно обобщенного, системного взгляда на отношения в окружающем мире как в природе, так и в обществе.

Практические задания

1. Решите задачи «о переправах», изобразите решение гра­фом.

1.  Три генерала – Строгий, Лихой и Грозный – со своими адъютантами переправлялись через реку с помощью двухместной лодки. Адъютант может либо перевозить своего генерала, либо пе­реправляться с другим адъютантом. Однако ни один из генералов не разрешил своему адъютанту ни оставаться с другим генералом вдвоем на берегу, ни переправляться с ним через реку. Как они переправились через реку?

2.  Трое мужчин и три женщины должны переправиться через реку. У них была одна лодка, которая вмещала только двух чело­век. Грести умели все мужчины и только одна женщина. Кроме того, женщины требовали, чтобы ни на одном берегу не остава­лось больше женщин, чем мужчин. Как им переправиться через реку?

3.  Муж, жена и двое детей должны переправиться на противо­положный берег реки при помощи лодки. Муж и жена весят по 100 кг, а дети – по 50. Как им быть, если лодка вмещает до 100 кг и каждый из них умеет грести?

4.  Человеку необходимо было переправить через реку с помо­щью лодки волка, козу и капусту. В лодке мог поместиться только человек, а с ним или волк, или коза, или капуста. Но если оста­вить волка с козой без человека, то волк съест козу, если оставить козу с капустой, то она съест капусту, а в присутствии человека никто никого не ел. Человек все-таки перевез через реку и волка, и козу, и капусту. Как он это сделал?

2. Задачи на поиск «фальшивой монеты» решите с помощью графов.

1.  Из 9 монет одна фальшивая (более легкая). Как двумя взве­шиваниями на чашечных весах определить фальшивую монету?

2.  Из 80 одинаковых по виду монет одна более легкая (фальши­вая). Как четырьмя взвешиваниями на чашечных весах определить фальшивую?

3.  Из 28 монет одна более легкая. Как при помощи 4 взвешива­ний определить ее?

4.  Из 27 монет одна более легкая. Как при помощи 3 взвешива­ний определить ее?

5.  Из 81 монеты одна более легкая. Показать, что 4 взвешива­ний достаточно, чтобы ее определить.

6. Из 82 монет одна более легкая. Какое наименьшее число взве­шиваний необходимо для определения этой монеты?

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

Требования к знаниям умениям и навыкам.

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