Прохоров Г.В., Леденев М.А., Колбеев В.В. Пакет символьных вычислений Maple V (Прохоров Г.В., Леденев М.А., Колбеев В.В. Пакет символьных вычислений Maple V.djvu), страница 7

Формат команды: ссе!еСе(Езес, Б) с с(вессс' Гьес, Ос'; где Π— имя графа; Чзег, Езе! — имена множеств, содержащих вершины или ребра, предназначенные для удаления. > Снасошр!есе(5); > с)е)еге((3,4),С): > чегбсеа(С), епдз(С); (1,2, 5), ((1, 5), (2,5), (1,2)) В предыдуших командах было удалено ребро (3,4).

В следующих командах удаляются ребра, инцидентные вершине 5. > йе$еге()псЫепс(5,С),С)с > чегИсея(С), спс(а(С); (1,2, 5), ((1,2) ) Команды )сенс( и сай Эти команды возвращают имена вершин, которые являются головой ребер (в случае команды Ьеас() или хвостом (в случае команды сай). 64 Глава В Формат команд: саст(61; ! ас'! ( е, б ); саст(еяес, 6); где Π— граф, с - ребро, еяес — множество ребер. Для команды Ьсас( формат вызова аналогичный.

> век(1с): > аИтег1ех((а,Ь),(с); > аййейде((а, Ь!.Ц; > \а(1(е1 (с); > Ьеас)(е1,$с); > аИес)ае((Ь,а),(с); > Ьеас((3с); саЫе(( е1= 6 е2= а )) Последняя команда вывела все вершины-головы графа. Решение задач из теории г вфов с визуализацией результатов 65 Команда гоЫ Эта команда генерирует пустой граф, т.е. граф без ребер. Формат команды: гоЫ(л), гоиз(изсы; где и — число, определяющее количество вершин; чвег — множество имен вершин. > д:=го)д(10): > ед8ев(8); > тегбсев(п); (1,2,3,4, 5, 6,7,8,9,10) Команда зйон' Эта команда возвращает таблицу, содержащую всю информацию о графе.

> Сиесопзр)еге(3): > Т:=ваап(С); Т:= ТАВЬЕ(( Езпахпагае = 3 Сопи(сп(в = Сопптспгв )ч(е(8)зЬогв = ТАВЬЕ(( 1 = (2, 3) 2 = (1, 3) 3 = (1, 2)() Ъ'пе(8)зе = ТАВ1,Е(врагве,[ !) бб Глава 3 ЕсоппесВгВу = ЕсоппесВчйу Чегг(сев = (1, 2, 3) Едпе!пдех = ТАВЬЕ(аушшесг)с,! (1, 2) = (еЦ (2, 3) = (еЗ! (1, 3) = (е2)!) Едпев = (е2, е1, еЗ! Неад = ТАВЕЕ(! !) Егге)п)гг = ТАВ1,Е(! е1 =1 е2 = 1 еЗ = 1 !) ТаВ = ТАВ(,Е(! !) В(сошропеп(в = В)согоропептв Епда = ТАВЬЕ(! е1 = (1, 2) е2= (1,3) еЗ = (2, 3! !) Сошйггеев = Сошгйгееа В(а(пв = (Б1МР1.Е, СОМР(.ЕТЕ)!) Команда )нсЫенсе Эта команда генерирует матрицу инцидентности.

> Снасус)е(4): > аддедае((1,3),С): > Т:=(пс(депсе(С); 1 О О 1 -1 1 1 О О О О 1 1 О 1 О О 1 1 О Решение задач из тео ии графов с визуализацией результатов 67 Команда афасеасу Эта команда генерирует матрицу смежности. > зч!!)з(пе!ног)гв): > С:=сус!е(4): > аддедйе(!1,31,С): > Тз=ад!асепсу(С); О 1 1 1 1 О 1 О О 1 О 1 1 О 1 О Команды чи е(еАг и еи ейдАг Эти команды возвращают веса вершин и ребер соответственно. Формат команды ччче!яЫ: чзче!еА|(6>; чие!яАз(к 6); чзче!еА! ( ч!т, 6); где С вЂ” граф; ч.- имя вершины; ч!!в! — список вершин. Формат команды еиецАп езче(еА~ ~ 6 >: езчефАце, 61; егае(яАбе!т, 6); > пеи(С): > аддчеггех(!1,2,3),зче!ай!в=!1,2,3),С): > чзге!фг(С)' гаЫе(лоан, ( 1=1 2=2 3=3 )) 68 Глава 8 > тзге(а)зг(1,С); > пеи(С): > аддтег1ех(1,2,3,С)." > ай$едйе(((1,2),(2,3),(1,3)),ие(8ЬЬ=(3,4,61,С); е(, е2, еЗ > еие(8М(С); гаЫе(( е1= 3 е2 = 4 е3=6 3 > еие(й)И(е1,С); Комаида с(ирйсаге С помощью этой команды можно создать копию графа.

> С:=сотар)е1е(4): > Н:=дирйсаге(С): Последние команды создали два идентичных графа: О и Н. Команда гаги(ози Эта команда создает случайный граф. Формат команды; 6: г талдоме (и); 6. =гаидоиз(и, из); Решение задач нз теории афон с визуализацией результатов 69 6:гхаиаат(и, 'ргаб =х); где и — число вершин: гп — число ребер; х — действительное число 0 < х с1. Если используется первый вариант команды, то создается граф с п вершинами, а ребра определяются с вероятностью 50 'е (т.е. ребро между данными вершинами выбирается случайным образом). > Ь:=саидов(5): йгаи(Ь); При вызове гапйош с несколькими аргументами строится случайный граф с и вершинами и с ш ребрами, причем вероятность построения ребра определяется числом х.

> С:=саидов(4,ргоЬж1): йгазг(С); В теории графов широко распространены задачи отыскания наибольшего потока через заданную сеть. Подобные задачи решаются не только для определения потока, но и для определения максимального паросочетания. Для решения таких задач обычно используется алгоритм Форда — Фалкерсона. Мар!е также предоставляет возможность решения задачи отыскания максимального потока в сети. Эту возможность реализует функция г)аж.

Формат команды Лов: Раж/С,а~); 11ан 16,а б 'тах11ан '=и); 11ав16,а безебсатр); у1ан (Од С езеасотр, 'тах)1 он '=и); 70 Глава 8 Эта команда находит максимальный поток в сети С от вершины я к вершине ! (от источника к стоку). езе! . имя множества, в котором будут содержаться ребра, по которым проходит максимальный поток.

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

> Снесовр!е!е(3,2): йож(С,1,2,еяет,совр); ((1,4), (1, 5), (2,4), (2, 5) ) > совр; (1,2,5) ) йои(С,1,2,ае!1,хе!2,'вахйон'ж1); ((1,4)„(2,4) ) Последняя команда йов выдала ! — поток, который требовался опцией тахйов (хотя максимальный поток в данной сети равен 2).

Граф, в котором находился поток, показан ниже: Решение задач нз теории г а ов с визуализацией езультатов 71 > йгаи(С); Широко распространены задачи нахождения кратчайшего пути. В таких задачах задаются граф (сеть дорог) и начальная вершина (пункт отправления). Каждому ребру можно присвоить вес — длину дороги; кроме зтого ребра могут быть как ориентированными, так и не ориентированными. Задача нахождения кратчайшего пути решается с помощью алгоритма Дейкстры. Результат работы алгоритма — дерево с началом в начальной вершине, причем ко всем остальным вершинам идут кратчайшие пути. В Мар(е задачу нахождения кратчайшего пути можно решить с помощью команды йоттра! атее.

Формат команды: зттоттрпт)н тее(6, ел где Й вЂ” граф; ч — начальная вершина. В следующем примере создадим полный граф с четырьмя вершинамй, причем вес каждого ребра равен единице. > я:=спер!еге(4): йтаи(й); Глава 8 > й!няз|юг1раг!г!гее(й,2): йгаю(я1); 4 Таким образом, я! — дерево, полученное в результате работы алгоритма Дейкстры.

Теперь изменим исходный граф я. Ребру, которое соединяет вершины 2 и 3, присвоим вес, равный !00. > еййеа((2,3),я); (е4) > де!еге(е4,я): ай$ег!йе((2,3),ие!й)гЬ=100,я): > й=аЬогграг)гггее(я,2): дгаи(г); Таким образом, в измененном графе найдены новые кратчайшие пути ко всем вершинам. Команда з)зогграг!зггее также присваивает длины кратчайших путей весам вершин.

> гие1я!гт(1); Из приведенной таблицы следует, что, для того чтобы попасть из вершины 2 в вершину 3, требуется пройти расстояние, равное двум. Решение задач из теории графов с визуализацией ез льтатов 73 В теории графов существует понятие лланарности графа. Граф называется планарным, если его можно изобразить на плоскости без самопересечений. Задача определения планарности встречается при разводке печатных плат, где ребра графа — печатные проводники, вершины — контактные площадки.

В Мар!е У проверить планарность графа можно с помощью команды мр1алаг, которая возвращает !гце, если граф планарный, и (а!зе — в противном случае. Вначале !зр!алаг упрощает граф, т,е. удаляет циклы и повторяющиеся ребра, а затем граф проверяется на планарность (упростить граф можно с помощью яз(шр). > я:жсогпр(е!е(5)з бган(й); > Ьр!апаг(й); > й1;=совр!еге(3): оган(й1); > Ьр1апаг(й1); В этом разделе приведены лишь краткие сведения о библиотеке Хе!чот(гз, но перечисленных команд будет достаточно для решения элементарных задач теории графов. При необходимости найти дополнительные сведения о данной библиотеке можно воспользоваться справочной системой Мар1е.

Глава 9 74 9. ПОСТРОЕНИЕ ГРАФИКОВ ПО РЕЗУЛЬТАТАМ МАТЕМАТИЧЕСКИХ ВЫЧИСЛЕНИЙ 9.1. Общие сведения Мар!е является прекрасным инструментом для визуализации информации о исследуемой функции. Используя устройство типа "мышь", можно просмотреть локальные минимумы и максимумы, нулевые точки. 9З.1. Ограничения Если функция имеет большой интервал между двумя точками (превышающий масштаб осей), то график не может быть выведен. Например: >. р!о! (гйв(х "2),х=0..30); 0 -05 В %шбоч з — версии Мар!е — не рекомендуется устанавливать ко- мандой !пгег(асе устройство вывода, так как не удастся восстановить выВод В окно 1т!поожз.

9.1.2. Устройства вывода Установить устройство вывода можно с помощью команды лнегГасе(р/опгет1се = х), где х — параметр. Построение г афиков по результатам математических вычислений 75 Параметр может принимать следующие значения: Ьвр, сапоп, срз (или роз|зспр|с), |)ез(с)е1, ерзоп24, ерзоп9, ерзоп9Ь(, Ьря!, я((; |300, |Ьв, |Ьв вопо, |Ъ|прго, (Ьвцн(е1, 1азег)е(, 1п03, о)с!92, ра|п|)е|, рсх, р!с, рз, (или роз|зспр|), йТ, |озЬ|Ьа, ип|х Если в качестве устройства вывода установлен один из типов принтеров, то вывод производится на терминал, укаэанный в команде т|ег~асе(р1о|ои|рщд т.

е. на РКХ, 1.РТ1, 1.РТ2, СОМ! или СОМ2. В противном случае вывод производится в файл, указанный в команде ш|е~асе(р!о|ооцлн7 Если устройство — с(|аг, то вывод в зависимости от установки р1о|он|рн| осуществляется на следующие устройства; ° на экран. если р!о|ои|рщ=|Ьгп; ° на принтер, если р(о|оозрл|=рйтч, (.РТ7, 2.РТ2, СОМ! или СОМ2; ° в файл (р!о|оврн|=имя файла). Режим гйаг не рекомендуется для вывода 313-графиков, > в(еггасе(р!оЫет!се=еряоп9)1 > вгег(асе(р1огон(рн(=РКХ); Эти команды установили режим вывода на девятиигольчатый ЕРБОХ вЂ” совместимый принтер. > (п(ее|все(р!он)ет(се=(Ьв); Последняя команда восстанавливает вывод на экран. В %(вдовцо†версии Мар!е — эта команда не работает! 9.1.3.