Элементы теории графов и их технические приложения: Учебно-методическое пособие. Часть 1

Федеральное агентство по образованию РФ. Тверской государственный технический университет Кафедра высшей математики

Пронькин Ю.С., Егоров Ю.А.

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

Учебно-методическое пособие для студентов технических специальностей. Часть 1

Тверь 2007

2

УДК 519.17 ББК 22.17

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

Элементы теории графов и их технические приложения. Учебно-методическое пособие для студентов технических специальностей. Часть 1. Составители: Пронькин Ю.С., Егоров Ю.А.

Технический редактор Комарова Г.В. Подписано в печать Физ.печ.л. 3,5 Усл.печ. л. 3,26 Уч.-изд. л. 3,05 Редакционно-издательский центр ТГТУ 170026, г. Тверь, наб. А.Никитина, 22 © Тверской государственный технический университет, 2007 © Пронькин Ю.С., Егоров Ю.А., 2007

3

Оглавление Введение ……………………………………………………………………… 4 стр. I. Графы – форма моделирования структур ……….………………………….. 4 стр. II. Графы и способы их задания 1. Графы. Различные типы графов……………………………………………. 6 стр. 2. Операции над графами ……………………………………………………. 12 стр. 3. Маршруты, циклы и связность …………………………………………… 14 стр. 4. Характеристики графов …………………………………………………….16 стр. 5. Представление графов с помощью матриц ………………………………. 17 стр. 6. Деревья ……………………………………………………………………….20 стр. 7. Полюсные графы 7.1 Физические системы с сосредоточенными компонентами ……………...23 стр. 7.2 Полюсные графы ..…………………………………………………………24 стр. 7.3 Электрические цепи ……………………………………………………….25 стр. 7.4 Механические поступательные системы ………………………………….27 стр. 7.5 Механические вращательные системы ……………………………………29 стр. 7.6 Пневматические системы …………………………………………………..31 стр. 7.7 Аналогии …………………………………………………………………….33 стр. 7.8 Нелинейные и параметрические компоненты …………………………….34 стр. 8. Многополюсные компоненты 8.1 Полюсный граф многополюсника ………………………………………....36 стр. 8.2 Уравнение многополюсника ……………………………………………….37 стр. 8.3 Электронная лампа ………………………………………………………….38 стр. 8.4 Транзистор …………………………………………………………………...39 стр. 8.5 Трансформатор ………………………………………………………………40 стр. 8.6 Механические многополюсники …………………………………………...41 стр. 8.7 Дифференциальный редуктор ……………………………………………. 43 стр. 8.8 Двигатель постоянного тока ………………………………………………..44 стр. 8.9 Гидромеханические многополюсники……………………………………...45 стр. 9. Задача о кратчайшем пути ……………………………………………………. 47 стр. 10. Кратчайший путь на ориентированном графе ……………………………….50 стр. 11. Постановка исследований оптимальных задач при наличии ограничений ..52 стр. 12. Понятие о сетевом планировании …………………………………………….54 стр. Литература ………………………………………………………………………. 57 стр.

4

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

I.

Граф – форма моделирования структур.

В инженерной практике рассматриваются технические системы, которые представляют собой комплекс взаимосвязанных технических средств, обеспечивающих преобразование массы, энергии и информации. Существенным элементом при этом является установление отношений между входами и выходами технических средств. Комплекс этих отношений и образует систему. Выделяют два типа отношений: отношения преобразования и отношения связей. Отношения преобразования включают отношения переработки (информации, массы, с изменением свойств материала (внутренней и внешней структуры), преобразование энергии) и отношения перемещения (изменение положения предмета по отношению к другим предметам). Отношение связи – это то, что объединяет функциональные элементы технической системы в одно целое. Они бывают только жесткими, т.е. не изменяющимися, в процессе функционирования системы. Через связи проходит интенсивный обмен веществом, энергией и информацией с окружающей средой и между элементами технической системы. Отношения связи отражают все взаимоотношения в технической системе и не обладают собственной материальной основой. F Под элементом системы будем понимать пару элементов I ⎯⎯→ О, где F характеризует преобразование. Рассмотрим блок-схему комплекса, в котором имеется несколько элементов, обеспечивающих ее действие в соответствии с отношением преобразований (при одновременном существовании отношения связей).

5

Рис. 1 Элементы от 1 до 5образуют комплекс, входящий как составная часть в совокупность С. Между действующим комплексом и этой совокупностью имеется отношение связи, которое обусловлено тем что вход Ос совокупности одновременно представляет собой и I. Отношение между комплексом и совокупностью раскрывает связь О5=Iс. Аналитическая запись отношений преобразований и отношений связей как комплекса, образующего систему выглядит следующим образом: Ос= I1 → O1=I12 → O2=I3 → O 13 =I5 → O5=Ic

↑ ↓ 11 I 2 =O4 ← I4=O 11 3 Рассмотренная система представляет собой последовательно-итерационный F комплекс, т.к. включает преобразование I4 ⎯⎯→ О4, дающее основу действия элемента 4 (случай обратной связи), характерного для автоматизированных комплексов. Действие элементов 2 и 4 оказывается сложным, поскольку в элементе 2 F F О2 и I 11 ⎯→ О2, где I 12 =О1; действие осуществляется на основе отношений I 12 ⎯⎯→ 2 ⎯ I 11 2 =О4. F F О 13 и I 3 ⎯⎯→ О 11 Для элемента 3 существует обратное явление I 3 ⎯⎯→ 3 , где

О 13 =I5; O 11 3 =I4. Для рассмотренной выше блок-схемы (рис. 1) используется еще одна форма записи – граф. В этой форме записи блоки соответствуют вершинам графа и

Рис. 2 обозначают отношения преобразований. Второй элемент графа - ребра (отрезки, соединяющие вершины) обозначают отношения связей. Можно построить обратный граф (рис. 3), в котором отношения

6

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

II.

Графы и способы их задания.

1. Графы. Различные типы графов. Многие прикладные задачи сводятся к рассмотрению совокупностей некоторых объектов, находящихся во взаимной связи и взаимодействии. Например, при изучении электрических цепей существенным может оказаться характер соединений различных ее компонентов; органические молекулы образуют структуры, характерными свойствами которых являются связи между атомами; различные связи и отношения между людьми, событиями, также могут представлять интерес. В подобных случаях принято, рассматриваемые объекты изображать точками, называемыми вершинами, а связи между ними – линиями (произвольной конфигурации), соединяющими их и называемыми ребрами. Графом называют множество вершин V, связи между которыми определены множеством ребер Е. Таким образом, граф G, обозначенный как G=(V,Е), представляет собой пару (V, Е), где V – непустое множество элементов, Е – некоторое подмножество множества V(2) всех его двухэлементных подмножеств. Будем рассматривать только конечные графы, т.е. предполагаем множество V конечным. Множество вершин графа G обозначим символом VG, а множество ребер графа G – символом ЕG. Вершины и ребра графа называются его элементами. Число |VG| вершин графа G называется его порядком и обозначается через |G|. Если |G|=n, |EG|=m, то G называют (n, m) – графом. Две вершины u и v графа называются смежными, если множество {u,v} является ребром; в противном случае вершины называются не смежными. Если е={u,v} – ребро, то вершины u и v называют его концами, а также, что ребро е соединяет вершины u и v. Такое ребро обозначается символом uv. Два ребра называются смежными, если они имеют общий конец. Вершина v и ребро е называются инцидентными, если v является концом ребра е ( т.е. е=uv), и не инцидентными в противном случае.

7

Следует иметь в виду, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами. Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается NG(v) или N(v). Обычно граф представляется диаграммой, состоящей из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии – ребрам. Часто эту диаграмму и называют графом. В качестве примера рассмотрим (5,6) граф (рис. 4). Для него множество вершин VG ={1,2,3,4,5} и множество ребер EG={{1,2}, {1,5}, {2,3}, {2,4}, {2,5}, {4,5}}. Вершины 1 и 2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро {1,2} инциденты. Окружение вершины 2 есть N(2)={1,3,4,5}.

Рис. 4 Граф G называется полным, если любые две его вершины смежны (соединены ребром). Полный граф порядка n обозначается символом Кn, число n(n − 1) . На рис. 5 изображены полные графы К1, К2, ребер в таком графе равно С n2 = 2 К3, К4, К5.

Рис. 5 Граф называется пустым, если в нем нет ребер. Пустой граф порядка n обозначается Оn. Для задания полного графа достаточно знать число его вершин. Набор подмножеств множества S называется покрытием множества S, если объединение этих подмножеств совпадает с S. Покрытие называется разбиением, если никакие два из входящих в него подмножеств не пересекаются. Граф называется двудольным, если существует такое разбиение множества его вершин на две части, что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из p и q вершин, обозначается символом Кp,q. При p=1 получаем звезду К1,q. На рис. 6 изображены звезда К1,5 и полный двудольный граф К3,3.

8

Рис. 6 Аналогично двудольным определяются К-дольный и полный К-дольный графы. Поскольку в применениях теории графов существенным является то, что есть объекты (вершины графа) и связи между объектами (ребра), граф является не геометрической, а топологической фигурой, определенные свойства которой инвариантны при взаимнонепрерывном и взаимнооднозначном пространственном преобразовании. Существенные инвариантные свойства графа отражают только число вершин, число ребер (дуг) и характер связей между вершинами. Так как граф является топологической фигурой, то один и тот же граф может быть изображен различными способами: вершины можно располагать в произвольном порядке, а соединяющие их ребра проводить в виде прямых или ломаных линий, информация, содержащаяся в графе, остается одной и той же. Оформим эти соображения в виде следующего определения: Пусть G и Н – графы, а ϕ : VG → VH – биекция. Если для любых вершин u и графа G их образы ϕ (u) и ϕ (v) смежны в Н, тогда и только тогда, когда u и v смежны в G, то эта биекция называется изоморфизмом графа G на граф H. Иначе говоря два графа называют изоморфными, если они имеют одинаковое число вершин и каждой паре вершин, соединенных ребром в одном графе, соответствует такая же пара вершин, которые соединены ребром в другом графе. Если существенные свойства графа не связаны со способом его изображения или нумерацией вершин и ребер, то изоморфные графы, обычно, не различают между собой. Изоморфизм графов G и Н обозначают следующим образом: G ≅ Н. Например, три графа, представленные на рис. 7 изоморфны между собой, так же как и два графа на рис. 8, а графы на рис. 9 не изоморфны.

Рис. 7

Рис. 8

рис. 9

9

Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным. Очевидно, что отношение изоморфизма графов является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т.е. считать совпадающими и изображать одним рисунком. В некоторых ситуациях приходится различать изоморфные графы и тогда вводится понятие «помеченный граф». Граф порядка n называется помеченным, если его вершинам присвоены некоторые метки. Например, номера 1,2,…,n. Отождествив каждую из вершин графа с ее номером, определим равенство помеченных графов G и Н одного и того же порядка условием: G=Н тогда, когда EG=ЕН. На рис. 5 изображены два равных помеченных графа. На рис. 10 изображены три разных помеченных графа. Чтобы подчеркнуть, что рассматриваемые графы различаются с точностью до изоморфизма, говорят: «абстрактный граф».

Рис. 10 Справедливо утверждение: число ln помеченных графов порядка n равно 2

2

Сn

.

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

Рис. 11 Очевидно, что G =G и G ≅ H , если G ≅ Н. Граф, изоморфный своему дополнению, называется самодополнительным. Иногда приходится рассматривать более общие объекты, чем определенный выше граф, в которых две вершины могут соединяться более чем одним ребром. Мультиграф – это пара (V,E), где V – непустое множество (вершин), а Е – семейство подмножества V(2) (ребер). В этом определении допускается существование кратных ребер. Дальнейшее обобщение состоит в том, что кроме кратных ребер допускаются еще петли, т.е. ребра,

10

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

Рис. 12 Часто связи между объектами характеризуются вполне определенной ориентацией. Например, на некоторых улицах допускается только одностороннее автомобильное движение, в соединительных проводах электрической цепи задаются положительные направления токов, отношения между людьми могут определяться подчиненностью или старшинством. Ориентированные связи характеризуют переход системы из одного состояния в другое, различные отношения между числами (неравенство, делимость). Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными ребрами – ориентированным графом (орграфом). Итак, ориентированный граф – это пара (V, А), где V – множество вершин, А – множество ориентированных ребер (дуг), А ⊆ V2 (V2 – декартов квадрат, состоящий из упорядоченных пар элементов множества V). Если а=(v1, v2) – дуга, то вершины v1 ее начало, а v2 – конец. Аналогично определяется ориентированный мультиграф. Рассматриваются также смешанные графы, у которых есть и дуги и неориентированные ребра. Для всех этих видов графов вводится понятие изоморфизма как биекции между множествами вершин, сохраняющей смежность, кратности ребер, петли и направления дуг. Направленный граф – это орграф, не имеющий симметричных пар ориентированных ребер, т.е. дуг вида (u, v) и (v, u). На рис. 13 приведены все орграфы с тремя вершинами и тремя дугами; два последних из них – направленные графы.

Рис. 13

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

11

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

Подграфы Граф Н называется подграфом (или частью) графа G, если вес его вершины и ребра принадлежит G: VH ⊆ VG, ЕH ⊆ ЕG. Если Н – подграф графа G, то говорят, что Н содержится в G. Подграф Н называется остовным подграфом (или фактором), если он содержит все вершины G: VH=VG. Если множество вершин подграфа Н есть U, а множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат U, то Н называется подграфом, порожденным (или индуцированным) множеством U, и обозначается через G(U). На рис. 14 изображен граф G и три его подграфа Н1, Н2 и Н3, среди которых Н3 является остовным, а Н2 – порожденным.

Рис. 14 Важный класс подграфов составляют подграфы, полученные в результате удаления вершин. Пусть v – вершина графа G. Граф Gv=G-v получается из графа G в результате удаления вершины v и всех инцидентных ей ребер. Очевидно, что

12

Gv=G(VG\v). Аналогично можно определить граф, полученный удалением или добавлением ребра. Обозначим соответствующие графы через G-x и G+х (рис. 15).

Рис. 15 Улам высказал предположение, что набор подграфов G-vi несет полную инфор мацию о всем графе G.

2. Операции над графами Естественно стремиться представить структуру рассматриваемого графа с помощью графов меньшего размера и более простой структуры. Одна такая операция уже была рассмотрена, это удаление вершины или ребра, а также переход к подграфу. Можно из имеющихся графов получить «большие» графы с помощью операции добавления ребра. Рассмотрим другие операции над графами. Объединение. Граф Н называется объединением (или наложением) графов F и G, если VH=VF ∪ VG и ЕH=ЕF ∪ ЕG, т.е. в Н объединяются множества вершин F и G и множество ребер. Обозначается H=F ∪ G. Аналогично определяется объединение любого конечного множества графов. Соединение графов, введенное Зыковым, обозначается F+G, состоит из F ∪ G и всех ребер, соединяющих вершины графов F и G. Операции объединения и соединения графов иллюстрируются на рис. 16.

Рис. 16

Произведение. Произведением двух графов G1=(V1, E1) и G2=(V2, E2) называется граф G=G1xG2, для которого VG=V1xV2 – декартово произведение множеств вершин исходных графов, а EG определяется следующим образом: вершины (u1, u2) и (v1, v2) смежны в графе G тогда и только тогда, когда или u1=v1, а u2 и v2 смежны в G2 или u2=v2, а u1 и v1 смежны в G1 (рис. 17).

13

Рис. 17

Композиция. G=G1[G2] также имеет VG=V1xV2 в качестве множества вершин и вершина u=(u1, u2) смежна с v=(v1, v2) тогда и только тогда, когда u1 смежна с v1 или u1=v1 и u2 смежна с v2. На рис. 17 справа показаны две композиции G1[G2] и G2[G1] и графов G1 и G2 представленных слева. Очевидно, что G1[G2] и G2[G1] не изоморфны. Если G1 и G2 – это (p1, q1) и (p2, q2) – графы соответсвенно, то для каждой из определенных выше операций можно найти число вершин и число ребер в получающемся графе (см. табл. ниже). Бинарные операции над графами Операция Число вершин Число ребер Объединение G1 ∪ G2 р1+р2 q1+q2 Соединение G1+G2 р1+р2 q1+q2+р1хр2 Произведение G1хG2 р1хр2 q1xq2+р2хq1 Композиция G1[G2] р1хр2 p1xq2+р 22 хq1 Отождествление (слияние) вершин. Пусть u и v – две вершины графа G, граф Н=G-u-v. К графу Н присоединим новую вершину v1, соединив ее ребром с каждой из вершин, входящих в объединение окружений вершин u и v в графе G. Говорят, что построенный граф получается из графа G отождествлением вершин u и v. Стягивание ребра. Эта операция означает отождествление смежных вершин u и v в графе G. На рис. 18 показаны граф G, и граф полученный из G стягиванием ребра {1,2}.

Рис. 18 Граф G называется стягиваемым к графу Н, если Н получается из G в результате некоторой последовательности стягивания ребер. Очевидно, что любой непустой связанный граф, отличный от К1, стягиваем к К2. Но уже не любой

14

связный граф стягивается к графу К3. Например, граф называемый простой цепью Р4, не стягивается к графу К3. Расщепление вершины – операция двойственная к операции стягивания ребра. Пусть v – одна из вершин графа G. Разобьем ее окружение произвольным образом на две части M и N и выполним следующее преобразование графа G: удалим вершину v вместе с инцидентными ей ребрами, добавим новые вершины u и w и соединяющее их ребро uw, вершину u соединим ребром с каждой вершиной из множества М, а вершину w- с каждой вершиной из множества N. Полученный граф обозначим символом G. Будем говорить, что G получается из графа G расщеплением вершины v (рис. 19).

Рис. 19

Операция удаления ребра. Эта операция позволяет обнаружить важные закономерности, свойственные графам. При удалении ребра (u, v) из графа G получается граф с теми же вершинами, что и граф G, и всеми ребрами, кроме ребра (u, v). (рис. 20)

Рис. 20

3. Маршруты, циклы и связность. Одно из наиболее простых свойств, которым может обладать граф, это свойство быть связным. Рассмотрим основные структурные свойства связных и несвязных графов. Маршрутом, соединяющим вершины v1 и vL+1 называется чередующаяся последовательность v1, e1, v2, e2, v3, e3, …, eL, vL+1 вершин и ребер графа, такая что еi=viхvi+1 (i=1,…,L). Эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Очевидно, что (v1 и vL+1) – маршрут можно задать последовательностью v1, v2,…,

15

vL+1 его вершин (наличие ребер подразумевается), а также последовательностью е1, е2,…, еL ребер. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины (а, следовательно, и ребра), кроме, возможно, крайних, различны. Маршрут называется циклическим, если v1=vL+1 (замкнутый маршрут). Циклическая цепь называется циклом, а циклическая, простая цепь – простым циклом (все его n вершин различны). Число n ребер в маршруте (v1, vn+1) называется его длиной. Простой цикл длины n называется n-циклом, 3-цикл часто называется треугольником. Длина всякого простого цикла не менее трех, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом, обозначается g(G). Окружение графа G (обозначается с(G)) – длина самого длинного простого цикла графа G. Эти понятия не определены, если в G нет циклов. Очевидно, что любую цепь графа можно рассматривать как его подграф. Рассмотрим некоторую цепь Р вида v1, v2,…, vL+1 графе G, vi и vj – входящие в нее вершины (i<j). Очевидно, что часть vi, vi+1,…, vj цепи Р, начинающаяся в вершине vi и заканчивающаяся в vj сама является цепью графа G и называется (vi, vj) – подцепью цепи Р.

Рис. 21 Для графа G, изображенного на рис. 21маршруты (1,2) и (1,2,4,7) являются простыми цепями; (1,2,4,7,8,4) – цепь не являющаяся простой; (1,2,4,7,8,4,2) – маршрут не являющийся цепью; (1,2,4,1) – простой цикл. Обхват этого графа g(G)=3. Для ориентированного графа вводится, аналогичным образом, понятие ориентированного маршрута. Аналогом цепи в этом случае служит путь (ориентированная цепь). Вершина v называется достижимой из вершин u, если существует (u, v) – путь. Контур – это конечный путь, у которого начальная и конечная вершины совпадают. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длины, образованный дугой вида (а, а), называется петлей. Петля связывает точку саму с собой. Замечание. Понятия ребра, цепи и цикла отличаются от понятия дуги, пути и контура только тем, что для последних принимается во внимание ориентация (направление). С понятием неориентированного графа связана важная характеристика, называемая связностью графа. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом (цепью или простой цепью). В силу того, что при u ≠ v произвольный (u, v) – маршрут, не являющийся простой цепью, после устранения «лишних кусков», превращается в простую (u, v)цепь, то верны следующие утверждения.

16

Утверждение 1. При u ≠ v всякий (u, v)-маршрут содержит простую (u, v)-цепь. Утверждение 2. Всякий цикл содержит простой цикл. Справедливы также: Утверждение 3. Объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл. Утверждение 4. Если С и Д – два несовпадающих простых цикла, имеющих общее ребро е, то граф (С ∪ Д) – е также содержит простой цикл. Для связанный графов очевидно следующее. Утверждение 5. Для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)-маршрут. Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. В этом понятии слово максимальный означает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности графа. Справедливо утверждение: каждый граф представляется в виде дизъюнктного объединения своих связных компонент. Разложение графа на связные компоненты определено однозначно. Некоторые проблемы (например, проблема изоморфизма) сводятся к случаю связных графов с помощью Утверждение 6. Для любого графа либо он сам, либо его дополнение является связным. Полезно также: Утверждение 7. Пусть G – связный граф, е∈ ЕG. Тогда: 1) если ребро е принадлежит какому-либо циклу графа G, то граф G-е связен; 2) если ребро е не входит ни в какой цикл, то граф G-е имеет ровно две компоненты. Обозначим через m(G) число ребер графа G, а К(G) – число его компонент. Возникает вопрос: сколько ребер может быть в графе порядка n с фиксированным числом К компонент. Ответ дает следующая теорема. Теорема.Если К(G)=к для n-вершинного графа G, то n-k ≤ m(G) ≤ (n-k)(n-k+1)/2, причем обе эти оценки для m(G) достижимы.

4. Характеристики графов. Рассмотрим некоторые важнейшие характеристики графов, полезные для их приложений, так как решение многих технических задач методами теории графов сводится к определению тех или иных характеристик графов. Циклическое число. Пусть G – неориентированный граф, имеющий n вершин, m ребер и r компонент связности. Циклическим числом графа G называют число ν =m-n+r Физический смысл этого числа заключается в том, что оно равно наибольшему числу независимых циклов в графе. При расчете электрических цепей цикломатическое число используется для определения числа независимых контуров.

17

Хроматическое число. Пусть р – натуральное число. Граф G называют рхроматическим, если его вершины можно раскрасить р различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р-хроматическим, называют хроматическим числом графа и обозначают γ (G). Если γ (G)=2, то граф называют бихроматическим. Необходимым и достаточным условием бихроматичности графа является отсутствие в нем циклов нечетной длины. Хроматическое число играет важную роль при решении задачи наиболее экономичного использования ячеек памяти при программировании. За исключением случая бихроматического графа, определение хроматического числа представляет собой довольно трудную задачу. Множество внутренней устойчивости. Множество S ⊆ V графа G=(V, E) называют внутренне устойчивым, если никакие две вершины из S несмежны, т.е. для любых u, v∈ S имеет место (u, v)∉ Е. Множество внутренней устойчивости, содержащее наибольшее число элементов, называют наибольшим внутренне устойчивым множеством, а число элементов этого множества – числом внутренней устойчивости графа G. Наибольшее внутреннее устойчивое множество играет важную роль в теории связи. Множество внешней устойчивости. Множество Т ⊂ V графа G=(V,E) называют внешне устойчивым, если любая вершина не принадлежащая Т, соединена дугами с вершинами из Т. Множество внешней устойчивости, содержащее наименьшее число элементов называют наименьшим внешне устойчивым множеством, а число элементов этого множества – числом внешней устойчивости графа G. Пример. Задача о пяти ферзях. Сколько ферзей достаточно расставить на шахматной доске так, чтобы каждая клетка доски находилась под ударом хотя бы одного из них? Эта задача сводится к отысканию наименьшего внешне устойчивого множества в графе с 64 вершинами (клетки доски), у которого (u, v)∈ Т тогда и только тогда, когда клетки u и v расположены на одной и той же горизонтали, вертикали или диагонали. Число внешней устойчивости β =5 для ферзей, β =8 для ладей, β =12 для коней, β =8 для слонов. Задача о восьми ферзях, которые нужно расставить на шахматной доске так, чтобы ни один из них не находился под ударом другого, сводится к нахождению наибольшего внутренне устойчивого множества, графа из предыдущей задачи. Существуют алгоритмы нахождения внутренне устойчивого множества и наименьшего внешне устойчивого множества (см. К.Берж. Теория графов и ее применения. М. 1962).

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

18

структурные особенности системы на язык чисел, фигурирующих в математических уравнениях. С каждым помеченным графом связаны несколько матриц, которые часто удается использовать при выявлении определенных свойств графа. Матрица смежности. Матрицей смежности А=(аij) помеченного графа G с n вершинами называется матрица порядка (nxn) с элементами ⎧1, если вершины i и j смежны, аij= ⎨ ⎩0, в противном случае Это симметрическая матрица с нулями по диагонали, в которой число единиц в стоке (сумма элементов матрицы А(G) по строкам) равно степени соответствующей вершины. Очевидно, что существует взаимно однозначное соответствие между помеченными графами с n вершинами и симметрическими бинарными (nхn) матрицами с нулями на диагонали. Бинарной называют матрицу, каждый элемент которой равен 0 или 1.

Рис. 22. Помеченный граф и его матрица смежности. Аналогично определяются матрицы смежности А мульти- и псевдографов: аij равно числу ребер, соединяющих вершины i и j (при этом петля означает два ребра). Также определяется матрица смежности А(G) ориентированного графа G: ⎧1, если дуга v i v j принадлежит G , аij= ⎨ ⎩0, в противном случае Очевидно, что любая квадратная бинарная матрица является матрицей смежности некоторого ориентированного графа.

Рис. 23. Ориентированный граф и его матрица смежности. Абстрактный граф приводит к различным матрицам смежности в зависимости от нумерации вершин. Пусть G и Н помеченные графы порядка (nxn) и G ≅ Н, т.е. G и Н различаются только нумерацией вершин, т.е. существует подстановка S на множестве вершин, сохраняющая смежность: вершины u и v тогда и только тогда смежны в G, когда их образы S(u) и S(v) смежны в Н. Следовательно, графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из

19

друга одинаковыми перестановками строк и столбцов. Это утверждение справедливо также для мультиграфов, псевдографов и ориентированных графов. Из предыдущего утверждения вытекает, что ранги матриц смежности изоморфных графов равны, что позволяет ввести для абстрактного графа следующее определение: рангом графа называется граф его матрицы смежности. Обозначать его будем через rang G. Пусть S – произвольная подстановка, действующая на множестве {1,2,…,n}. Определим бинарную nxn матрицу S, положив ⎧⎪1, если S( j) = i, Sij= ⎨0, в противном случае ⎪⎩ Очевидно, что в каждой строке и в каждом столбце матрицы S содержится ровно по одной единице и det S= ± 1. С помощью прямых вычислений проверяется, что B=SAS-1. Это означает, что матрицы смежности изоморфных графов подобны, поэтому равны характеристические полиномы этих матриц. Следовательно, корректно определение характеристического полинома графа как характеристического полинома его матрицы смежности. Спектр этой матрицы, т.е. совокупность корней характеристического полинома с учетом их кратностей, называется спектром графа.

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

Матрица инцидентности. Другой матрицей, связанной графом G, в котором помечены и вершины и ребра, является матрица инцидентности. Пусть G – (n, m) – граф, множество вершин VG={1,2,…, n} графа G, EG={e1, e2,…, em} – множество его ребер. Матрицей инцидентности помеченного графа G называется бинарная nхm – матрица J=J(G), элементы которой определяются условиями: ⎧1, если вершина k и ребро е l инцидентны, Jkl= ⎨ ⎩0, в противном случае

20

В каждом ее столбце ровно две единицы, равный столбцов нет.

Рис. 25. Граф и его матрица смежности А и матрица инцидентности J. Как и матрица смежности, матрица инцидентности определяет граф G с точностью до изоморфизма. Для ориентированных графов определение матрицы инцидентности J видоизменяется: ⎧1, если вершина k является началом дуги е l , Jkl= ⎪⎨− 1, если вершина k является концом дуги е l , ⎪ ⎩0, если вершина k и дуга е l не инцидентны.

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

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

21

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

Рис. 27 С увеличением числа вершин количество различных деревьев резко возрастает (например, при n=20 их насчитывается около миллиона). Среди рзличных деревьев выделяются два частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево, в котором одна из вершин (центр) смежна со всеми остальными вершинами. Рассматриваются также деревья с ориентированными ребрами (дугами). Ориентированное дерево называется прадеревом с корнем v0, если существует путь между вершиной v0 и любой другой его вершиной (рис. 28).

Рис. 28

Рис. 29. Исходный граф (а) и два возможных дерева (б и в). Для графа G с n вершинами и m ребрами следующие утверждения эквивалентны: 1) G – дерево; 2) G – связный граф и m=n-1; 3) G – ациклический граф и m=n-1; 4) Любые две несовпадающие вершины графа G соединяет единственная простая цепь; 5) G – ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. Из этих утверждений следует, что в любом дереве порядка n ≥ 2 имеется не менее двух концевых вершин.

22

Важное значение имеет такая точка зрения, когда деревья или лес являются частями некоторого графа, т.е. образуются из его ребер. Любая связная совокупность ребер, не содержащая контуров, вместе с инцидентными им вершинами образует дерево графа. Если такое дерево является суграфом (содержит все вершины графа), то оно называется остовом (каркасом) графа G. Очевидно, что в каждом графе существует остов: разрушая в каждой компоненте циклы, т.е. удаляя лишние ребра, придем к остову. Так как петля представляет собой простейший цикл, состоящий из одного ребра, то она не может входить в состав любого дерева графа. Ребра графа, которые принадлежат его дереву, называют его ветвями. Несложно показать, что число ребер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m(G)-|G|+k(G), где m(G) – число ребер, k(G) – число компонент графа G.

Рис. 30.Дерево как часть графа, а – исходный граф, б – дерево, в – остов. Выше было определено цикломатическое число графа G: ν (G)=m(G)-|G|+k(G) Справедливы утверждения: 1) Граф G является лесом тогда и только тогда, когда ν (G)=0; 2) Граф G имеет единственный цикл тогда и только тогда, когда ν (G)=1; 3) Граф, в котором число ребер не меньше, чем число вершин, содержит цикл. Остов минимального веса. Рассмотрим задачу, возникающую при проектировании линий электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры соединить некоторой системой каналов связи так, чтобы любые два центра были связаны либо непосредственно соединяющим их каналом, либо через другие центры и каналы, и чтобы общая длина (или, например, стоимость) каналов связи была минимальной. В этой ситуации заданные центры можно считать вершинами полного графа с весами ребер, равными длинам (стоимости) соединяющих эти центры каналов. Тогда искомая сеть будет кратчайшим остовным подграфом полного графа. Очевидно, что этот кратчайший остовный подграф должен быть деревом. Решение этой задачи простым перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n, поскольку полный граф Кn содержит nn-2 различных остовных деревьев. Однако имеются эффективные алгоритмы ее решения. Опишем алгоритмы Дж. Краскала и Р. Прима применимые к произвольному связному графу. Задача. В связном взвешенном графе G порядка n найти остов минимального веса. Алгоритм Краскала, решающий эту задачу, заключается в следующем.

23

1. Строим граф Т1=Оn+е1, присоединяя к пустому графу Оn на множестве вершин VG ребро е1∈ EG минимального веса. 2. Если граф Тi уже построен и i
Рис. 31 Построить для него остов минимального веса. Решение. Полагаем е1={1,4} – ребро минимального веса 1 (веса указаны рядом с ребрами), е2={4,5}. Среди оставшихся ребер минимальный вес имеют два ребра {1,5} и {2,3}. Однако первое не пригодно для построения, т.к. составляет цикл с двумя предыдущими ребрами, поэтому берем е3={2,3} и добавляем к нему ребро е4={2,5}. Итак, ребра {1,4}, {4,5}, {2,3}, {2,5} составляют остов минимального веса (рис. 28 (б)). Алгоритм Прима отличается от алгоритма Краскала тем, что на каждом этапе строится не просто ациклический граф, но дерево. 1. Выбираем ребро е1=аb минимального веса и строится дерево Т1, полагая VT={ab}, ET={e1}. 2. Если дерево Ti порядка i+1 уже построено и i
7. Полюсные графы 7.1. Физические системы с сосредоточенными компонентами. Для физических систем, допускающих идеалированное представление в виде схем с сосредоточенными компонентами широко используются структурные модели в форме графов. Соединение между собой компонентов таких систем осуществляется путем объединения их полюсов, образующих узлы схемы. В зависимости от числа полюсов различают двухполюсные и многополюсные компоненты, которые так и называют двухполюсниками и многополюсниками. Например, схема на рис. 32 представляет собой соединение двух трехполюсников (А и В), четырехполюсника (С) и трех двухполюсников (Д, Е, F).

24

Рис. 32 Типичными представителями физических систем такого типа могут служить электрические и электронные цепи, в которых резисторы, конденсаторы и катушки индуктивности являются двухполюсниками, а трансформаторы, электронные лампы, транзисторы – многополюсниками. Аналогичные компоненты можно выделить в системах различной физической природы: механических, акустических, гидравлических, тепловых и т.д. Для математического описания состава и структуры физической системы используются два типа соотношений: 1) полюсные уравнения, характеризующие индивидуальные свойства каждой компоненты вне возможных соединений с другими компонентами; 2) уравнения связей, отражающие характер соединения различных компонент в схеме вне зависимости к их индивидуальным свойствам. Уравнением двухполюсника служит функциональная зависимость между двумя физическими величинами, характеризующими его состояние (например, между током и напряжением электрического двухполюсника, силой и скоростью механического двухполюсника и т.п.). Многополюсник описывается системой уравнений, связывающей физические величины на его полюсах. Часто он представляется схемной моделью, состоящей из двухполюсных компонентов, каждый из которых описывается соответствующей функциональной зависимостью, в которой могут содержаться величины, связанные с другими компонентами схемной модели. В роли уравнений связи обычно выступают фундаментальные физические законы, выражающие условия равновесия и непрерывности ( законы Кирхгофа для электрических цепей, принцип Даламбера для механических систем и т.п.). Эти уравнения получают из рассмотрения структуры схемы, причем они должны содержать те же величины, что и полюсные уравнения, характеризующие состояние двухполюсников, обеспечивая совместность исходных уравнений, преобразование которых позволяет получить математическую модель системы в требуемой форме. 7.2. Полюсные графы. Схема, содержащая двухполюсные компоненты, может быть представлена полюсным графом, при этом, узлам схемы соответствуют вершины, а двухполюсникам – ребра графа. Ориентация ребра согласуется с направлением отсчета физических величин, характеризующих состояние двухполюсника.

25

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

Рис. 33 Полюсным графом любого двухполюсника служит дуга с двумя концевыми вершинами (рис. 33). Уравнение двухполюсника, в общем случае, содержит две переменные η и ξ : ϕ(η, ξ ) =0. Одна из них, например η , характеризует состояние двухполюсника относительно поперечного сечения и противоположно направлена к каждому из его полюсов. Такие переменные называют поперечными (например, электрический ток или магнитный поток, сила или момент, расход жидкости или газа, тепловой поток и т.п.). Другая величина ξ характеризует состояние двухполюсника относительно его полюсов (например, электрическое напряжение, линейная или угловая скорость, перемещение, давление, разность температур и т.п.). Такие переменные называют продольными и их направления связывают с направлением пути от одного полюса к другому. Поскольку из двух переменных η и ξ одна характеризует воздействие, а другая реакцию, то их положительные направления считают взаимно противоположными. Обычно направления дуг отождествляют с положительными направлениями отсчета поперечных переменных, а положительные направления отсчета продольных переменных принимают обратными ориентации дуг. Полюсный граф системы строится таким образом, чтобы обеспечивались наиболее простые отношения между его структурой и уравнениями связей. Обычно уравнения связей формируются для поперечных и продольных переменных в следующем виде: 1) алгебраическая сумма поперечных переменных для любой вершины графа равна нулю: ∑ η(t ) = 0 ; 2) алгебраическая сумма продольных переменных для любого контура графа равна нулю: ∑ ξ(t ) = 0 . При алгебраическом суммировании переменных они считаются положительными при совпадении их направлений с выбранным направлением относительно вершины или контура и отрицательными, если направления переменных противоположны с выбранными направлениями (рис. 34).

26

η 1- η 2+ η 3+ η 4- η 5=0 ξ 1- ξ 2+ ξ 3+ ξ 4- ξ 5=0 Рис. 34. Уравнения связей для вершины и контура.

7.3. Электрические цепи. Существуют три типа пассивных электрических двухполюсников: сопротивление, ёмкость и индуктивность. Пассивными они называются потому, что рассеивают или накапливают энергию. Сопротивление – компонент, в котором происходит необратимое преобразование электрической энергии в тепло. Зависимость между током (поперечная переменная) и напряжением (продольная переменная) может быть представлена в одной из двух форм: iR(t)=GUR(t) или UR(t)=RiR(t), где параметры G – проводимость, R – сопротивление (G=R-1 и R=G-1). Емкость – компонент, накапливающий электрическую энергию. Заряд q(t) связан с напряжением UС(t) на линейной емкости соотношением q(t)=CUC(t), где С – параметр, называемый емкостью. Ток iC(t) протекающий через емкость, выражается через производную заряда по времени, следовательно: iC(t)= dq(t ) = C duc (t ) ; dt

UC(t)= 1 ∫ i c (t )dt = S ∫ i c (t )dt , С

dt

-1

где S=C называют инверсной емкостью.

Индуктивность – компонент, накапливающий магнитную энергию. Магнитный поток ψ (t) линейной индуктивности пропорционален, протекающему в ней току iL(t), т.е. ψ (t)=LiL(t), где L – параметр, называемый индуктивностью. Напряжение UL(t) на индуктивности равно скорости изменения магнитного потока во

времени:

UL(t)= dψ (t ) = L di L (t ) ; dt

dt

iL(t)= 1 ∫ U L (t )dt = Г ∫ U L (t )dt , L

где

Г=L-1

инверсная индуктивность.

Рис. 35. Идеальные электрические двухполюсники: а – резистор; б – конденсатор; в – катушка индуктивности; г – источник напряжения; д – источник тока.

–

27

Источники энергии в электрических цепях представляются идеальными двухполюсниками двух типов. Источник напряжения – двухполюсник (рис. 35.г), напряжение в котором определяется некоторой функцией времени е(t) и не зависит от протекающего по нему тока, т.е. UE(t)=e(t). Источник тока – двухполюсник (рис. 35.д), ток в котором также определяется некоторой функцией времени j(t) и не зависит от приложенного напряжения, т.е. iJ(t)=j(t). Для построения графа электрической схемы достаточно ее узлы рассматривать как вершины, а каждый двухполюсник заменить ребром, сохраняя отношение инцидентности (рис. 36). Следует иметь в виду, что при изображении электрических схем линии означают проводники без сопротивления, и узлы, соединенные такими линиями, являются по существу одним узлом (узел f на рис. 36.а). Узлы, с которыми связаны только два двухполюсника, на схемах обычно не отмечаются (рис. 36.а, узел а). Направления дуг пассивных двухполюсников можно выбирать произвольно. Дуги активных двухполюсников ориентируются по направлению источника тока и противоположно направлению источника напряжения (направление дуги указывает на положительное направление тока и противоположно положительному направлению напряжения).

Рис. 36. Электрическая схема (а) и ее изоморфные графы (б и в). При построении графа удобно поступить следующим образом. Выделяется на схеме внешний контур и изображается замкнутой линией (например, окружностью), на которой размещаются соответствующие вершины. Затем граф дополняется теми ребрами и вершинами, которые отсутствуют во внешнем контуре (рис. 36.в, граф изоморфный графу б). Уравнения связей выражаются законами Кирхгофа, представляющими условие непрерывности для токов и условия равновесия для напряжений в любой момент времени t: 1) алгебраическая сумма токов для любой вершины равна нулю (первый закон Кирхгофа), т.е. ∑ i(t ) = 0 ; 2) алгебраическая сумма напряжений в любом контуре равна нулю (второй закон Кирхгофа): ∑ U(t ) = 0 .

28

7.4. Механические поступательные системы. Идеальные пассивные двухполюсники механических систем – механическое сопротивление, масса и упругость. Перемещение х(t) и скорость v(t) являются продольными переменными, а сила f(t)- поперечной переменной. Сопротивление отражает превращение механической энергии в тепло. В простейшем случае предполагается, что это превращение происходит в результате вязкого трения, сила которого fB(t) пропорциональна относительной скорости vB(t) dx (t ) 1 трущихся тел, т.е. fB(t)=B B = Bv B (t ) ; vB(t)= f B (t ) (В - параметр, называемый dt B механическим поступательным сопротивлением, а 1/В – инверсное сопротивление или податливость). Полюсы элемента сопротивления соответствуют твердым телам, между которыми имеет место вязкое трение. Масса – компонент, накапливающий кинетическую энергию и обладающий механической инерцией. Зависимость между силой инерции fm(t) и перемещением xm(t) или скорости vm(t) массы М относительно точки отсчета выражается dv (t ) d 2 x m (t ) 1 соотношениями: fm(t)=M = М m ; vm(t)= ∫ f m (t )dt , где 1/М называется 2 М dt dt инверсной массой. Один из полюсов компонента массы связан с движущимся телом, а другой – с неподвижной или равномерно движущейся системой координат. Упругость – компонент, накапливающий потенциальную энергию. Его можно представить как пружину, концы которой соответствуют его полюсам. В линейном случае предполагается, что такая пружина не обладает массой и сила fк(t) реакции пропорциональна относительному перемещению хк(t) ее концов. 1 df (t ) fk(t)=kxk(t)=k ∫ v k (t )dt , vk(t)= × k , где k называется жесткостью; 1/k – k dt гибкостью (рис. 37.в).

Рис. 37. Идеальные механические (поступательные) двухполюсники (а – сопротивление; б- масса; в – упругость; г – источник скорости; д – источник силы). Идеальные источники механической энергии могут быть двух типов. Задающая скорость u(t) какой-либо точки системы представляется источником скорости (рис. 37.г), один полюс которого связан с этой точкой, а другой – с той точкой системы, относительно которой эта скорость задается. Скорость такого двухполюсника не зависит от приложенных сил, т.е. vv(t)=u(t). Источник силы

29

изображается двухполюсником (рис. 37.д), полюсы которого соответствуют точкам приложения силы и ее реакции, причем сила определяется некоторой функцией времени ϕ (t) и не зависит от скорости, т.е. f ϕ (t ) = ϕ(t ) . На основе этих определений можно построить схему механической поступательной системы. При этом узлы схемы соответствуют соединениям компонент системы, которые могут рассматриваться как единое целое, а соединяющие линии – жестким связям между компонентами. Переход от механической схемы к ее графу осуществляется на основе соответствия между инцидентностью идеальных двухполюсников узлам схемы и инцидентностью дуг и вершин графа. Направления дуг для пассивных двухполюсников принимаются в соответствии с выбранной системой отсчета (противоположно направлению оси перемещений х), а ориентация дуг источников определяется заданными направлениями (для источников силы они совпадают, а для источников скорости – противоположны).

Рис. 38. Механическая поступательная система (а), ее схема (б) и граф (в). Например, в системе (рис. 38), движение которой может совершаться только по вертикали, платформа массой М3 движется с заданной скоростью u(t). Схема этой системы показана на рис. 38 б, а ее граф – на рис. 38 в. При навыке граф можно построить непосредственно из условного изображения механической поступательной системы без промежуточного вычерчивания ее схемы. Уравнения связей механической поступательной системы выражают условие равновесия сил и условие непрерывности для скоростей (или перемещений): 1) алгебраическая сумма сил для любой вершины равна нулю (принцип Даламбера): ∑ f (t ) = 0 ; 2) алгебраическая сумма скоростей (перемещений) в любом контуре равна нулю: ∑ v(t ) = 0 . 7.5. Механические вращательные системы.

Для механических вращательных систем справедлива аналогия с поступательными системами. Перемещению х(t) соответствует угол поворота ϕ (t), линейной скорости v(t) – угловая скорость ω (t), силе f(t) – вращающий момент μ(t). Соответственно, для механических вращательных систем имеются три пассивных

30

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

Рис. 39. Идеальные механические (вращательные) двухполюсники (а – вращательное сопротивление; б – вращательная масса; в – вращательная упругость; г – источник угловой скорости; д – источник момента). Вращательное сопротивление (рис. 39.а) характеризует рассеивание механической энергии в тепло за счет вязкого трения: dϕ ( t ) 1 μВ(t)=В B = BωB (t ) ; ω B (t ) = μ B (t ) , где В – крутильное сопротивление; 1/В – dt B инверсное сопротивление. Вращательная масса (рис. 39 б) характеризует кинетическую энергию вра2 1 щательного движения: μ I (t ) = I d ϕ I2(t ) = I dω I (t ) ; ω I (t ) = ∫ p I (t )dt , где I – момент

dt

dt

I

инерции. Вращательная упругость (рис. 39 в) – накапливает потенциальную энергию

вращательного движения: μk (t) = kϕk (t) = k∫ ωk (t)dt ; ω k (t ) = 1 × dμ k (t ) , где k – круk

dt

тильная жесткость, 1/k – гибкость. Идеальный источник может быть источником угловой скорости (рис. 39 г), характеризующимся задающей угловой скоростью ω(t ) , и источником момента (рис. 39 д), характеризующимся задающим моментом m(t). Рассмотрим пример построения схемы и графа механической вращательной системы (рис. 40). Узлы графа соответствуют вращающимся массам, а направления ребер принимаются в соответствии с выбранным положительным направлением отсчета угла поворота. Параметры I1 и I2 означают моменты инерции роторов, В1 и В2 – вязкое трение в опорах, К1 – жесткость вала.

Рис. 40. Механическая вращательная система (а), ее схема (б) и граф (в).

31

Уравнения связей выражают условие равновесия моментов и условие непрерывности угловых скоростей (или углов поворота): 1) алгебраическая сумма моментов для любой вершины равна нулю: ∑ μ(t ) = 0 ; 2) алгебраическая сумма угловых скоростей (углов поворота) в любом контуре равна нулю: ∑ ω(t ) = 0 .

7.6. Пневматические системы Движение газа в ограниченной среде характеризуется зависимостью между давлением Р(t) и потоком g(t), который выражается как количество молекул, проходящих в единицу времени. Используются три пассивные двухполюсные компоненты: сопротивление, инертность и упругость. Поток, при этом, рассматривается как поперечная величина, а давление (разность давлений) – как продольная величина. Сопротивление (рис. 41 а) – двухполюсник, учитывающий рассеивание энергии за счет вязкого трения. Его уравнение можно представить одной из двух форм: gR(t)=GPR(t); PR(t)=RgR(t), где G – пневматическая проводимость, R – сопротивление (G=R-1, R=G-1). Величина PR(t) представляет собой разность давлений на концах этого двухполюсника при потоке gR(t). Примерами пневматических компонент с явно выраженным сопротивлением являются трубки с тонкими отверстиями (капилляры), сужающие устройства (сопла), щели и различные препятствия на пути движения газа.

Рис. 41 Идеальные пневматические двухполюсники (а – сопротивление, бинертность, в – упругость, г – источник давления, д – источник потока). Инертность (рис. 41 б) является двухполюсником, характеризующим протииводействие изменению потока газа в среде, описывается соотношениями: dg (t ) 1 PL(t)=L L ; gL(t)= ∫ PL (t )dt , где параметр L называется пневматической инертL dt ностью; PL(t) представляет собой разность давления на концах этого двухполюсника при потоке gL(t). Пневматическая инертность заметно сказывается в трубопроводах при существенных изменениях потока газа во времени.

32

Упругость (рис. 38.в) – двухполюсник, характеризующий свойство идеального газа, заключенного в некотором объеме: изменение концентрации молекул пропорционально изменению давления (при условии, что процесс изотермический). dP (t ) Поскольку изменение концентрации определятся потоком газа, то gC(t)=C C ; dt 1 PC(t)= ∫ g C (t )dt , где С называется пневматической упругостью, PC(t) – давление C газа в объеме относительно давления, принимаемого за нулевое (атмосферного или вакуума). Поэтому один из полюсов этого двухполюсника связан с данным объемом, а второй – со средой, выбранной за начало отсчета давления. Существует аналогия между пневматическими и электрическими системами. Поток соответствует току, давление – потенциалу, разность давлений – напряжению, избыточная концентрация молекул (по сравнению с условным уровнем) – заряду. Поэтому соответствующие параметры пневматических и электрических двухполюсников обозначают одинаковыми буквами (R, L, C). Инертность называют пневматической индуктивностью, а упругость – пневматической емкостью. Источники энергии в пневматических системах представляются идеальными двухполюсниками двух типов: источником давления (рис. 41г) и источником потока (рис. 41 д), которые определяются соответственно давлением е(t) и потоком j(t), а также положительными направлениями этих величин. При построении схемы пневматической системы узлы соответствуют объемам газа с различными давлениями, причем один из них соответствует окружающей среде. На рис. 42 показан пример пневматической систем

Рис. 42 Пневматическая система (а), ее схема (б) и граф (в). Уравнения связей пневматической системы выражают условие непрерывности потоков и условие равновесия разностей давлений: 1) алгебраическая сумма потоков для любой вершины равна нулю: ∑ g(t ) = 0 ; 2) алгебраическая сумма разностей давлений в любом контуре равна нулю: ∑ p( t ) = 0 . Аналогичные соотношения применимы к акустическим и гидравлическим системам. 7.7 Аналогии. Для систем различной физической природы имеет место аналогия между их компонентами и переменными, характеризующими состояния систем. В связи с этим чаще всего в качестве основной принимают терминологию электрических

33

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

Поперечные Ток i(t) Заряд q(t) i(t)= q(t)=

dq (t ) dt

;

Переменные Продольные Напряжен Потокосцеплен ие u(t) ие ψ (t) U(t)=

∫ i(t )dt

dψ ( t ) dt

ψ ( t ) = ∫ U( t )

Идеальные двухполюсники Сопроти вление R I(t)=1/R U(t), U(t)=Ri(t )

Емкость С i(t)=C

Индуктивнос ть L i(t)=

dU(t ) , dt

1 ∫ U(t )dt L

U(t)=

Механиче ская поступате льная

Сила

Импульс силы

Скорость

Перемещение

Механиче ская вращатель ная Пневмати ческая

Вращающ ий момент

Импульс момента

Угловая скорость

Угол поворота

Молекуля рный поток

Концент рация молекул

Давление (разность давлений)

Импульс давления

Гидравлич еская

Объемный поток

Объем жидкост и

Давление (разность давлений)

Импульс давления

Тепловая

Теплоотда ча (тепловой поток)

Количес тво тепла

Температу ра (разность температу р)

-

Преобразов атель Трансформа тор

U(t)=L

1 ∫ i(t )dt С

di(t ) dt

Инверсн ое сопроти вление (демифе р) Инверсн ое сопртив ление Пневмат ическое сопроти вление

Масса (инертность)

Упругость (пружина)

Рычаг

Вращающаяс я масса (момент инерции) Пневматичес кая емкость (упругость)

Вращательна я упругость

Редуктор

Компрессор

Гидравл ическое сопроти вление Теплова я проводи мость

Гидоравличес кая емкость (резервуар)

Пневматичес кая индуктивност ь (инертность) Гидравлическ ая индуктивност ь -

Теплоемкость

Гидравличе ский преобразова тель -

7.8. Нелинейные и параметрические компоненты.

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

34

Рассмотрим основные соотношения для нелинейных и параметрических компонент в терминах электрических цепей. Зависимость, в общем случае, между током и напряжением резистивного компонента выражается соотношением ϕ (i,u)=0, которое может быть представлено одной из двух форм: i= ϕG ( U ) ; U= ϕ R(i). Первое соотношение описывает резистор (проводимость), управляемый напряжением и представляемый у-дугой, а второе – резистор (сопротивление), управляемый потоком и представляемый Z-дугой. Если характеристика монотонно возрастающая, то ее можно выразить однозначной функцией как тока, так и напряжения. Соответствующий двухполюсник является взаимоопределенным и представляется W-дугой. Нелинейные резистивные компоненты часто используются в квазилинейном режиме, при котором токи и напряжения изменяются относительно некоторой точки покоя (i0, u0), причем рабочий участок характеристики можно считать линейным, поскольку эти изменения достаточно малы. Разлагая функцию i= ϕ G (u ) в ряд Тейлора и ограничиваясь членом с первой производной, можно записать: i = ϕ G (u 0 ) + ϕ1G (u 0 )(u −u 0 ) = i 0 + ϕ1G (u 0 )(u − u 0 ) . Обозначая Δi = i − i 0 и Δu = u − u 0 - изменения тока и напряжения относительно точки покоя, предыдущие соотношения можно представить в виде: 1 di Δi = R D Δi . Величина G D = ϕ1G (u 0 ) = | u=u0 называется Δi = G D Δu ; Δ U = GD du динамической проводимостью, а обратная ей величина RD – динамическим 1 du = сопротивлением (RD= 1 | i = i 0 .) ϕ G (u 0 ) di Соотношения для параметрического резистора линейны, но его проводимость и сопротивление являются функциями времени, т.е. iG(t)=G(t)UG(t); UR(t)=R(t)iR(t). Нелинейный емкостный двухполюсник характеризуется зависимостью заряда от напряжения на этом двухполюснике q(t)=q(uC(t)). Дифференцируя по времени, получим выражение для тока в виде: du (t ) dq(t ) dq(u C ) du C (t ) = × = C(u C ) C , i C (t ) = dt du C dt dt где функция С(uC) определяет динамическую емкость, зависящую от приложенного напряжения uC. Емкость параметрического (линейного, но не стационарного) двухполюсника является функцией от времени. Поэтому, дифференцируя соотношение du (t ) d dC(t ) q(t)=C(t)uC(t) получим: i C (t ) = (C(t )u C (t )) = u C (t ) + C(t ) C . dt dt dt Нелинейный индуктивный двухполюсник можно охарактеризовать зависимостью потокосцепления от тока в индуктивности ψ(t ) = ψ(i L (t )) . Дифференцируя по di (t ) dψ (t ) dψ (i L ) di L (t ) времени имеем: U L (t ) = = × = L(i L ) L , где L(iL) определяет dt di L dt dt динамическую индуктивность, зависящую от протекающего тока iL. Так как индук-

35

тивность параметрического двухполюсника является функцией времени, то дифференцируя соотношение ψ (t ) = L(t )i L (t ) будем иметь: d dL(t ) di(t ) . U L (t ) = (L(t )i L (t )) = i L ( t ) + L( t ) dt dt dt Полученные соотношения можно рассматривать как аналоги нелинейных и параметрических двухполюсников любой физической природы, если понимать под входями в эти соотношения символами величины в соответствии с таблицей п. 7.7. Замечание. y-дугой называется дуга, соответствующая двухполюснику, уравнение которого представимо в явном виде относительно поперечной переменной η = f y (ξ) , при этом величину η можно рассматривать как реакцию на воздействие ξ . Аналогично, если уравнение двухполюсника представимо в виде ξ =fz(η), то соответствующая ему дуга называется z-дугой, причем величину ξ можно рассматривать как реакцию на воздействие η. Двухполюсники, допускающие описание относительно обоих переменных, называются взаимноопределенными, а соответствующие им дуги - w-дугами.

8. Многополюсные компоненты. 8.1.Полюсный граф многополюсника.

Многомерный элемент, имеющий m+1 полюсов, посредством которых он может объединиться с другими элементами, характеризуется m независимыми поперечными переменными η1, η2 , …,ηm и m независимыми продольными переменными ζ1 ,ζ2 ,…,ζm. Это связано с тем, что с каждым полюсом связана поперечная переменная, но поскольку их алгебраическая сумма равна нулю, то одна m из них зависима и выражается через остальные m переменных: ηm +1 = − ∑ ηi . i =1

Аналогично, каждая продольная переменная связана с парой полюсов и отображается соответствующим ребром. Совокупность ребер независимых переменных должна образовать дерево на множестве m+1 полюсов многополюсника. (рис 43б). Любое другое ребро, связывающее пару полюсов, образует с совокупностью ветвей дерева контур, и поэтому любая другая продольная переменная может быть выражена через некоторую совокупность m независимых продольных переменных. В качестве стандартного представления совокупности независимых переменных многополюсника удобно принять звездное дерево с центром в некотором полюсе, называемом базисным которому, присваивается обозначение О. Остальные вершины этого дерева нумеруются числами от 1 до m (рис. 43в).

36

Рис 43 Представление многополюсника (а-поперечные переменные; б-продольные переменные; в - полюсный граф; г - поперечные и продольные переменные соответствующие полюсному графу). Ветви дерева ориентируются одинаково относительного базисного полюса; чаще всего они направляются к базисному узлу, что соответствует направлению поперечных переменных внутрь многополюсника и продольных переменных – от базисного полюса к соответствующим полюсам (рис 43г). Таким образом, с каждым не базисным полюсом связаны продольная и поперечная переменные, которые нумеруются теми же числами, что и соответствующий полюс, и называются полюсными переменными. Каждая ветвь полюсного графа (рис 43в) характеризуется соответствующим уравнением системы m уравнений, связывающих независимые поперечные и продольные переменные многополюсной компоненты. Если продольные переменные заданы произвольным деревом, то они легко могут быть выражены через полюсные переменные. Например, для продольных переменных пятиполюсника (рис 43б) при базисном узле 5 имеем: ξ1 = ξ'2 –ξ'1 ; ξ2 =ξ'3 -ξ´2 ; ξ3 =ξ'4 -ξ'3 ; ξ4 = -ξ'4 , где штрихами отмечены полюсные переменные. 8.2 Уравнение многополюсника.

Для описания линейной компоненты с m+1 полюсами используются три различные формы соотношений, называемых полюсными уравнениями. Уравнения, записанные относительно поперечных переменных, имеют вид: ⎧ η1 = y11 ξ1 + y12 ξ2 + ... + y1m ξm ⎪ ⎪ η2 = y 21 ξ1 + y 22 ξ2 + ... + y 2m ξm ⎨ ⎪− − − − − − − − − − − − − − − − − − − − ⎪ η = y ξ + y ξ + ... + y ξ m 2 m ⎩ m1 1 m2 mm

Или в матричной форме η = y ⋅ ξ , где η = (η1, η2, ..., ηm ) - вектор поперечных переменных; ξ = (ξ,1 ξ2, ..., ξm ) - вектор продольных переменных ( в уравнении они входят в форме столбцевых матриц); Y – квадратная матрица.

37

⎛ y11 y12 ... y1m ⎞ ⎜ ⎟ ⎜ y 21 y 22 ... y 2 m ⎟ Y=⎜ − − − − − − − −⎟ ⎜ ⎟ ⎜ y y ... y ⎟ ⎝ m1 m 2 mm ⎠

Уравнения, записанные относительно продольных переменных, имеют вид: ⎧ ξ = Z η + Z η + ... + Z η ⎪ ⎪ ξ = Z η + Z η + ... + Z η 1

11

1

21

1

12

2

22

2

1m

2m

m

⎨ ⎪− − − − − − − − − − − − − − − − − − − ⎪ ξ = Zm1 η + Zm 2 η + ... + Zmm η ⎩ m 1 2 m 2

m

Или в матричной форме ξ = Z ⋅ η , где Z- квадратная матрица ⎛ Z Z ... Z ⎞ ⎟ ⎜ ⎜ Z Z ... Z ⎟ Z= 11

12

1m

21

22

2m

⎜− − − − − − − −⎟ ⎟ ⎜ ⎟ ⎜ ⎝ Zm1 Zm 2 ... Zmm ⎠

Матрицы Y и Z однозначно характеризуют многополюсник относительно принятой нумерации полюсов и выделенного базисного полюса и являются его обобщенными параметрами. Между ними существует очевидная зависимость Y=Z-1 ; Z=Y-1 , означающая, что каждая из матриц неособенная. Если же одна из них особенная, то вторая не существует. В смешанной форме часть уравнений выражены относительно продольных переменных, объединенных в вектор ξ', а остальная часть - относительно поперечных, объединенных в вектор η´´

⎛ ξ ′ ⎞ ⎛ H11 ⎜⎜ ⎟⎟ = ⎜⎜ ⎝ η′′ ⎠ ⎝ H 21

H H

⎞⎛ η′ ⎞ ⎛ η′ ⎞ ⎟⎟⎜⎜ ⎟⎟ = H⎜⎜ ⎟⎟ , где H- блочная ξ ′′ ⎠ ⎝ ξ ′′ ⎠ 22 ⎠⎝

12

матрица, записанная через субматрицы H11, H12, H21 , H22. Решив это уравнение −1 −1 ⎞⎛ ξ′ ⎞ , − H11 H12 относительно векторов η′ и η′′ получим, ⎛⎜ η′ ⎞⎟ = ⎛⎜ H11 ⎟⎜ ⎟ −1 ⎜ η′′ ⎟ ⎜ ⎝ ⎠ ⎝ H21 H11

H

22

−1 − H21 H11 H12 ⎟⎠⎜⎝ ξ′′ ⎟⎠

что равносильно уравнению η =Y ξ . Для матрицы Y, таким образом, получается соотношение через блоки матрицы H: ⎛ H11−1 Y = ⎜⎜ −1 ⎝ H21 H11

−1 ⎞ − H11 H12 ⎟ −1 − H 22 H 21 H11 H12 ⎟⎠

Аналогично для матрицы Z находим −1 ⎛ ⎞ Z = ⎜⎜ H11 − H12−1 H22 H21 H H ⎟⎟ − H22 H21 H ⎠ ⎝ Дуга полюсного графа описывается уравнением относительно связанной с ней поперечной или продольной переменной. В отличие от дуги двух полюсной компоненты, правая часть уравнения дуги многополюсника может содержать любые переменные, связанные с дугами этого графа. Рассмотрим полюсные графы и уравнения наиболее часто встречающихся многополюсных компонент. −1

12

22

−1

22

38

8.3 Электронная лампа

Идеальный электровакуумный триод в квазилинейном режиме без сеточных токов при выборе катода в качестве базисного полюса представляется полюсным i1 = 0 , где графом с двумя дугами (рис 44), уравнение которых ⎧⎨ ⎩i 2 = SU1 + G i U2

параметры называют S-крутизной, Gi- внутренней проводимостью.

Рис. 44 Электронная лампа (а) и ее полюсный граф (б) Дуга 1 полюсного графа отображает двухполюсник с бесконечно большим сопротивлением (разомкнутая дуга) и ее роль сводится к фиксированию напряжения U2 между сеткой и катодом триода. Уравнение дуги 2 можно представить в виде: U2 = − S U1 + 1 i2 = − rU1 + Ri i , где r = S - статический коэффициент усиления;

R= i

G

1

G

i

G

G

i

i

- внутренне сопротивление. Для идеального электровакуумного триода Y-

i

⎛0 матрица является особенной Y = ⎜⎜ ⎝S существует.

0 ⎞ ⎟ поэтому Z-матрица для него не Gi ⎟⎠

Рис 45 Схема с электронными лампами (а) и ее граф (б). В качестве примера, приведена схема с двумя электронными лампами ( рис 45а) и ее граф (рис45б) где первый триод представлен дугами 1' и 2', а второй 1´´и 2´´. Дуги полюсных графов и источника напряжения имеют строго определенную ориентацию, а дуги пассивных двухполюсников ориентированы произвольно. 8.4 Транзистор

Уравнения низкочастотного транзистора (рис. 46) в квазилинейном режиме обычно представляются в трех формах:

39

⎛ i 1 ⎞ ⎛ g 11 ⎜⎜ ⎟⎟ = ⎜⎜ ⎝ i 2 ⎠ ⎝ g 21

g 12 ⎞⎛ u 1 ⎞ ⎟⎜ ⎟ ; g 22 ⎟⎠⎜⎝ u 2 ⎟⎠

⎛ u 1 ⎞ ⎛ r11 ⎜⎜ ⎟⎟ = ⎜⎜ ⎝ u 2 ⎠ ⎝ r21

r12 ⎞⎛ i 1 ⎞ ⎟⎜ ⎟ ; r22 ⎟⎠⎜⎝ i 2 ⎟⎠

⎛ u 1 ⎞ ⎛ h 11 ⎜⎜ ⎟⎟ = ⎜⎜ ⎝ i 2 ⎠ ⎝ h 21

h 12 ⎞⎛ i 1 ⎞ ⎟⎜ ⎟ h 22 ⎟⎠⎜⎝ u 2 ⎟⎠

Рис.46 Транзистор (а) и его полюсные графы при выборе в качестве общего полюса эмиттера (б), базы (в) и коллектора (г). Им соответствуют три системы параметров, которыми служат матрицы g, r, h этих уравнений. Переход от одной системы параметров к другой осуществляется следующим образом: g12 ⎞ 1 ⎛ r22 − r12 ⎞ 1 ⎛ 1 − h12 ⎞ ⎛g ⎜⎜ ⎟⎟ ; ⎟⎟ = ⎜⎜ ⎟⎟ = g = ⎜⎜ 11 h h g g r r − r h ⎝ 21 ⎝ 21 22 ⎠ 11 ⎠ 11 ⎝ 21 ⎠ r ⎞ 1⎛ g − g 12 ⎞ 1 ⎛ h h 12 ⎞ ⎛r ⎜⎜ ⎟⎟ ; ⎟⎟ = r = ⎜⎜ 11 12 ⎟⎟ = ⎜⎜ 22 r r g g − g h h − 1 ⎝ 21 ⎝ 21 22 ⎠ 11 ⎠ 22 ⎝ ⎠ 21 h 12 ⎞ 1 ⎛ 1 − g 12 ⎞ 1 ⎛ r r12 ⎞ ⎛h ⎜⎜ ⎟⎟ = ⎟, ⎜⎜ ⎟⎟ = h = ⎜⎜ 11 g ⎠ r22 ⎝ − r21 1 ⎟⎠ ⎝ h 21 h 22 ⎠ g 11 ⎝ g 21

где g , r и h обозначены определители соответствующих матриц. В зависимости от того, какой из трех полюсов транзистора выбран базисным, имеем три типа полюсных графов: с общим эмиттером (рис. 46 б), с общей базой (46 в), с общим коллектором (46 г). Для описания дуг каждого из этих полюсных графов пригодна любая из трех форм уравнений.

Рис. 47. Транзисторная схема (а) и ее граф (б).

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

40

8.5 Трансформатор

Простейший трансформатор представляет собой две индуктивно связанные катушки (рис. 48 а), полюсные уравнения которые в линейном приближении имеют вид: di 1 di 2 ⎧ ⎪ u1 = L1 dt + M dt , ⎨ di di ⎪u 2 = M 1 + L 2 2 dt dt ⎩

где L 1 и L 2 - индуктивности катушек; M - взаимная индуктивность.

Рис. 48. Трансформатор (а), его полюсный граф (б) и идеальный трансформатор (в)

Величина M входит в эти уравнения со знаком плюс, если токи в катушках одинаково направлены относительно одноименных полюсов и со знаком минус, если токи относительно одноименных полюсов направлены противоположно (обычно одноименные полюсы отмечаются жирными точками) Представив каждую катушку ее полюсным графом (дугой), получим полюсный граф трансформатора, который состоит из двух топологически несвязанных дуг (рис. 48 б). Полюсные уравнения трансформатора можно представить в операторной форме следующими способами: ⎛i ⎞ ⎛ u1 ⎞ ⎛ pL 1 pM ⎞⎛ i 1 ⎞ ⎟⎟⎜⎜ ⎟⎟ = Y⎜⎜ 1 ⎟⎟ ; ⎜⎜ ⎟⎟ = ⎜⎜ ⎝i2 ⎠ ⎝ u 2 ⎠ ⎝ pM pL 2 ⎠⎝ i 2 ⎠

⎛ i1 ⎞ ⎛ L 2 − M ⎞⎛ u1 ⎞ ⎛u ⎞ 1 ⎜⎜ ⎟⎟ = ⎜ ⎟⎟⎜⎜ ⎟⎟ = Ζ⎜⎜ 1 ⎟⎟ ; 2 ⎜ ⎝ i 2 ⎠ p(L1L 2 − M ) ⎝ − M L1 ⎠⎝ u 2 ⎠ ⎝u2 ⎠ ⎛ L1L 2 − M 2 M ⎞ ⎜p ⎟ ⎛ u1 ⎞ ⎜ ⎛i ⎞ L2 L 2 ⎟⎛ i 1 ⎞ ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ = H⎜⎜ 1 ⎟⎟ 1 ⎟⎝ u 2 ⎠ M ⎝ i2 ⎠ ⎜ ⎝u2 ⎠ − ⎜ ⎟ L2 pL 2 ⎠ ⎝

Квадратные матрицы Y, Z, H в этих уравнениях являются обобщенными параметрами трансформатора. Для характеристики трансформаторов используются L1 M также две величины: K = - коэффициент связи и n = - коэффициент L2 L1L 2 трансформации. Из физических соображений следует, что k 2 < 1 . В предельном случае при k = 1 говорят о полной связи, причем уравнения трансформатора 0 n ⎞ i ⎛ u 1 ⎞ ⎛⎜ 1 ⎟⎛⎜ 1 ⎞⎟ и представляют модель совершенного преобразуются к виду ⎜⎜ ⎟⎟ = − n ⎟⎜ ⎟ ⎝ i 2 ⎠ ⎜⎝ pL 2 ⎠⎝ u 2 ⎠

41

трансформатора.

В

таком

трансформаторе отношение u коэффициенту трансформации, т.е. u 1 = nu 2 ; 1 = n . u2

напряжений

равно

1 → 0 , т.е. pL 2 L 2 → ∞ . Для конечности n необходимо принять тогда и L 1 → ∞ . В этом случае ⎛ u ⎞ ⎛ 0 n ⎞⎛ i 1 ⎞ ⎟⎟⎜⎜ ⎟⎟ . i 2 = −ni 1 и уравнение имеет вид ⎜⎜ 1 ⎟⎟ = ⎜⎜ i n − 0 ⎠⎝ u 2 ⎠ ⎝ 2⎠ ⎝ Компонент, описываемый этими уравнениями, называют идеальным трансформатором (трансформатор с полной связью и бесконечно большими индуктивностями, отношение которых конечно и равно n 2 ). Его полюсный граф имеет тот же вид, что и в общем случае (рис. 48 б), но уравнения могут быть представлены только в смешанной форме. Поэтому в полюсном графе идеального трансформатора дуга 1 является Ζ – дугой, а дуга 2- y -дугой. 8.6. Механические многополюсники. Рассмотрим полюсные уравнения и полюсные графы простейших механических многополюсников. Рычаг (рис. 49 а) при малых перемещениях представляется полюсным графом (рис. 46, б) и описывается уравнениями Аналогичное соотношение, имеет место для токов при условии

d2x ⎧ = + n 21f 2 + n 31f 3 f M 2 ⎪1 dt ⎪ , где f1 , f 2 , f3 - силы; x1 , x 2 , x 3 - перемещения в точках x 2 = −n 21 x1 ⎨ ⎪ x 3 = −n 31 x1 ⎪ ⎩

a, b, c рычага; M - масса приведенная к точке a ; n 21 ,n 31 - отношения плеч рычага: e e n 21 = 2 ; n 31 = 3 . e1 e1

Рис. 49. Рычаг (а) и его полюсный граф (б)

Рис. 50. Зубчатая передача (а) и ее полюсный граф (б)

Зубчатая передача представляется полюсным графом (рис. 50) и описывается следующими полюсными уравнениями:

42

d 2 ϕ1 d 2 ϕ1 ⎧ ⎪r1 = (B1 + n 221B 2 ) + (τ1 + n 221 τ 2 ) + n12 r2 ,где r , r моменты, ϕ , ϕ - углы поворо1 2 1 2 ⎨ dt dt ⎪⎩ ϕ1 = −n12 ϕ1

та первого и второго валов; B 1 , B 2 - крутильные сопротивления, τ 1 , τ 2 - моменты инерции валов; n12 - переда- точное число, равное отношению количества зубьев

m1 . m2 Натяжной ролик преобразует вращательное движение в поступательное и его полюсный граф состоит из двух отдельных дуг (рис. 51). Полюсные уравнения шестерен: n 12 =

dϕ 1 d 2 ϕ1 ⎧ ⎪ натяжного ролика записываются в виде: ⎨ρ1 = B dt + τ dt − rf 2 , где B - крутильное ⎪⎩ x 2 = rϕ1

сопротивление; τ - момент инерции и r - радиус ролика.

Рис. 51. Натяжной ролик (а) и его полюсный граф (б)

Рис. 52. Блок (а) и его полюсный граф (б)

Блок, характеризующийся массой M , моментом инерции τ , радиусом r и сопротивлением трения B , представляется полюсным графом с тремя дугами (рис. 52) и описывается системой уравнений: ⎧ B dx1 τ d 2 x1 B dx 3 ⎛ τ ⎞ d 2x3 ⎪f1 = r 2 dt + r 2 dt 2 + f 2 r 2 dt − ⎜ M + r 2 ⎟ dt 2 ⎝ ⎠ ⎪ , x 2 = − x 1 + 2x 3 ⎨ 2 2 ⎪ d x B dx τ d x1 − 2f 2 + M 23 f3 = − 2 1 + 2 ⎪ 2 r dt r dt dt ⎩

где f1 , f 2 , f3 - силы, приложенные в точках a, b, c ; x1 , x 2 , x 3 перемещения этих точек.

Рис. 53. Механическая система с многополюсными компонентами (а) и ее граф (б). В качестве примера на рис. 53 изображена схема с механическим многополюсником и ее граф. Рычаг P1 представлен на графе дугами 1' и 2' , и рычаг P2 дугами 1" и 2"

43

8.7 Дифференциальный редуктор Дифференциальный редуктор (дифференциал) является примером вращательного механического многополюсника, полюсами которого являются три вала, которые осуществляют связь с другими компонентами. Скорость ωс пропорциональна разности скоростей ωа ωв и, т.е ωс = n( ωа - ωв). Коэффициент n определяется соотношением между числом зубьев конических зубчатых колёс.(рис.54)

Рис.54 Дифференциал (а), его кинематическая схема(б) и полюсный граф(в) Для вывода полюсных уравнений воспользуемся соотношениями динамики трёх валов ( без учёта трения в подшипниках и упругости валов): dω dω d I1 dt 1 = r1 − r ; I2 dt 2 = r2 − r ; I dtω = r − r , 3

3

3

где I1, I2, I3 - моменты инерции валов вместе с насаженными на них коническими шестернями ( I3 учитывает также момент инерции части дифференциала непосредственно сцепленной с валом С); r1, r2, r3 - внешние вращающие моменты; r эквивалентный момент нагрузки, приложенный к первому валу со стороны дифференциала. Соотношение для угловых скоростей при выбранном положительном направлении ω (рис54а.) имеет вид ω3 = −n(ω1 + ω2) Подставляя значение ω3 в последнее выражение, находим: r = n2 I3 ( dω1 + dω2 ) + nr 3 dt dt

Заменив в первых двух соотношениях r через полученное выражение и присоединив соотношение для угловых скоростей, получим полюсные уравнения дифференциала в виде: μ = (I + n I ) dω + n I dω + nμ , 2

1

1

μ

2

=n

2

I

dω

1

3

dt

2

1

3

2

3

dt

+ (I 2 + n

2

I) 3

dt

3

dω + nμ , 2

dt

3

ω = −nω −nω , или в матричной форме с использованием оператора дифференцирования p: 3

⎛ r1 ⎞ ⎟ ⎜ ⎜ r2 ⎟ ⎟ ⎜ ⎝ω3⎠

1

2

2

2 = ⎛⎜ p ( I 1 + 2n I 3 ) ⎜ pn I 3 ⎜ − n ⎝

pn I p (I + n I 3 2

2

−n

3

)

n n 0

⎞ ⎟ ⎟ ⎟ ⎠

⎛ ω1 ⎞ , ⎜ ⎟ ⎜ω2⎟ ⎜ ⎟ ⎝ r3 ⎠

где квадратная матрица третьего порядка,

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

44

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

8.8. Двигатель постоянного тока. В системах с электромеханическим преобразованием энергии в качестве многополюсных компонент используются электрические машины. Они представляются несвязанными полюсными графами, а их полюсные уравнения выражают зависимости между электрическими и механическими величинами. Наиболее простой пример электрических машин - двигатель постоянного тока. Он представляется полюсным графом дуги которого соответствуют обмотке возбуждения, электрическому входу и механическому выходу (рис 55.). Полюсные ⎧

= + di уравнения двигателя имеют вид: ⎪⎪ U R i L dt

1

1

1 1

1

⎪ di2 ⎨U2 = Gω3 i3 + R 2 i2 + L2 dt ⎪ d ω ⎪ =− Gi1 i2 + Bω3 + I dt 3 ⎪⎩ r3

, где R1 , L1 - сопротивление и

индуктивность обмотки возбуждения; R2, L2 - сопротивление и индуктивность цепи якоря; G - коэффициент, зависящий от параметров машины.

Рис55 Двигатель постоянного тока (а) и его полюсный граф(б) Два из этих уравнений нелинейны, так как в них входят произведения переменных. В частном случае (постоянное напряжение возбуждения u1 =const и отсутствие реакции якоря), ток возбуждения также постоянен i=i0. Уравнения становятся ⎛ U 2 ⎞ ⎛ R 2 + pL 2 ⎟⎟ = ⎜⎜ ⎝ r2 ⎠ ⎝ − G i 0

линейными и в матричной форме принимают вид: ⎜⎜

G i 0 ⎞⎛ i 2 ⎞ ⎟⎜ ⎟ . B + pI ⎟⎠⎜⎝ ω 3 ⎟⎠

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

8.9 Гидромеханические

многополюсники.

В технике в качестве исполнительных механизмов, усилителей, гидроприводов широко используются различные гидромеханические системы, которые также можно рассматривать как соединение многополюсных компонент. Рассмотрим примеры гидромеханических многополюсников. Управляющий золотникпредставляет собой многополюсник с механическим входом, характеризующимся силой f, и перемещением X1, и гидравлическим выходом, характеризующимся разностью давления P2 и объемным потоком жидкости g2. Полюсный граф состоит

45

из двух дуг, первая из которых отображает механический вход, а вторая гидравлический выход. Полюсные уравнения управляющего золотника имеют вид: 2 ⎛ d ⎜ K1 + B1 + M1 d 2 ⎛ f1 ⎞ ⎜ dt dt ⎜ ⎟= ⎜g ⎟ ⎜ ⎝ 2⎠ ⎜ K 21 ⎝

⎞ 0⎟ , ⎟⎛⎜ X1 ⎞⎟ ⎜ ⎟ 1 ⎟⎝ P 2 ⎠ ⎟ R2 ⎠

где B1 и M1 – соотвеетственно вязкое сопротивление и

масса золотникового поршня; R2 – гидравлическое сопротивление; K1 и K2 коэффициенты, определяемые экспериментально.

-

Рис 56 Управляющий золотник(а) и его полюсный граф(б)

Силовой цилиндр служит для преобразования гидравлического давления в механическую силу. Дуги полюсного графа соответствуют гидравлическому входу (объемный поток g1 и давление P1) и механическому выходу (сила f2 и перемещение поршня X2) (рис 57) Полюсные уравнения силового цилиндра можно записать в d⎞ ⎛ виде: S ⎟⎛ ⎞ ⎛ ⎞ ⎜0 g

⎜ 1⎟ = ⎜ ⎜ ⎟ ⎜ ⎝f 2 ⎠ ⎜ − S ⎝

dt ⎟⎜ P1 ⎟ 2 d ⎟⎜ ⎟ d B2 dt + M2 dt ⎟⎠⎝ X2 ⎠

где S площадь поршня; B2 и M2 – вязкое сопротивление и масса поршня.

Рис 57. Силовой цилиндр(а) и его полюсный граф(б) Управляющий золотник и силовой цилиндр совместно образуют гидравлический исполнительный механизм (Рис.58а), позволяющий при небольших управляющих усилиях и перемещениях на входе золотника получать значительные силы и перемещения на выходе силового цилиндра. Необходимая для этого энергия поступает от внешнего источника давления гидравлической системы. Граф гидравлического исполнительного механизма (рис.58б) получается объединением полюсных графов его компонент (дуги управляющего золотника отмечены Гидравлический штрихом, а дуги силового цилиндра – двумя штрихами). исполнительный механизм также можно рассматривать как многополюсный элемент с механическим входом (f1 , X1) и выходом (f2, X2) и представить соответствующим полюсным графом (рис.58в).

46

Рис.58 Гидравлический исполнительный механизм (а) и его графы (б, в) Исключая из уравнений золотника и силового цилиндра переменные g1=g2 и P1=P2, получим полюсные уравнения, соответствующие этому графу: 2 ⎛ d d ⎜ 0 + + k1 B1 dt M1 2 ⎛ f1⎞ ⎜ dt ⎜⎜ ⎟⎟ = d 2 ⎝ f 2 ⎠ ⎜⎜ (− R2 S + B2) + M2 d k 21 R2 S dt dt ⎝

⎞ ⎟ ⎟⎛⎜ X1 ⎞⎟ ⎟⎜⎝ X2 ⎟⎠ ⎟ ⎠

В гидроусилителе (рис.59а) гидравлический механизм используется совместно с рычагом в качестве обратной связи между входом и выходом, которая обеспечивает автоматическое закрытие золотника, когда силовой поршень занимает требуемое положение в полюсном графе гидроусилителя (рис.59б), дуги 1' и 2' изображают гидравлический механизм, дуги 1'' и 2''- рычаг, а дуги 1 и 2 соответственно входное и выходное усилия.

Рис 59. Гидроусилитель (а) и его полюсный граф (б)

9. Задача о кратчайшем пути. Многие задачи выбора наиболее экономичного (по расстоянию, времени или стоимости) маршрута на имеющейся карте дорог, выбора наиболее экономичного способа перевода динамической системы из одного состояния в другое и т.п., сводятся к задаче о нахождении кратчайшего пути между двумя вершинами связного неориентированного графа. Методы, основанные на использовании графов, часто оказываются наименее трудоемкими, по сравнению с другими методами решения подобных задач. В общем виде, задача о кратчайшем пути на графе может быть сформулирована следующим образом. Дан неориентированный граф G = (V; E) . Каждому ребру e ⊂ E этого графа приписано некоторое число l(e) ≥ 0, называемое его длиной. Это число, в частном случае, может являться расстоянием между вершинами, соединяемыми этим ребром, временем или стоимостью проезда по этому ребру и т.п. При этом любая цепь r = ( e1 , e 2 ,..., e K ) будет характеризоваться длиной,

47 K

определяемой соотношением l (r ) = ∑ l (e i ) . Требуется для произвольных вершин a i =1

и b графа G найти путь rab , причем такой, чтобы его полная длина была наименьшей. Общее правило нахождения кратчайшего пути в графе состоит в том, чтобы каждой вершине x i приписать индекс λ i , равный длине кратчайшего пути из данной вершины в конечную. Сложность этой процедуры заключается в том , что путь, проходящий через наименьшее число вершин, часто имеет большую длину, чем некоторые обходные пути. Например, в графе рис. 60, изображающем карту дорог, прямой путь, из вершины помеченный звездочкой в конечную вершину, имеет длину l = 12, в тоже время обходной путь через вершину, отмеченную треугольником имеет длину l = 10.

Рис. 60. Карта дорог. Цифры у ребер указывают время проезда не каждой из дорог. Приписывание индексов вершинам производится в следующем порядке: 1) конечной вершине b = x 0 приписывается индекс λ 0 = 0 , остальные вершины x i помечаются индексами λ i , которым полагаем λ i = ∞ (i ≠ 0) ; 2) ищем такую дугу (x i , x j ) , для которой λ j − λ i > l (x i , x j ) и заменяем индекс λ j индексом λ ′j = λ i + l (x i , x j ) < λ j . Продолжаем этот процесс замены индексов до тех пор, пока остается хоть одна дуга, для которой можно уменьшить λ j . Приписанные вершинам индексы обладают двумя свойствами: 1. Для произвольного ребра (x K , x S ) обязательно выполняется условие λ S − λ K ≤ l (x K , x S ) . 2. Для произвольной вершины x p с индексом λ p найдется вершина x q , соединенная ребром с x p , такая, что λ p − λ q = l (x q , x p ) .

48

Рис. 61. На основе указанных свойств можно сформулировать правило нахождения кратчайшего пути. Пусть x n = a - начальная вершина с индексом λ n ищем вершину x p , такую, 1

что λ n − λ p = l (x p , x n ) . Далее ищем вершину x p такую, что λ p − λ p = l (x p , x p ) и 1

1

2

1

2

2

1

т.д. до тех пор, пока не дойдем до конечной вершины x 0 = b . Путь r0 = (x n , x p , x p ,..., x p , x 0 ) длина которого λ n является кратчайшим (последовательность индексов должна уменьшаться). Рассмотрим указанную процедуру на графе рис. 60, результат которой приведен на рис. 61. Конечной вершине b = x 0 приписываем индекс λ (x 0 ) = 0 . Вершине x1 , непосредственно примыкающей к x 0 приписываем индекс λ (x1 ) = 2 , т.к. кратчайший путь l (x1 , x 0 ) = 2 . Вершине x 2 приписываем индекс λ (x 2 ) = 7 , т.к. кратчайший путь l (x 2 , x 0 ) = 7 . Вершине x 3 приписываем индекс λ (x 3 ) = 10 , т.к. Вершине кратчайший путь l (x 3 , x 0 ) = l (x 3 , x 5 ) + l (x 5 , x1 ) + l (x1 , x 0 ) = .1+7+2=10 x 4 приписываем индекс λ (x 4 ) = 10 , т.к. кратчайший путь l (x 4 , x 0 ) = l(x 4 , x 3 ) + l (x 3 , x 0 ) = 3 + 7 = 10 . Вершине x 5 приписываем индекс λ (x 5 ) = 9 , т.к. кратчайший путь l (x 5 , x 0 ) = l (x 5 , x1 ) + l (x1 , x 0 ) = 7 + 2 = 9 . Для вершины x 6 l (x 6 , x 0 ) = l (x 6 , x 5 ) + l (x 5 , x1 ) + l (x1 , x 0 ) = 8 + 7 + 2 = 17 , поэтому λ (x 6 ) = 17 . Для вершины x 7 имеем l (x 7 , x 0 ) = l (x 7 , x1 ) + l (x1 , x 0 ) = 5 + 2 = 7 , т.е. λ (x 7 ) = 7 . Поскольку l (x 9 , x 0 ) = λ (x 9 ) − λ (x 6 ) = l (x 9 , x 6 ) + λ (x 6 ) = 3 + 17 = 20 , то λ (x 9 ) = 20 . Далее λ (x 8 ) = λ (x 9 ) + l (x 8 , x 9 ) = 4 + 20 = 24 ; λ (x10 ) = l (x10 , x11 ) + l (x11 , x12 ) + l (x12 , x 3 ) + λ (x 3 ) = 2 + 5 + 3 + 10 = 20 ; λ (x11 ) = l (x11 , x12 ) + l (x12 , x 3 ) + λ (x 3 ) = 5 + 3 + 10 = 18 ; λ (x12 ) = l (x12 , x 3 ) + λ (x 3 ) = 3 + 10 = 13 ; 1

2

K

49

λ (x13 ) = l (x13 , x 2 ) + λ (x 2 ) = 8 + 7 = 15 ; λ (x14 ) = l (x14 , x13 ) + λ (x13 ) = 1 + 15 = 16 ; λ (x15 ) = l (x15 , x14 ) + λ (x14 ) = 12 + 16 = 28 ; λ (x16 ) = l (x16 , x12 ) + λ (x12 ) = 10 + 13 = 23 ; λ (x17 ) = l (x17 , x16 ) + λ (x16 ) = 5 + 23 = 28 ; λ (x18 ) = l (x18 , x 8 ) + λ (x 8 ) = 3 + 24 = 27 ; λ (x19 ) = l (x19 , x18 ) + λ (x18 ) = 4 + 27 = 31; λ (x 20 ) = l (x 20 , x10 ) + λ (x10 ) = 12 + 20 = 32 ; λ (x 21 ) = l (x 21 , x17 ) + λ (x17 ) = 3 + 28 = 31 . Кратчайший путь (см. рис. 61) проходит через вершины x n = x 21 = a , x17 ; x16 ; x12 ; x 3 ; x 5 ; x1 ; x 0 = b ; длина его l (a, b) = 31 . Интерес к решению рассмотренной задачи объясняется, прежде всего, потребностями практики. При изучении объектов и управлении ими формируются определенные отношения соподчинения. В результате исследования первоначальная система элементов вместе с установленными в ней связями образуют сеть. Вершинами сети являются исходные объекты, а ребрами – установленные между ними связи. Если появляется необходимость в построении новых пунктов, то возникает вопрос, как расположить эти пункты в сети с тем, чтобы расстояние до них от первоначально заданных пунктов было минимальным. Подобные задачи возникают при выборе наилучшего варианта транспортных, вентиляционных, электрических сетей, при использовании тарифной системы на телефонных линиях, определения границ территорий, имеющих различные темпы развития и многих других. Методы, позволяющие решать разные задачи, сходные в некотором смысле по своему критерию оптимальности тесно связаны с областью математики, известной под названием сетевого планирования и управления, в основе, которой лежит теория графов. Эти методы моно разделить на два основных класса: индексные и матричные. В основу индексных методов положен принцип индексации, т.е. принцип присвоения вершинам графа некоторых индексов, значения которых изменяются в процессе решения. Эти величины в результате реализации алгоритма определяют длину пути от фиксированной до рассматриваемой вершины. Все матричные методы связаны с построением матрицы смежности весов, элементами которой являются веса соответствующих дуг или ребер. Экстремальные пути находятся последовательным преобразованием исходной матрицы смежности. И те и другие методы могут быть реализованы на ЭВМ.

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

50

построения наилучшей схемы административного подчинения по критерию минимального количества непосредственных связей (минимуму непосредственных подчиненных и непосредственных начальников), задача построения определенной схемы связи в электрических сетях по критерию минимального количества контактов, задача выбора при обработке деталей наилучшего порядка, который должен удовлетворять определенной технологии и др. При решении подобных задач приходится, имея допустимую схему связей объектов, выделить из нее какую-нибудь часть связей, удовлетворяющую определенным критерием. В качестве элементов (вершин) могут выступать некоторые узловые коммуникации (населенные пункты, магазины, склады, пункты электроснабжения и т.д.). Каждая связь (дуга) между вершинами характеризуется определенной величиной (временем, некоторыми затратами на строительство коммуникаций, длиной пройденного пути и т.д.). Требуется, не теряя связности графа, найти один из вариантов сети, для которой достигается минимум суммарных весов дуг. Аналогичные задачи могут встречаться при проектировании строительства сетей транспортных, газовых, воздушных, сети коммуникаций для передачи информации, при составлении графика выполнения работ и т.д. Рассмотрим алгоритм решения такой задачи на примере графа изображенного на рис. 62, в котором дуга u 3, 6 с весом l (3;6) = 5 входит в обязательном порядке в искомый частичный граф.

Рис. 62.

Рис. 63.

Шаг 1. Располагаем дуги графа в порядке убывания соответствующих им

весов:

u ij

u 4,6

u 3, 4

u′4, 6

u 2,5

u 3, 6

u 5, 6

u 3, 2

u ′3, 2

u 1, 3

u 2, 4

u 1, 2

u 4,5

l ij

8

7

7

6

5

4

4

3

3

2

1

1

Шаг 2. Рассматривая последовательно каждую дугу u ij , удаляем ее из исходного графа, если вес этой дуги больше, чем длина пути от x i к x j . Берем первую дугу u 4 , 6 из таблицы с максимальным весом l 4, 6 = 8 . Найдем пути, соединяющие вершины 4 и 6 . В нашем случае такими путями являются 4 → 5 → 6 с длиной 5 и 4 → 6 с длиной 7 Среди этих путей выберем путь с наименьшей длиной 5. Следовательно, дуга u 4, 6 с весом l 4 , 6 = 8 удаляется из исходного графа.

51

Рассмотрим вторую дугу в таблице u 3, 4 с весом l 3, 4 = 7 . Снова находим все пути, идущие от узла 3 до узла 4. 3 → 2 → 4 с весом 6 и 3 → 2 → 4 с весом 5. Дуга u 3, 4 также удаляется из исходного графа, т.к. 7 > 5 . Далее дуга u′4, 6 с весом l ′4, 6 = 7 путь 4 → 5 → 6 с весом 5 < 7 удаляется, дуга u 2 , 5 с весом l 2, 5 = 6 путь 2 → 4 → 5 с весом 3 < 6 удаляется, с весом 3 < 4 удаляется. дуга u 3, 2 с весом l 3, 2 = 4 путь 3 → 2 В результате выполнения шага 2 в таблице останутся дуги с весами:

u ij

u 3, 6

u 5, 6

u′3, 2

u 1, 3

u 2, 4

u 1, 2

u 4,5

l ij

5

4

3

3

2

1

1

Шаг 3. Выбираем первую дугу u 3, 6 с весом l 3, 6 = 5 . Так как по условию она входит в граф в обязательном порядке, переходим к рассмотрению следующей дуги u 5, 6 с весом l 5, 6 = 4 . Для этой дуги не существует другого пути от вершины 5 к вершине 6, оставляем ее и переходим к следующей. Аналогичная проверка показывает для дуг u ′3, 2 , u 1, 3 , u 2 , 4 таких путей тоже не существует. Переходим к рассмотрению дуги u 1, 2 с весом 1. Для концевых вершин этой дуги существует путь 1 → 3 → 2 , поэтому дуга u 1, 2 из графа удаляется. Дуга u 4 ,5 оставляется, т.к. не существует другого пути между вершинами 4 и 5. Итак, в результате выполнения шагов 2 и 3 из исходного графа (рис. 62) получен искомый частичный граф (рис. 63), сумма весов дуг которого равна ∑ l iK = l 1, 3 + l 3, 2 + l 2, 4 + l 4, 5 + l 5, 6 + l 3, 6 = 18 . Множество дуг этого графа составят дуги u 3, 6 ; u 5, 6 ; u 3, 2 ; u 1, 3 ; u 2 , 4 ; u 4 ,5 с весами 5; 4; 3; 3; 2; 1.

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

52

обслуживания разбираются задачи назначения приоритетов в обслуживании поступающих заявок некоторыми устройствами, приборами и т.п. Существует некоторое сходство формальных моделей этих видов задач. Целенаправленную деятельность можно рассматривать как некоторый протекающий во времени процесс, заключающийся в реализации (выполнении) определенной совокупности работ S = {P1 , P2 ,..., PS }. Выполнение работ стеснено целым рядом ограничений и условий, которые можно разбить на две группы. Ограничения α . Эти ограничения описывают взаимную зависимость выполнения работ. Каждой работе Pi ∈ S можно поставить в соответствие некоторое множество Π i ⊂ S непосредственно предшествующих работ, без выполнения которых нельзя начинать выполнение работы Pi , а также ряд работ, не входящих во множество S , которое могут рассматриваться как внешние факторы, необходимые для выполнения работы Pi . Например, возведение стен строящегося здания возможно начать лишь после того, как сделан фундамент (работа из множества S ), а также при наличии кирпича и раствора, изготовление и транспортировка которых могут и не входить в данный перечень работ. Для описания некоторых других условий, входящих в ограничения α , удобно ход выполнения работ рассматривать в дискретном времени, приняв некоторую величину Δt за единичный интервал времени (условный день, год и т.п.) называемый шагом. Некоторые работы могут быть выполнены целиком за один шаг, другие – за несколько шагов. В ограничение α должно входить условие допустимости или недопустимости прерывания работ. Пусть t - номер рассматриваемого шага (t = 1,2,...) . Обозначим через y i (t ) долю работы Pi , выполняемую на шаге с номером t , которую назовем единичной порцией работы Pi . Обозначим через S(t ) перечень работ, выполняемых на шаге с номером t . Пусть работа Pi состоит из m единичных порций y i и прерывание этой работы недопустимо. Условие недопустимости прерывания работы заключается в том, что если эта работа начинается на шаге с номером t , то единичные порции y i должны входить в перечни работ S(t ), S(t + 1),..., S(t + m − 1) . Ограничение β . Они связаны с ограниченным объемом ресурса, который может быть выделен на выполнение совокупности работ S . Обозначим через Q(t ) вектор ресурса, который может быть выделен на выполнение работ на шаге с номером t . Компонентами вектора Q(t ) могут быть величины Q1 - сырье, материалы, Q 2 - оборудование, Q 3 - рабочая сила и т.п. Обозначим через q[y i (t )] количество ресурса, которое необходимо затратить для выполнения работы y i (t ) . В этих обозначениях ограничение β запишется в виде

∑ q[y S

i =1

i

( t ) ] ≤ Q( t ) ,

t = 1,2,..., M ,

где M - общее число шагов.

53

В задачу иногда вводится предложение, что единичная порция работы y i (t ) либо выполняется полностью, если на нее выделен необходимый ресурс, либо не выполняется совсем, если ресурс выделен не полностью. Более сложная задача получается, когда доля выполненной работы зависит от количества выделенного ресурса. Задача на составление расписания сводится к тому, чтобы для каждого шага t назвать перечень работ S(t ) = Pt ,..., Pt , которые должны выполняться в течение

{

1

e

}

этого шага, и также долю y i (t ) каждой из этих работ с учетом всех ограничений, накладываемых на порядок выполнения работ и на выделяемые ресурсы. Если число работ велико, то число вариантов расписания может быть огромным. Выбор конкретного варианта расписания связан с понятием директивного срока. Если перечень работ и ресурс на их выполнение заданы, то наилучшим (оптимальным) вариантом расписания следует считать тот, при котором время выполнения всего перечня будет минимальным. Этот срок и принято называть директивным. Пусть имеется сложная программа работ S = {P1 ,..., PS } , в которой действуют ограничения α , определяющие очередность выполнения отдельных работ, так и ограничения β на выделяемые ресурсы. На практике обычно ограничения α связывают между собой не все работы, а действуют внутри некоторых независимых групп работ. Сами же такие группы между собой жесткими ограничениями не связаны. В таких случаях программу работ S можно представить в виде некоторого разбиения m = {R 1 ,..., R m }, элементы которого R ∈ m представляют собой некоторые самостоятельные подпрограммы, обладающие тем свойством, что между ними отсутствуют жесткие ограничения очередности, так что каждая подпрограмма R ∈ m может выполняться почти независимо от выполнения других подпрограмм. Однако внутри каждой подпрограммы R i = {Pi ,..., Pi } порядок выполнения работ подчинен жестким ограничениям α . Таким образом, задачу на составление расписания можно разбить на две самостоятельные задачи. Особенности задач первого типа состоят в том, что жесткие ограничения α в таких задачах в значительной степени предопределяют порядок выполнения отдельных работ и число возможных вариантов расписания здесь не очень велико. Однако варианты всегда возможны и среди них могут найтись такие, при которых окажется минимальным время выполнения подпрограммы, наиболее рациональное распределение ресурсов и т.п. Для решения задач этого типа широко применяются методы сетевого планирования и управления (СПУ). В задачах второго типа ограничения на очередность выполнения отдельных работ незначительны, что не означает, что порядок выполнения работ здесь безразличен. От порядка выполнения работ зависит распределение ресурса по шагам. На переход от одной работы к другой тратится время, может потребоваться переквалификация персонала, переналадка или замена оборудования и т.п. Поэтому и здесь стоит задача составления расписания работ в определенном смысле 1

r

54

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

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

Рис. 64. Сетевой график изготовления прибора. На рис. 64 приведен образец сетевого графика, на котором показаны работы, необходимые для изготовления некоторого прибора. Сетевой график дает наглядное представление о порядке выполнения работ, позволяет оценивать влияние отклонений от плана на дальнейший ход работ, дает возможность наиболее рационально распорядиться имеющимися трудовыми и материальными ресурсами. Первый шаг в построении сетевого графика состоит в расчленении всего комплекса на отдельные работы или операции. Каждая работа связана с затратами времени, следовательно, имеет начало и конец, которые должны легко определяться. Одновременно с перечнем работ определяются ограничительные условия на их выполнение: длительность каждой работы, средства на ее выполнение, интенсивность, перечень непосредственно предшествующих работ, выполнение которых является необходимым для начала данной работы. С целью упорядочения работ удобно приписывать отдельным работам вес, отражающий степень их важности, что в значительной степени предопределяет порядок выполнения работы. Одним из способов упорядочения работ является приписывание работе веса, равного сумме числа непосредственно следующих за ней работ и вес этих работ. Конечные работы принято считать одинаково важными и приписывать им вес условно равный единице.

55

Начало некоторых работ можно изменять в пределах, называемых резервами времени, не нарушая требуемой последовательности работ и общего срока окончания всего комплекса работ. Так резерв времени Δτ K для работы K будет равен Δτ K = t ′K′ − t ′K , где t ′K - наиболее ранний, t ′K′ - наиболее поздний сроки ее окончания. Наглядное представление хода выполнения работ дает сетевой граф. Дуги в сетевом графе представляют собой некоторые работы, требующие затрат времени и ресурсов, а вершины являются событиями (моментами окончания одной или нескольких работ). Сетевой граф должен удовлетворять определенным условиям: 1. Ни одно событие не может произойти до тех пор, пока не будут закончены все входящие в него работы. 2. Ни одна работа, выходящая из данного события, не может начаться раньше этого события. Поскольку ни одна последующая работа не может начаться раньше, чем будут закончены все предшествующие ей работы, то на сетевом графе не должно быть контуров. Кроме того сетевой граф должен содержать только одно начальное и одно конечное событие, в противном случае его всегда можно преобразовать к нужному виду. Существуют определенные правила построения сетевого графика, которые дают возможность изображать каждую работу единственной стрелкой между двумя событиями и позволяют безошибочно составить и проверить сетевую модель любого комплекса работ. Отсылая за подробностями построения сетевого графика к многочисленной литературе, например, [9,10,11] , здесь лишь отметим, что с точки зрения классификации графов сетевой график представляет собой ориентированный связный, асимметрический граф без контуров с одним входом и одним выходом. Вершины графа (события) обычно нумеруются, а над стрелками (дугами) ставятся числовые характеристики работ. Наличие числовых характеристик у дуг позволяет осуществлять математический анализ сетевого графа. Путем на сетевом графе называют непрерывную последовательность работ – дуг графа, а длиной пути – сумму числовых характеристик дуг, составляющих этот путь. Путь наибольшей длины между начальным и конечным событиями сети называют критическим, а длина его определяет срок завершения всего комплекса работ. Работы, лежащие на критическом пути, называют критическими. Раннее начало работы – это самое раннее время начала работы, которое определяется длиной максимального пути от начального события до события, предшествующего данной работе. Определим раннее начало работы (дуги) u4.7 на графе рис. 65. Длина максимального пути 1 → 2 → 3 → 4 от узла 1 до узла 4 равна 6. Поэтому раннее начало работы u4.7 будет 6. Раннее окончание – время окончания работы, которая начата в самый ранний срок (раннее начало работы). Это время определяется как сумма раннего начала и продолжительности данной работы. Например, раннее окончание работы u4.7 равно 6+5=11.

56

Позднее начало – самое позднее время начала работы, сдвиг которого вызывает задержку окончания всего комплекса. Оно определяется как

Рис.65. разность продолжительности критического пути и длины максимального пути от предшествующего события данной работы до конечного события. Найдем позднее начало работы u4.7 (рис.65). Длина критического пути 1 → 2 → 3 → 6 → 7 → 8 равна 20. Максимальный путь от вершины 4 до вершины 8 будет 4 → 7 → 8 и его длина равна 5+1=6. Отсюда позднее начало работы u4.7 будет 206=14. Позднее окончание – время окончания работы, если она начата в поздний срок (позднее начало). Оно определяется как сумма позднего начала и продолжительности рассматриваемой работы. Позднее окончание работы u4.7 будет 14+5=19. Полный резерв времени работы – это максимальное количество времени, на которое можно увеличить продолжительность выполнения работы без увеличения продолжительности выполнения всего комплекса (длины критического пути). Для работы u4.7 (рис. 65) полный резерв времени будет 8, т.к. 5+8=13<14. На сети (рис. 65) в этом случае существует другой критический путь 1 → 2 → 3 → 4 → 7 → 8 длина которого также равна 20. поэтому значение 8 для u4.7 будет максимальным резервом времени. Свободный резерв времени – максимально допустимое увеличение продолжительности работы, не нарушающее возможности начать все работы, последующие за рассматриваемой, в наиболее раннее допустимое время. Для работ, оканчивающихся в событиях, лежащих на критическом пути полный резерв совпадает со свободным. Например, для определения свободного резерва времени работы u4.7 нужно найти разность между ранним началом любой работы выходящей из события 7 (например, u7.8) и ранним окончанием работы u4.7 , т.е. 19-11=8. Свободный резерв времени совпал с полным, т.к. событие 7 лежит на критическом пути. Перед теорией сетевого планирования и управления ставится задача поиска методов решения практических задач исключающих необходимость перебора всех возможных вариантов, поэтому она является объектом приложения различных областей математики: теории графов, теории вероятности, методов линейного, нелинейного и динамического программирования, математической статистики и многих других. Процесс оптимизации сети, как правило, связан с распределением ресурсов, которые охватывают средства производства (машины, оборудование, изделия,

57

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

Литература 1. Емеличев В.А. и др. Лекции по теории графов. – М.: Наука, 1990, 382 с. 2. Белов В.В., Воробьев Е.М., Шабалов В.Е. Теория графов.– М.: Высшая школа, 1976, 396 с. 3. Зыков А.А. Теория конечных графов. – Новосибирск: Наука, 1969, 543 с. 4. О. Оре. Графы и их применение. – М.: Мир, 1965, 174 с. 5. Ф. Харари. Теория графов. – М.: Мир, 1973, 300 с. 6. К. Берж. Теория графов и ее применения. – М .: Иностранная литература, 1962, 319 с. 7. С. Цой, С.М. Цхай. Прикладная теория графов.– Алма-Ата: Наука, 1971, 499 с. 8. Сигорский В.П. Математический аппарат инженера. – Киев: Техника, 1975, 765 с. 9. Воробьев Б.М. Методы сетевого планирования и управления (практикум). – М.: Наука, 1967, 268 с. 10. Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. – М.: Наука, 1965, 360 с. 11. Разумов И.М., Белова Л.Д., Ипатова М.И., Проскуряков А.В. Сетевые графики в планировании. – М.: Высшая школа, 1967, 396 с. 12. Л.Ловас, М. Пламмер Прикладные задачи задачи теории графов. Теория паросочетаний в математике, физике и химии. – М.: Мир, 1998, 343 с.