автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Графо-геометрическое моделирование в САПР технических устройств

МШШСТЕРСВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ КАЗАХСТАН КАЗАХСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Р Г Б ОД

,, - На правах рукописи

| у

Есмуханов Жанузак Мухитович

ГРАФО-ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ В САПР ТЕХНИЧЕСКИХ УСТРОЙСТВ

05Л3.12 — Системы автоматизированного проектирования 05.01.01 — Прикладная геометрия и инженерная графика

ДИССЕРТАЦИЯ в виде научного доклада на соискание ученой степени доктора технических наук

Алматы 1995

Работа выполнена в Казахском национальном техническом университете.

Ведущая организация -Институт горного дела имени ДАКунаева

НАН РК

Официальные оппоненты:

Заслуженный деятель науки и техники РФ, доктор технических наук, профессор Фролов С.А. академик Инженерной академии РК, доктор технических наук, профессор Мырзахметов М.М. доктор физико-математических наук, профессор Добрица В.П

Защита состоится "й/ " Жир л\ 1996 г. в ^ часов на заседании специализированного совета Д. 14.13.03 при Казахском национальном техническом университете по адресу: 480013, Алматы, ул.акад.Сатпаева,22, Ц^К, ауд. £{) I С диссертацией в виде научного доклада можно ознакомиться в библиотеке Казахского национального технического университета.

Диссертация в виде научного доклада разослана " <14 " ¿и^ГЛ 1996 г.

Ученый секретарь специализированного совета

Сулейменов Б.А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Из анализа накопленных до настоящего времени методов геометрического моделирования вытекают следующие выводы:

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

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

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

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

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

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

графо-геометрических моделей технических устройств, применяемых при автоматизации проектирования, конструирования и воспроизведения этих объектов и процессов. К разработке именно таких универсальных методов графо-геометрического моделирования направлено наше исследование, выполненное на стыке специальностей 05.01.01 — Прикладная геометрия и инженерная графика и 05.13.12 — Системы автоматизированного проектирования.

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

Для достижения этой цели были поставлены и решены следующие задачи:

—разработка графо-геометрических моделей многомерного линейного пространства с помощью теории графов, построения графов гиперплоскостей и плоскостей любой размерности этого пространства, графов прямых и точек;

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

—разработка графо-геометрических моделей статически определимых систем, анализ условий равновесия систем, алгоритмы вычисления равнодействующей силы и крутящего момента из графо-геометрических моделей;

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

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

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

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

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

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

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

Информационной и теоретической базой исследований служили работы:

— по геометрическому моделированию: Н. Ф. Четверухина, И. С. Джапаридзе, И. И. Котова, В. И. Валькова, В. Е. Михайленко, П. В. Филиппова, А. В. Павлова, В. Н. Первиковой, Н. Н. Рыжова, Г. С. Иванова, В. Я. Волкова, 3. А. Скопеца, А. В. Бубенникова,

B. А. Осипова, Б. А. Бусыгина, С. Н. Ковалева, Б. Н. Нурмаханова и других;

— по вычислительной и компьютерной геометрии:

C. А. Фролова, В. С. Полозова, Е. А. Стародстко, В. М. Найдыша, К. М. Наджарова, М. Д. Зазулевича, П. Кастельжо, П. Безье, С. Кунса, К. А. Созонова, А. Г. Горелика и других;

— по САПР: В.И.Якунина, М. Д. Принса, Г. Шпура, Ф. Л. Краузе, Д. Райана, А. Сазерленда, Ж. С. Сарыпбекова, У. А. Тукеева, А. Д. Тузова, С. В. Цой и других.

Научная новизна работы заключается в следующем:

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

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

3. Определены основной элемент многомерного пространства (гиперплоскость), обеспечивающий простоту и наглядность отображения, и алгоритмы, позволяющие синтезировать остальные элементы (плоскость любой размерности, в том числе прямая и точка) «-мерного пространства;

4. Разработана методика составления графов равновесия статических систем, плоских и пространственных ферм, теорем и других закономерностей кинематики и динамики технических устройств; установлены основные признаки статической определенности и динамической устойчивости графов механических систем;

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

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

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

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

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

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

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

12. Определены оптимальные содержание, структура и методика изложения курсов по начертательной геометрии, инженерной графике и автоматизации чертежно-конструкторских работ, учитывающих достижения компьютерной графики и САПР; написаны и опубликованы учебники, учебные пособия и другие методические разработки на русском и казахском языках по указанным учебным

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

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

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

Реализация результатов работы. Полученные автором прикладные результаты исследований в виде методов, граф о геометрических моделей, методик, алгоритмов и пакета прикладных программ реализованы в НИПИ «Казсельэнерго», «Дирекцией тепловых сетей г. Алматы», «Каз НИПИ нефть и газ» и НИПИ Мин-водхоза Республики Казахстан.

Результаты работы внедрены также в учебный процесс Казахского национального технического университета и ряда высших учебных заведений Республики Казахстан. Материалы диссертации использованы при разработке нового спецкурса «Автоматизация чертежно-конструкторских работ», а также при написании учебника и учебных пособий по начертательной геометрии, инженерной и горно-геологической графике. На защиту выносятся:

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

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

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

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

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

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

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

—геометрия и алгоритмы построения кратчайших связывающих линий пространств с расстояниями первого порядка;

—геометрия плоскости и алгоритмы построения кратчайших связывающих линий на плоскости с полярной метрикой;

—геометрия и алгоритмы построения кратчайших связывающих линий пространства с цилиндрической метрикой;

—технология построения оптимальной конфигурации инженерных сетей средствами интерактивной компьютерной графики в диалоговом режиме;

—учебно-методические комплексы, обеспечивающие индивидуализацию и дифференциацию обучения студентов на русском и казахском языках и задающие стандарт втузовского графического образования;

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

Апробация работы. Основные результаты доложены и обсуждены: —на общегородских семинарах преподавателей начертательной геометрии и инженерной графики, г. Алматы в 1972 — 1992 гг.;

—на научно-технических и научно-методических конференциях профессорско-преподавательского состава Казахского политехнического института, а ныне Казахского национального технического университета, г. Алматы, 1971, 1972, 1974, 1978, 1979, 1980, 1982, 1988, 1993, 1994 гг.;

—на всесоюзных научных семинарах «Кибернетика графики», г. Москва, 1974, 1982 гг.;

- на зональной научно-методической конференции по прикладной геометрии и инженерной графике, г. Омск, 1975 г.;

—на всесоюзной научной конференции по САПР и инженерной графике, г. Орел, 1978 г.;

—на зональной научно-методической конференции «Роль инженерной графики и машинного проектирования в подготовке специалистов», г. Ленинград, 1984 г.;

—на Республиканской научно-методической конференции «Использование вычислительной техники при подготовке инженерных кадров», г. Караганда, 1986 г.;

— на секции «Теория изображений и ее приложения. Информатика и автоматизация» всесоюзной конференции «Современные проблемы механики и технологии машиностроения», г. Москва, 1989 г.;

—на всесоюзной научно-методической конференции «Компьютеризация и специализация обучения по графическим дисциплинам», г. Новочеркаск, 1990 г.;

—на X всесоюзном научно-методическом семинаре «Инженерная и машинная графика», г. Полтава, 1991 г.;

—на всесоюзной конференции «Компьютерная геометрия и графика в инженерном образовании», г. Нижний Новогород, 1991 г.;

—на Международном симпозиуме «Компьютерная технология: актуальные вопросы теории и практики», г. Севастополь, 1992 г.;

— на научно-методической конференции СНГ «Проблемы графической подготовки инженера: непрерывность графического образования, машинная графика, компьютерные технологии обучения», г. Минск, 1992 г.;

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

Публикация. По теме диссертационной работы опубликовано более 120 научных работ общим объемом более 150 печатных листов, среди которых учебники, учебные пособия и методические разработки на русском и казахском языках. Из них в научном докладе охвачены только 64 публикаций.

ОСНОВНОЕ СОДЕРЖАНИЕ ПУБЛИКАЦИИ

1. ГРАФО-ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ

МНОГОМЕРНОГО ПРОСТРАНСТВА, МЕХАНИЧЕСКИХ СИСТЕМ И ЭЛЕКТРИЧЕСКИХ ЦЕПЕЙ

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

1.1. Моделирование многомерного пространства [1, 4, 11, 12, 40, 45, 61]. Как известно, для изображения (моделирования) различных объектов трехмерного пространства в начертательной геометрии применяется проекционный метод. Распространение проекционного метода на случай многомерного пространства сопряжено с большими трудностями. Поэтому нами были исследованы возможности выполнения изображений элементов и-мерного евклидова прост-

ранета Е" на основе теории графов. В результате таких исследований были определены методы графо-геометрического моделирования элементов многомерного пространства. Рассмотрим многомерное пространство Еп, отнесенное прямоугольной декартовой системе координат Ох]Х2-..х„. Оказалось, что в качестве основного элемента пространства Е" удобно брать гиперплоскость Еп~] этого пространства и остальные элементы определить с помощью гиперплоскостей. Всякое линейное уравнение в декартовых координатах является уравнением плоскости. Поэтому уравнение

ао + а]Х] + (*2Х2 + ... + апхп ~ 0 (1.1)

определяет некоторую гиперплоскость. После несложного преобразования уравнение (1.1) превращается равенстно

Хк = адхо(хо = 1) +сцх] + а2Х2+ ... + (ак + 1) хк + ... +апхп, которое после введения других обозначений имеет следующий вид:

/ = п

■Ч = т*Ъ+тйк- (1.2)

1 = 1

Здесь

Ток = ао, Т/к = а/, Т2к - а2, ..., Т(к~1)к ~ ак-1>

ткк = ак+]> Т(к+1)к ~ ак+1.....Тпк = ая.

Равенство (1.2) можно изобразить сигнальным графом, представленным на рис. 1,а. Вершину хк, относительно которой решено уравнение гиперплоскости, будем называть носителем этой плоскости. В качестве носителя может выступать любая из координат X], х2, ..., хп. При необходимости можно преобразовать граф так, чтобы любая выбранная вершина стала носителем.

Хо=]

х0 = 1

х0 = 1

б)

в)

Рис. 1

Одним и тем же графом можно моделировать несколько гиперплоскостей. Если требуется изобразить две гиперплоскости, то уравнение одной из них надо решить относительно ха уравнение другой

плоскости -

относительно Ху.

Если передача дуги, идущей от вершины с единичным сигналом, равно нулю, то гиперплоскость содержит начало координат. Дуги с нулевой передачей показывать на графе не будем. Если же равна передача любой другой дуги, то гиперплоскость параллельна соответствующей координатной оси. На рис. 1,6 изображена гиперплоскость, которая параллельна ко всем координатным осям, кроме х^. Ее будем называть гиперплоскостью уровня. Рассмотренные на рис. 1,а и 1,6 графы называются общими графами плоскостей. Плоскость может быть моделирована также в виде параметрического графа, соответствующего ее параметрическому уравнению. При необходимости можно получить из параметрического графа гиперплоскости ее общий граф с носителем хк. Для этого нужно осуществить инверсию дуг соответственно с передачами 7^;, 1\22 • ■ ■ ■■ Т1к_}(к-1). т1к(к+ц. , а затем исключить параметры 1,, 12, ...,

Наряду с гиперплоскостями интересно рассмотреть плоскости любого числа измерений. Плоскость ЕГ будем задавать

параметрическим графом, приведенным на рис. 1,в. Отметим, что одномерная плоскость является прямой линией, а нульмерная плоскость — точкой. Рассмотрим их отдельно.

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

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

1X2

Х0 = Я\Т02 \ Хо = 1*\Го2 I Х0 = 1' ТЬпЧ*

I(Г^а^Т Щ'1402 - Т02)Х2 А ГЧц^^ , хо-1

^ . 1 хп

\> .

в)

г)

Рис. 2

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

начинающихся из этой всршшгы, мы получим канонический граф прямой, проходящей через две точки (рис. 2,в). Осуществляя инверсию одной из дуг, начинающихся из вершины параметрического графа прямой, а затем исключив параметр /, мы получим приведенный граф прямой (рис. 2,г). На рис. 2,6 осуществлена инверсия душ tx; с передачей ÏJо/ Тщ, а на рис. 2,г введено следующее обозначение:

fl T>0i - T0i

1 Oi - Toi - ТцТоь Тц ~ —-- ; i = 2. 3, n.

1 01 ~ Toi

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

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

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

Взаимное положение двух прямых. Если две прямые (рис. 3,а и б) в я-мерном пространстве параллельны, то выполняется равенство Ttl Tt2 Ttn

Tvi Tv2 7 vn

Если эти две прямые пересекаются, т. е. имеют общую точку, то существует граф, изображенный на рис. 3,в. Для получения последнего графа расщепляем вершину у и инвертируем все дуги, начинающиеся из этой вершины. Полученный граф совместим с графом первой прямой. Затем исключим текущие координаты х/, ..., хп и инвертируем одну из дуг, начинающихся из вершины I. Из графа, показанного на рис. 3,в, можно записать выражение для определения параметра V:

(т,0!-то,)тп+(т01~т1о0г!1

v =--—, 1-2, 3, ..., п.

Тц Тщ - Ту] Ти

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

Взаимное положение двух плоскостей. Для всяких двух плоскостей в « мерном пространстве можно определить плоскость наименшего числа измерений, проходящую через данные плоскости, а также плоскость наибольшего числа измерений, содержащуюся в обеих данных плоскостях. Первая из этих плоскостей является объединением данных плоскостей, а вторая результатом пересечения этих плоскостей. Размерности объединения и пересечения любых двух плоскостей в л-мерном пространстве исследованы Грассманом. Исходя из результатов Грассмана, выясним характер взаимного расположения двух плоскостей, заданных на рис. 4,а и б своими графами. Для этого ищем общие точки плоскостей. Осуществляем инверсию всех дуг одного из графов, начинающихся от параметров, а затем совмещаем графы плоскостей. Проверим, существует ли такой совмещенный граф. Из этого графа исключаем вершины xj, xj, х4, t2 и V2- Тогда получится граф, показанный на рис. 4,в. На основе этого графа имеем t; + vj = 1 и t] + v; = -1. Последнее противоречие показывает, что такой граф не существует. Значит, данные плоскости не имеют общих точек, т.е. не пересекаются. Каждая из этих плоскостей определяется тремя точками общего положения: точки А(1, 1, -1, 0), В(2, -1, 0, 1) и С (0, -1, 1, 0) определяют первую плоскость, а точки D (1, 2, 1, 2), Е(1, 3, -1, 0) и F( 1, -1, 2, 1) — вторую плоскость.

х0=1

в)

г)

Из этих шести точек в четырехмерном пространстве могут быть независимыми только пять. Поэтому можем исключить из рассмотрения любую из этих шести точек, например, точку F. Нетрудно проверить, что остальные пять точек являются линейно независимыми. Следовательно, объединение данных плоскостей является 4-плоскостыо, т. е. четырехмерным пространством. Из классической формулы т+1 = я+к 1 получаем, что к = 1. Отсюда следует, что данные плоскости имеют лишь одно общее направление. Для определения этого направления параллельным переносом обе плоскости расположим так, чтобы передачи всех дуг, начинающихся из вершины с единичным сигналом, были бы раны нулю (при этом плоскости проходят через начало координат). Совместив полученные графы плоскостей и исключив вершины X/, х2, х3 и х4, получим Г; = г2 = -V; = V2- Из графа первой плоскости при 11 = г2 или из графа второй плоскости при V; = -\2 получим граф прямой общего направления плоскостей (рис. 4,г).

1.2. Моделирование механических систем [4, 7, 8, 15, 25, 31, 50, 66]. Исследование механической системы методом теоретической механики включает два важных этапа: 1) вывод математических уравнений, описывающих системы и 2) изучение системы путем решения уравнений. В классических методах Ньютона, Гамильтона, Лагранжа и др. оба этапа являются довольно сложными, требующими логического мышления и специального знания. Наиболее трудным следует считать первый этап, так как ни одна вычислительная машина не в состоянии вывести математические уравнения системы. На основе теории графов удается получить строгие и упорядоченные методы вывода уравнений. А это позволяет применить современную вычислительную технику не только на втором этапе для решения уравнений системы, но и на первом этапе — для получения математического описания самой механической системы. Таким образом, разработка методов графо-геометрическо-го моделирования и решения задач теоретической механики с помощью теории графов, позволяющих широко использовать компьютер, способствует созданию САПР механических систем и улучшению качества их работы.

Статика твердого тела. Пусть твердое тело находится под действием произвольной пространственной системы сил Ру, ¥2, ..., Р

* п-

Выбираем прямоугольную декартовую систему координат Охуг. Через Гх, Ру и обозначим суммарные проекции всех сил на координатные оси х, у и г, а через Мх, Му и М2 — главные моменты всех сил относительно координатных осей л, у и г. Тогда можно построить сигнальный граф, приведенный на рис. 5,а. Передачи дуг 1\х, Т1у и Т-12 равны косинусам углов между соответствующими силами и осями координат, а передачи дуг Т1 ¡х, Т1 ¡у и Т1 ¿2 — произведениям кратчайших расстояний между линиями действия соответствующих сил и осями координат на синусы углов между ними, т. е.:

Т1х = Со.ч(¥^х); Т1у = Со*(¥^у); 7}, = Соз(¥^\);

Т11х = а1х8т(¥^х); Т*1у = а1у5т(¥^у); = а^тф^г).

(2.1)

а

х)

Здесь я1Л, а1у, а1г — кратчайшие расстояния между линией действия силы Р,- и соответствующими осями координат х, у и 2; / = 1,2, ..., п.

Возможны следующие случаи:

1. Если ^ = 0, = О, Я = О, Мх = 0, Му ~ 0 пМ2 = 0, то твердое тело, к которому приложены данная система сил Ку, ..., Г„, находится в равновесии;

2. Если Мх = О, Му = О, Мх = 0, но хотя бы одна из Гх, 1;у и ¥г не равна нулю, то система сил ¥2, приводится к равнодействующей Г, причем модуль и направляющие косинусы определяются из графа рис. 5,6;

3. Если Гх = 0, Гу - О, ^ = 0, но хотя бы один из Мх, Му и Мг не равен нулю, то система сил Ру, ¥2,..., Р„ приводится к паре сил с моментом М0, причем модуль и направляющие косинусы определяются из графа рис. 6,а;

л

4. Если хотя бы одна из Рх, Гу и Т2 не равна нулю, а также хотя бы один из Мх, Му и М2 не равен нулю, то возможны два варианта:

а) существует граф, приведенный на рис. 6,6. Тогда система сил РI, ¥2, ..., ¥п приводится к равнодействующей модуль и направление которой определяются из того же графа на рис. 6,6;

б) граф, показанный на рис. 6,6, не существует. Тогда система сил ¥), ¥2, ■ ■■,¥„ приводится к динаме.

Очень часто в задачах статики приходится определять неизвестные силы, зная, что тело находится в равновесии. В статически определимых задачах число алгебраических неизвестных не превосходит шести. Система сил Р;, Р2, ..., Р„ разбивается на два множества: множество известных сил ¥], ¥2, ..., Ру_/, ...,

..., ¥м, ..., ¥р_ь ¥р+1,..., ¥д+1, ..., ¥г_], ¥г+], ..., Р„ и множество неизвестных сил Б^, Е/., ¥р, и Рг. Инвертируя дуги Р] Рх, Рк Ру Р\ Р2, Рр Мх, Рд Му, Рг М, и исключая вершины Рх, Ру, Мх, Му и Мг, из графа рис. 5,а получим граф равновесия для произвольной пространственной системы сил. На этом не планарном графе (рис.7) вершины первого множества расположены в нижней строке. Они являются источниками и каждая из них инциндентна шести дугам. А вершины второго множества расположены в верхней строке. Каждая вершина, расположенная верхней строке, инциндентна п+4 дугам, причем п-1 из них заканчивается в ней, а пять начинается из этой вершины.

Р1 Р2

Рис. 7

Из графа равновесия легко вычислить модуль любой из неизвестных. Для этого можно пользоваться простейшими эквивалентными преобразованиями графа или правилом Мэзона.

Рассмотрим графо-геометрическую модель пространственной фермы (рис. 8,а), прикрепленной к земле шестью стержнями и имеющей форму правильной трехугольной призмы. Ферма имеет 30 стержней и 12 узлов: Л, В, С, 1, 2, ..., 9. Стержни обозначены через узлы его концов. Например, стержень, соединяющий узлы 2 и б, имеет обозначение 2-6. К узлу 9 фермы приложена сила Р, направленная параллельно стержню 7-8. Нетрудно проверить, что данная ферма является жесткой без лишних стержней. Если разложить силу Р на состовляющие по направлениям боковых граней, то расчет последней сводится к расчету двух плоских ферм. Исходя из методов сечений и вырезания узлов, построим граф (рис. 8,6), моделирующий данную ферму. Заранее можно показать, что усилии в стержнях 7-8, 8-4, 5-4, 5-1, 2-1, 2-А и А -В будут равны

Поэтому указанные стержни при составлении графа не учтены. Изолированные вершины графа соответствуют стержням, в которых усилия равны нулю. Таковыми являются вершины 8-5 и 8-9. Из графа легко вычисляются усилия в стержнях. Например, усилия в стержнях 5-2 и 6-3 определяются следующим образом:

нулю.

8-9 5-6 5-2

Рис. 8

= = 0,75-Р;

4 5 4

4 5 4 2

Геометрический смысл графа равновесия состоит в том, что он отображает многомерное пространство. Пусть размерность этого пространства т и граф имеет / носителей. При этом может оказаться, что число неизвестных к больше числа независимых уравнений статики /, т.е. приходим к статически неопределимой задаче. Граф равновесия статически определимой системы соответствует точке в многомерном пространстве и определение неизвестных величин сводится к определению координат этой точки. Граф статически неопределимой задачи может соответствовать прямой, если к - / = 1, и двумерной плоскости, если к - I = 2 и т. д.

Моделирование задач динамики. Ограничимся рассмотрением методики построения графо-геометрических моделей динамических систем на основе принципа Даламбера, метода возможных перемещений и общего уравнения динамики (принцип Даламбера-Лагранжа).

Пусть мы имеем систему из и-материальных движущихся точек и неподвижную декартовую систему координат Охуг. Выделим какую-нибудь точку этой системы. На эту точку действуют активные силы и силы реакций. Равнодействующую активных сил обозначим через Рв, а равнодействующую сил реакций — через ¥р. Тогда, применяя второй закон Ньютона для рассматриваемой точки с массой т и ускорением \У, имеем

Ка + Ь> + Рю( = 0, (2.2)

где векторная величина Тш ~ представляет собой

(даламберовую) силу инерции. Уравнение (2.2) выражает принцип Даламбера, который позволяет записывать уравнения движения в виде уравнений равновесия. Применяя принцип кинетостатики (Даламбера) для каждой точки системы, мы получим граф Даламбера для всей системы (рис. 9,а). На рис. 9,а для простоты изображения через обозначен полный шестивсршинный граф (рис. 9,6).

25

Передачи дуг графа соотношений:

Cosa;r

Даламбера определяются из следующих

Т- -

Соха^

Сощу * ¡к =-

Ти-.

гр IX'

Чр =

Со$аку СОЗОГ,-,

" " у

СоЯЩг

арх^1парх

а^БтЩу

Т _■ •* я =

а^БтсСцу

аг£тап

Т, - С°Ф1>х Со.у«уг

т Саф^ Ссиа/г

7};/ = -

Т.] -'Р арх^парх

ачу$тачу

г, _ Ь^Щ],

1 ¡'г

апБтагг

Т>2,= Т,2к =

Гд=

Щ

СояУРх . Ома,-,.

Со.ча^у ' Сохур. Соя щг

_ с^ту,2х арх3тарх

а^уБтсСцу

с&Яту^ аГ2БтаГ2

(2.3)

Р,

4-1 яР+1 рР-1

Здесь а,х, а1у, а1:, а7> аку, а1:, арх, адх, агх — углы между соответствующими силами реакций и осями координат х, у и г;

А7.г' й'у Д';г — Углы между соответствующими активными силами и осями координат х, у и г;

урх, у2}., У[22 — углы между соответствующими силами инерции и осями координат х, у и г;

а;х, оа,-,, арх, аду, аГ2 — расстояния между соответствующими силами реакций и осями координат х, у и г;

Ъ[1у, — расстояния между соответствующими активными силами и осями координат х, у и г\

С;2Х, с¡2у, с/22 — расстояния между соответствующими силами индекции и осями координат х, у иг.

Первый столбец соотношения (2.3) составлен из передач дуг, идущих из вершины Р(р, второй — из передач дуг, идущих из вершины Р/а, и третий — из передач дуг, идущих из вершины Ь\и в вершины Р]р, Ркр, Р^, Ррр, Р^ и Ргр.

Рассмотрим какую-нибудь точку системы из материальных точек и обозначим равнодействующую всех действующих на ее активных сил через ¥,а. Дадим каждой точке М, системы возможное (виртуальное) перемещение 58/8х,-, 5у,, Тогда для равновесия данной механической системы с идеальными связями необходимо и достаточно существование графа, показанного на рис. 10,а. Этот граф будем называть графом возможных перемещений. Число носителей графа возможных перемещений равно числу степеней свободы данной системы.

Применяя совместно принцип Даламбера и метод возможных перемещений к движущей системе, можно сказать, что существует граф, показанный на рис. 10,6. Этот граф будем называть графом Даламбера-Лагранжа. Из этого графа следует известный принцип: при движении системы с идеальными связями каждый момент времени сумма элементарных работ всех приложенных активных сил и всех сил инерции на любом возможном перемещении системы будет равна нулю. На рис. 10,6 приняты следующие обозначения: — угол

между силой и возможным перемещением бБ,; /3,- — угол между силой и возможмым перемещением 58,-.

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

Рис. 10

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

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

Таблица 1

№№ п/п

Наименование и схема двухполюсника

Полюсный граф

Полюсное уравнение

1. 2. 3.

Масса и земля А

т

а 0~

Пружииа о—--о

А _ В

Демпфер О..... И О

а

О-

Ъ

-О

Р(1)=В- ¿(1)

Таблица 2

№№ п/п

Наименование и схема многополюсника

Полюсный граф

Полюсное уравнение

Зубчатая передача Шг

А

ТТЛ?

ЯТЯ / '/{>

.в

г2

Рычаг (малое перемещение)

м,

V.2

-П12 О

<Р1 М2

па = 2/А2; В = В,+п212В2;

] -

<

Натяжной ролик о-

В

1

£

а Ь

ь

52 =

П21 "31

-П21 О О -Щ1 О О П2! = 12/1,;п31 = !з/1,; т = В,+т1~.

(В+-К я о

,1/,

к

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

1. Систему разбиваем на компоненты; построим полюсные графы и запишем полюсные уравнения для каждой компоненты;

2. Построим граф системы. Для чего изображаем нуль-граф, образованный полюсами компонент. Вершины нуль-графа обозначаем строчными буквами латинского алфавита. Затем соединяем полюсные графы компонент в соответствии с нуль-графом;

3. Выбираем дерево в соответствии с основным правилом: заданные последовательные переменные должны входить в дополнение графа (хорды), а заданные параллельные переменные входить в дерево (ветви);

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

М • X = 0, (2.4)

(}•¥= 0, (2.5)

матрица фундаментальных контуров; матрица отсечений;

матрица-столбец, составленная из параллельных переменных;

матрица-столбец, составленная из последовательных переменных.

5. Полученные три системы уравнений: система уравнений фундаментальных контуров (2.4), система уравнений отсечений (2.5) и система полюсных уравнений компонент дают полное математическое описание системы.

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

где М —

х — у —

коэффициентом жесткости к3 (рис. 11). В точках Е и О рычаг опирается на пружины с коэффициентами жесткости к1 и к2. В состоянии покоя рычаг занимает горизонтальное положение. Масса опорного стержня ЕВ равна т2, а масса груза В - т;. Размеры указаны на рис. 11.

Рис. 11

Данная система с двумя степенями свободы (<р и ¿) состоит из многополюсника (рычаг) и четырех двухполюсников. Полюсные графы компонент системы построены на рис. 12,а. Рычаг Пружина

ре

\' 4

8

Пружина к2 Пружина кз

4

а)

Масса т\

£

Рис.12 31

б)

Т5

7 Ъ в)

С помощью табл. 1 и 2 получим полюсные уравнения системы

<Р

^ Ч Ч 0 0 0 0

-Ь о 0 0 0 0 0

-13 0 0 0 0 0 0

= 0 0 0 Ч 0 0 0

0 0 0 0 1/к2 0 0

¡¡6 0 0 0 0 0 Ч 0

Г7 0 0 0 0 0 0 т

с?

Ж2

Рз

Ъ р6

2

(2.6)

где ф = Эу = 2;

т2(11+12) . , ¡¡+Ь ,

12

+ т2(-

Составим граф системы (рис. 12,6) и выбираем лагранжево дерево (рис. 12,в).

Уравнения фундаментальных контуров:

—1 0 0 0 1 0 0

0 -1 1 0 0 0 1

0 0 0 ~1 0 1 0

Уравнения отсечений:

1 0 0 0 1 0 0

0 1 0 0 0 0 1

0 0 1 0 0 0

0 0 0 1 0 1 0

Р4 Ъ Р7

Р1 Р2 Р6

$4 ■У5

= 0.

(2.7)

= 0.

(2.8)

1

где sj = ср; s7 = г.

Совместно решая системы (2.6), (2.7) и (2.8), получим искомые дифференциальные уравнения свободных колебаний

2

J о —/ + (к1I2, + к212г + к312з) <р + к 1123 z = 0; dt

c?z

mj —i- + к-з h(p -l-кз z = 0. dt

1.3. Моделирование электрических цепей [13, 25, 37, 46, 50. 61]. В настоящее время применение теории графов в электрорадиотехнике уже является традиционным. Специалисты научились легко составлять линейные и сигнальные графы для любых сложных электрорадиотехнических установок и рассчитывать схемы замещения, исходя из графовой модели. Методы графов позволили значительно сократить вычислительную процедуру при расчете особо сложных цепей. Однако не обращается внимание на геометрический смысл графов, получаемых при анализе и синтезе электрических цепей. Знание геометрического смысла графа тех или иных электротехнических установок позволяет более осмысленно подойти к расчету схем их замещения, заранее избежать некоторых ошибок.

Пусть мы имеем элемент г, через который течет электрический ток / (рис. 13). Тогда разность потенциалов и между зажимами элемента z равно произведению точки i на сопротивление г, т. е. имеет место граф, показанный на рис. 3 рядом с элементом с правой его стороны. Этот граф представляет собой с геометрической точки зрения одномерное пространство (прямая при z - const), так как имеет только один свободный параметр. Если имеется два элемента, которые соединены между собой последовательно (г; и Z2) или параллельно (у/ и у2), то, анализируя их графы, убедимся в том, что в этом случае они моделируются двумерным пространством (плоскость). Три элемента могут быть соединены между собой тремя способами: параллельно, последовательно и смешанно. Независимо от способа их соединения соответствующие им графы имеют общую

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

1.

2. а) б)

21 ои1

г 2 ^г>и2

У2 О,

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

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

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

г)

Д)

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

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

14,г, получим новый граф рис. 14,д. Теперь источником (независимым параметром) стала вершина с сигналом и.

Рассмотрим систему управления двигателем постоянного тока (система генератор-двигатель). Пусть генератор независимого возбуждения работает от двигателя Д/, имеющего постоянную скорость; рабочий двигатель Д2 имеет постоянный ток возбуждения. Напряжение иц, создаваемое генератором, зависит от тока возбуждения и^ - К^. Примем, что вращающий момент М двигателя Д2 пропорционален его току, т. е. М - К2 ¡2, а напряжение на нем равно ит - яК^в, где 9 — угол поворота вала нагрузки (рис.

15,а). Проанализируем граф этой системы с геометрической точки зрения. Если нагрузка обладает моментом инерции 3(кг. м ) и

моментом трения /"(нм/рад.сек), импеданс линии связи генератора Г с двигателем /Ь равен г (Ом).

гч»

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

щ

I =

Я+ зЬ

где .у представляет собой оператор .V = ток нагрузки генератора

ид - ит ид

I - -

угловую скорость вращения со вала двигателя Д2

М

03 =-

(рад/сек).

Теперь рассматриваемую систему управления двигателем постоянного тока можно моделировать сигнальным графом, показанным на рис. 15,6. Этот граф имеет 8 вершин и 8 ветвей. Вершина и1 является источником (независимый параметр). Имеется один контур обратной связи. Здесь мы должны рассмотреть 7-мерное пространство, в котором заданы 7 гиперплоскостей. Семь гиперплоскостей в 7-мерном пространстве инцидентны одной точке, которая опишет некоторую кривую при плавном изменении напряжения цу.

Если задано постоянное значение величин входного параметра и у, то из графа можно определить любую из интересующих нас величин 1/, и5, 12, М, со, в и ит. Например, угол в поворота вала нагрузки определяется из графа (по правилу Мезона)

К!К2и1

в = .--.

¿1) (л/г + + К2К})

Величины I], ие ¡2, М, оз, в и ит являются координатами точки в 7-мерном пространстве.

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

2. РАЗРАБОТКА МЕТОДИКИ ПОСТРОЕНИЯ КРАТЧАЙШИХ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ В ПРОСТРАНСТВАХ С РАЗЛИЧНОЙ МЕТРИКОЙ

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

38

проектироватнии ИС необходимо определить оптимальную ее структуру, параметры отдельных элементов, которые используются при сооружении и эксплуатации ИС. Искомые оптимальные структуры и параметры должны обеспечивать надежность, экономичность и экологичность ИС. Математические и технические расчеты, возникающие при проектировании и эксплуатации ИС, должны быть автоматизированы на базе применения современной ВТ, т, е. возникает проблема создания САПР ИС. Для этого осуществляется математическое моделирование соответствующей ИС. При разработке математической модели ИС возникает следующая геометрическая задача: требуется соединить фиксированных в метрическом пространстве дискретное множество точек и геометрических фигур линией, удовлетворяющей предъявляемые требования [37]. Для решения этой задачи необходимо иметь алгоритмы построения кратчайших связывающих деревьев в пространствах с различной метрикой.

2.1. Проблема Я. Штейиера и некоторые ее обобщенна [6, 9, 10, 20, 30]. Вначале рассмотрим построение кратчайшей связывающей линии для трех и четырех точек. Пусть требуется связать точки Л ¡, Л2 и Аз линией кратчайшей длины (рис. 16,а).

>¿2

А1

а)

б)

Рис. 16

В)

Предположим, что среди углов треугольника А ¡А2А3 нет угла, равного или большего 120°. Пусть

/\ л л

А]А2А3> А2А3А} > А3А1А2

о

Тогда кратчайшая связывающая линия представляет собой ломаную (рис. 16,6), состоящую из двух отрезков A¡A2 и А2А3. Эту линию назовем кратчайшей сетью (КС). Однако можно найти более короткую связывающую точки А¡, А2 и A¡ линию. Для этого находим точку N, из которой стороны треугольника AjA2Aj видны под одним и тем же углом, т. е. под углом 120°. Соединим точку с точками А ¡, А2 и Aj отрезками прямых. Длину полученной линии (рис. 16,в) сравним с длиной КС (рис. 16,6). Нетрудно доказать, что

\A¡A21+ \А2А j| > |A¡N\ + \A2N\ + j/íjiV|.

Линию, состоящую из трех отрезков AjN, A2N и AjN, назовем

кратчайшим деревом (КД) точек А¡, А2 и A¡. В общем случае КД

короче КС для тех же точек. В частности, когда один из углов

треугольника A¡A2A¡ равно или больше 120°, КД и КС совпадают.

Для определения положения точки N и построения КД для трех

точек существуют различные способы. Один из этих способов

заключается в следующем: на отрезке A¡А2 строим равностороний

1 2

треугольник так, чтобы третья его вершина А ' лежала на другой стороне от прямой А ¡А2 по сравнению с точкой A¡ (рис. 17,а).

Рис.

40

Точку А1'2 называют эквивалентной точкам Л} и Л2, так как отрезок А ¡А1'2 определяет длину КД точек А ¡, А2 и А т. е.

\А3Аи | = \А¡М |+ \А2Щ + \А3Щ.

Положение точки N определим с помощью чертежного треугольника

с углами 90°, 60° и 30°. Расположим его так, чтобы меньший катет

1 2

совпадал с прямой А ¡А ' и гипотенуза проходила через точку А2.

1 2

Проведем линию по гипотенузе до пересечения с прямой А ¡А в точке N, которую соединим с точкой А ¡.

Л

Л1 — Лг ( (рис. 17,а) - искомое КД3.

Рассмотренный способ нахождения КД для трех точек назовем построением Евклида.

Проводим дугу // 2 окружности, заключенную между точками А / и А2, из центра А1' (рис. 17,6). Эта дуга пересекает отрезок А3Л1,2 в точке М. Теперь нетрудно увидеть, что длина КД для точек А ¡, А 2 и Аз будет равна сумме двух отрезков А]А2 и А3М. Это положение используется при разработке алгоритмов построения КД путем модификации известного алгоритма Прима для КС. В модифицированном алгоритме вводится понятие расширенного фрагмента, сущность которого заключается в следующем: находим вершины А1' я А2'1 двух равностороних треугольников, построенных на отрезке А ¡А2. Проводим дуги и Д/ через точки А / и А2 из центров А1'2 и А2,1. Фигура, ограниченная дугами /¡ 2 и Д/, является расширенным фрагментом точек А]\\А2 (рис. 17,в).

Определение: расстоянием от точки В до расширенного фрагмента называется минимум всех расстояний

4 = \BMii

где точка М,- принадлежит расширенному фрагменту.

Например, расстоянием от точки А $ до расширенного фрамента точек Л/ и А2 является отрезки А(рис. 17,6). Отрезок А$М

определяет величину удлинения КД точек А ¡, А2 и А^ при переходе от КД точек А/иА2.

Покажем построение КД для четырех заданных точек А ¡, А2, А3и А4( рис. 18).

1-шаг. Определяем пару точек с минимальным расстоянием. Из шести отрезков А ¡А 2, А 2А А ¡А 4, А ¡А 4, А ¡А 3 и А2А4 кратчайшей длиной обладает отрезок Л2Л Поэтому на первом шаге объединяются точки А^ и А3, т. е. строится КД2. Находим эквивалентную точку А ' и проводим дугу /2 $ из этого центра. Оставшиеся точки А; а А4 расположены от прямой А2А^ правее, поэтому в проведении другой дуги /32 расширенного фрагмента нет необходимости (рис. 18,а). Таким образом, на первом шаге определяется пара точек с минимальным расстоянием, строится для них КД и расширенный фрагмент.

2-шаг. Сравниваем расстояния между оставшимися точками А А4 и фрагментом. Фрагмент и точка А 4 обладают минимальным расстоянием, равным длине отрезка А4М¡. Это означает, что на втором шаге к КД2 точек А2 и А$ надо присоединить точку А4.

Евклидовым построением находим КДз для трех точек А 2, А з и А4

~> з

(рис. 18,6). Строим расширенный фрагмент точек А" и А4, для чего находится эквивалентная точка А ,3~4 и проводится дуга ]2,з-4 из центра А2,3^(рис. 18,в). Строить другую эквивалентную точку А4"2,3 и Дугу/4-2,3 не будем.

3-шаг. Сравниваем расстояние от точки А] до точки А2 и до расширенного фрагмента (дуги /¿3-4). Точка А] ближе к фрагменту, чем к точке А2: \А]А2\ > \А]М2\. Поэтому сначала строим построением Евклида КДз для точек А ¡, А4 и А2' , а затем-для точек Ы], А2иАз (рис. 18,г). Искомое КД4 имеет следующую топологию:

А]-М1 ( А2 \ N2 '

•у э_А

Длина найденного КД4 равна длине отрезка А ¡А ' .

¿2.3-4

Проблема Я. Штейнера: дано с пространстве с евклдовой метрикой дискретное компланарное множество точек А ¡, А2,..Лт и требуется построить линию, проходящую через данные точки и имеющую кратчайшую длину. Искомая кратчайшая линия представляет собой дерево и состоит из связанных между собой отрезков прямых. Действительно, если искомая кратчайшая линия имеет замкнутый контур, то можно было бы удалить любое ребро этого замкнутого контура, не нарушая связанности линии и тем самым укоротить длину линии. Последнее противоречит предположению о том, что она имеет кратчайшую длину. Далее предположим, что искомая линия имеет ребро /4,-Лу, отличное от отрезка прямой. Тогда это ребро можно заменить отрезком прямой и тем самым укоротить длину линии, а это снова противоречит предположению о том, что она имеет кратчайшую длину. Таким образом, задача состоит в том, чтобы для заданного компланарного множества точек А], А2, ■■•,Ат и дополнительно вводимых точек N ¡, N2, ..., найти КД, связывающее их. Точки А А у, ...,Ат неподвижны (координаты их заданы), их будем называть исходными. Точки N1, N2, ..., подвижны (координаты их неизвестны), их будем называть точками Штейнера или свободными вершинами искомого дерева. Сложность проблемы Штейнера обусловлена двумя обстоятельствами:

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

2) надо определить, в какой последовательности соединить исходные вершины А¡, А2, ..., Ат и свободные вершины И/, Ы2, ..., Ып с тем, чтобы связывающее дерево имело возможно кратчайшую длину, т. е. найти оптимальную топологию дерева.

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

Отметим, что проблема Штейнера является частным случаем более общей проблемы об оптимальных связывающих деревьях, сформулированных в работе [21] автора. Даны три вещественных числа и m фиксированных точек А/, А2, ■■■, Ат в метрическом компактном пространстве, в котором расстояние между точками Л,- и * Aj равно длине геодезической, соединяющей их; требуется найти целое число nun точек Nj, N2, .... Nn и построить дерево Д на вершинах А¡, А2, Ат, N], N2, ..., N„ так, чтобы минимизировать сумму

in п

кд) + ш+ «X® (Nß+ Уп ' ¡=i j=i

ITC 1(Д) ~ длина дерева Д; т(А¡), co(Nj) ~ число ветвей, сходящихся в вершинах Л,- и Nj дерева Д. Известны некоторые частные случаи этой проблемы оптимальных связывающих деревьев:

1) пусть ß = 0 и а > у » 1. Тогда задача сводится к построению

точки N, для которой^ минимальна. Точку N называют точкой

i=l _ „ „ „ _ _ . наименьших расстоянии. Этот случаи, именуемыи задачей Вебера,

возникает при выборе места расположения электрической станции,

снабжающей энергией потребителей А ¡, А2, . ■ Ат;

2) пусть а = 0 и max(ß, у) » 1. Тогда задача сводится к построению кратчайшей связывающей сети (КС);

3) пусть max(ß, у) » а » 7. Тогда задача сводится к построению кратчайшего неразветвленного дерева, вершинами которого служат

только исходные точки Aj, А2.....Ат. Этот случай в литературе

именуется задачей нахождения кратчайщего гамильтонового пути;

4) пусть а = ß = у = 0. Этот случай именуется в литературе проблемой Штейнера.

2.2. Алгоритмы построения кратчайших связывающих деревьев в пространствах с евклидовой метрикой [3, 5, 17, 19, 27, 28, 56, 62]. Для построения КД для заданного компланарного множества точек А ¡, А2, -.., Ат определяются дополнительные точки NN2, .... Nn,

которые уменьшают длину КД„, до возможного минимума. Положения и количество точек Л'/, М2, .... Nn заранее неизвестно, тогда как точки А¡, Ап, ..., Ат являются фиксированными. Заданные точки назовем /(- точками, а дополнительно вводимые — /У-точкамн. Установлены следующие необходимые свойства КД:

1) число Лоточек не может быть более чем т-2, где т - число А- . точек (п < т-2);

2.) в каждой //-точке сходятся ровно три отрезка, которые будут равнорасположснными (углы между ними равны 120°);

3) в каждой А-точке могут сходиться не более трех отрезков. Случай, когда Л-точке сходятся три отрезка, является редким исключением. Как правило, из Л-точки выходит один или два отрезка;

4) угол между двумя отрезками, сходящимися в одной точке, не может быть менее чем 120°;

5) КД для любого конечнного множества Л-точек может быть построено конечным числом построений Евклида.

Если определено число Лоточек и их расположение, то КД можно построить алгоритмом Прима, исходящим из принципа наименьшего удлинения на каждом шаге построенной до этого КС. Этот принцип оставим без изменения. Для определения удлинения КД используются расширенные фрагменты. Теперь приведем один из алгоритмов, разработанных автором для построения КД для множества точек А}, А2, ..., Ат.

1. Выбирается две точки из числа Л-точск, расстояние между которыми больше, чем для любой другой пары. Строится КД2 для этих двух точек.

2. Каждый последующий шаг алгоритма заключается в переходе от КД,-, построенного для группы из i точек, к КД,-+; для группы из /+/ точек. При этом определяются:

а) на основе принципа наименьшего удлинения КД очередная (1+1)-я точка, которая должна быть подключена к КД,-;

б) построениями Евклида конфигурация КД,+], которому ранее найденное КД, войдет в общем случае уже в частично измененном виде.

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

Применение этого алгоритма покажем на примере построения КД для множества из десяти точек А¡, А2, А¡0 (рис. 19).

1-шаг. Сравнивая расстояния между данными десятью точками, определим минимальное из них. Таким минимальным расстоянием обладают точки А ¡и А2. Соединим их отрезком прямой и построим расширенный фрагмент, т. е. проведем дугу¡¡ 2 из центра А1'".

2-шаг. Сравнивая расстояния между остальными точками и расширенным фрагментом (т. е. дуги Д2), определим пару с минимальным расстоянием. Такой парой оказались точки Л5 и А у. Соединим их в КД? и построим дуги Д 7 и /75 (которые на рис. 19 не показаны).

3-шаг. Сравнивая расстояния между остальными шестью точками и двумя расширенными фрагментами, находим, что ближайшими соседями являются точка А3 и фрагмент А¡~А2. Причем точка А3 расположена ближе всего точке А2. Поэтому она соединяется с этой точкой отрезком прямой, в результате получаем КДз со структурой А ¡-А2-А 3. Находим эквивалентную точку А1,2'3 и строим дугу /'

4~шаг. Сравнение расстояний между пятью точками Ал, А(5, А#, Ау и Аю, двумя расширенными фрагментами позволяет определить ближайших соседов: А^ и фрагмент А ¡-А -¡. Так как точка Л б ближе к точке А5, присоединим ее к точке А$ отрезком прямой. В результате получим фрагмент А у-А^-Л^.

5-шаг. Парой с минимальным расстоянием оказались точка А 8 и фрагмент А7-А5-АТочка Аз расположена ближе к А/, поэтому она

присоединена отрезком прямой с точкой A¿ и получен фрагмент А6~А5-Лт-А8.

6-гиаг. Сравнивая расстояния между тремя изолированными точками А4, А9, А10 и двумя фрагментами Aj-Aj-Aj и А6 Ау-Аy--Ag, определим пару с минимальным расстоянием. Такой парой является точка А4 и дуга /57 фрагмента Ag-A$-Aj~Ág. Построением Евклида получаем КД3 точек A4, A¡ и А Тогда КД5 точек A4, A¡, Л& Aj\\ As имеет следующую структуру:

/А5—А6 A4~N(

\At~A8.

КД^ точек ААб, Ау и Ag вошло в дерево КД5 частично деформированном виде. Проводим дуги/4-5,7 я/5,7-4.

7-шаг. Ближайшими соседями оказались дуги /¡,23 и /5,7-4-Поэтому КД^ точек A¡, А 2, A¡ и КД5 точек А4, A¡, Ag, А7, Ag объединены в одно КД8. Сначала построение Евклида применяем для точек А1,2, А3, А5'1'4 и находим точку N¡, а затем — для точек Л'/, А ¡, А2 и находим точку N2. Далее построение Евклида применяем для точек А4, N¡, А5'7 и находим точку N3, наконец - для точек А5, А7, N¡ и находим точку N4.

8-шаг. Сравнивая расстояния между точками Ад, А ¡о и от них до фрагмента, определяем, что очередной присоединяемой к КД# точкой является точка А ю- Проводим отрезок AgA }0.

9-шаг. Остается подключить точку Ад к КДр. Ближайшим соседом

точки А9 является дуга /78-Ю- Поэтому сначала построение Евклида

' 7 S

применяем для точек Ад, А ¡о, А ' и находим точку Aj, а затем - для точек N5, А7, As и находим точку А^. Таким образом КД;о для заданного множества из десяти точек A¡, А2, ■■., A¡q имеет следующую структуру:

А3

л5-А6 к/ А8

4А7~М/ Ад А ю.

Длина / найденного КД™ равна сумме длин трех отрезков А1^А5^4,А}Л(1, Л9А18-10{рис. 19):

/ = \Аи'3А5-™\ + \А5А6\ + [А^А7-8'101.

На пути отрезка КД могут оказаться ограничения и запреты. Кроме того, выгодно трассу ИС проложить вдоль существующей дороги. Учет всех таких обстоятельств проводится путем расположения на местности определенных промежуточных точек (фиктивных пунктов), позволяющих обходить запретную зону. На рис. 20 штриховыми линиями изображено КД4 точек А¡, А2, А3И А4. Отрезок N¡N2 проходит через запретную зону. Выбрав фиктивную точку Р, позволяющую обходить запретную зону, находим оптимальную конфигурацию КД^ (толстая линия на рис. 20).

В качестве примера на рис. 21 изображена схема трасс водопровод совхоза «40 лет Октября». Пункты потребления воды обозначены белыми кружочками, фиктивные пункты — черными кружочками и подземные источники воды — треугольниками. 1, 2, ..., 30 — потребители воды; 31, 32, ..., 37 — фиктивные пункты с нулевым водопотреблением; 38, 39 — подземные источники водоснабжения. Штриховыми линиями показана конфигурация водопроводной сети, заданной проектировщиком. Протяженность этой существующей водопроводной сети составляет 171,9 км. Конфигурация водопроводной сети, найденная алгоритмом Прима, изображена сплошной тонкой линией. Протяженность КС равна 149,3 км. Конфигурация водопроводной сети, найденная предложенным алгоритмом построения КД, показана на рис. 21 сплошной толстой линией. Протяженность КД составляет всего 140 км.

В работе [62] была предложена технология определения кратчайших связывающих линий средствами интерактивной машинной графики. Трудность таких многоэкстремальных задач комбинаторного типа обусловлена наличием многих локальных оптимальных решений, удовлетворяющих все выявленные свойства КД, и отсутствием критерий достаточности. Самым надежным является метод перебора всех возможных вариантов. Для этого необходим — перечень всех допустимых связывающих данное множество линий. Число всех связывающих деревьев обозначим через Р(т, п), где т — число исходных неподвижных точек и п -число подвижных точек Штейнера.

Число деревьев с вершинами только в исходных точках будет равно

Р(т,0) = (>п-2)!С2т (2.1)

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

Другим предельным случаем является полное дерево, в котором число точек Штейнера равно максимально возможному (п = т-2).

Число полных связывающих т неподвижных и ш-2 подвижных точек рано

т

БОп, т 2) = П (21 -3). (2.2)

¡=3

КД, связывающее заданное множество из т точек, определяется сравнением длин всех с 0, 1, 2, ..., т-2 точками Штейнера. Число всех связывающих т точек дервьев, претендующих стать КД, определяется по формуле:

п=т-2(т+п-2)!С"п F(m) = £ --(2.3)

п = 0 «!?

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

Число связывающих линий резко возрастает с ростом количества элементов в исходном множестве. Например, число связывающих деревьев равно: 4 при т = 3; 27 при т = 4\ 270 при т - 5\ 3 645 при т = 6; 62 370 при т = 7 и 1 163 295 при т = 8. Поэтому практически при т > 8 сравнение между собой всех допустимых вариантов связывающих линий становится невозможным для современной ВТ. Наиболее перспективное направление состоит в разбиении множества фигур на подмножества, состоящие не более чем из 8 точек. Причем желательно, чтобы каждое подмножество было полным компонентом. Число полных деревьев Штейнера равно: 1 при т = 3; 3 при т = 4\ 15 при т = 5; 105 при т = 6\ 945 при т = 7 и 10 395 при т = 8. Формализовать процесс разбиения данного множества на полные компоненты очень трудно. Поэтому предлагается решить такие задачи в диалоговом режиме, где разбиение осуществляется опытным специалистом, а построение КД для отдельного подмножества — с помощью компьютера автоматически.

Такая технология проектирования ИС в диалоговом режиме позволяет рационально использовать возможности специалистов и ВТ.

Многомерное обобщение проблемы Штейнера. Пусть в ^-мерном пространстве дано множество точек A¡, А2, ■■■, Лт. Тогда в пространстве можно построить кратчайшее дерево, связывающее заданное множество точек. Можно доказать, что КД в пространстве f!: обладает указанными выше свойствами. Действительно, ветви не могут пересекаться в точках за исключением его вершин. Докажем, что в каждой вершине КД не могут сходиться более трех ветвей (третье свойство). Предположим, что КД имеет вершину X с четырьмя ветвями. Тогда один из углов между ветвями, сходящимися в точке X, меньше 120°. Пусть X¡XX2 < 120°. Тогда путем введения дополнительной вершины (точки Штейнера) можно уменьшить длину КД, что невозможно. В дополнительно вводимых Лоточках не могут сходиться менее трех ветвей, иначе не будет уменьшения длины дерева. Отсюда КД обладает вторым свойством. Покажем наличие первого свойства. Число ветвей, ведущих в Л-точки, больше т/2, в JV-точки ~ Зл/2, а дерево с ш+п вершинами имеет т+п-1 ветвей. Поэтому (т+Зп)/2 <т+п-1. Отсюда п <т-2.

Распространение предложенного выше алгоритма на многомерное пространство (к ¿ 3) сопряжено со значительными затруднениями, связанными с необходимостью построения эквидистационных поверхностей. Поэтому разработан еще один алгоритм, использующий операцию «введения Штейнера» и «штейнализации». Применим этот алгоритм для построения КД5 точек А,(12, I, 1), А2(9, 6, 9), А3(5, 1, 5), А4(3, 6, 10) и А5(1. 4, 7) в пространстве Е3. Построение будем выполнять на эпюре Монжа (рис. 22). Сначала построим КС алгоритмом Прима. КС изображена сплошной тонкой линией и имеет суммарную длину, равную 26,9. Далее оптимизируем КС «введением Штейнера», т. е. определим точку Штейнера N¡ для тройки A¡, А2, Aj и точку Штейнера N2 для тройки А ¡, А 4, А 5. Полученное связывающее дерево (оно изображено на рис, 22 штриховой линией) имеет 7 вершин и 6 ветвей, а суммарная его длина 24,4. Теперь «введение Штейнера» можно применить для тройки N], N2, Aj. Тогда появляется новая дополнительная точка

Штейнера N3. Новое связывающее дерево имеет длину 24,2 и изображено на рис. 22 толстой сплошной линией. Нетрудно заметить, что точки АГ1 и N2 перестали быть точками Штейнера. Определим действительные точки Штейнера: ЛГу — для тройки Л ,, Л2, ЛГ? и И2~ для тройки М3, А4, А5. После определения точек /V; и М2 точка А'3 перестает быть точкой Штейнера для тройки Л^, М2, А3. Перенеся точку Ы3 в действительную точку Штейнера N3 для тройки /V/, Ы2, А3 укоротим длину связывающей линии. Такую операцию назовем «штейнализацией». Эта процедура продолжается до тех пор, пока относительное улучшение не окажется меньше заданной величины

?

Минимальные деревья. На плоскости ЕГ дано множество точек А ¡, А2, ■ ■-, Ат, в каждой из которых сопаставлена некоторая положительная величина 1, 2, ..., т. Величину р1 назовем весом точки Аг Требуется определить число п, расставить на плоскости п дополнительных точек и построить дерево миниималыюго веса с вершинами в точках А/, А2, ..., Ат, ЛГ;, ..., Nn. Весом ветви [Л,ЛГ] называется величина р^А^М^, весом дерева — сумма весов всех ветвей дерева. Дерево, удовлетворяющее условиям сформулированной задачи, назовем минимальным (МД).

Для построения МД для трех точек А], А2, Аз с весами р¡, р2, рв проведем две окружности с центрами в точках А} и Л2 (рис. 23,а).

в) б)

Рис. 23

Радиус первой окружности равен р^АхА^/рз, а радиус второй —

р^А/А2Урз. Точка А1'2 пересечения этих окружностей эквивалентна

точкам А/ и А2. Окружность, описанная вокруг треугольника 12 12 А]А2А ' , пересекает прямую А3А ' в точке N. Тогда искомое МД

состоит из четырех вершин А ¡, А2, А& N и трех ветвей [Л;Л/], [А2Щ,

[А зЩ. Вес МД для данных трех точек будет равен сумме

pMiN\ +p2\A2N I + p3\A3N\.

Если pi >P2 + pj, то точка N совпадает с точкой А¡. Если p2-Vit + Рз или р3 > pj+p2, то N = А2 или N = А3. Приведенное построение МД для трех точек назовем обобщенным построением Штейнера. Ясно, что если множество КД может быть построено конечным числом построений Штейнера, то множество МД также может быть построено конечным числом обобщенных построений Штейнера. На рис. 23,6 показано построение МД для точек Aj, А2, Ар А4, Aj, образующих выпуклый пятиугольник, в предположении, что они

17 Л 1

имеют веса pj, Р2, Рз, Рф Ps- Определены эквивалентные точки А ' А ' и АОкружность, проведенная через точки А1'2,А4'5 и д(1,2)(4,5)^ пересекает прямую А3Ав точке N]. Окружность, проведенная через точки А ¡, А2 и А1,2, пересекает прямую A1,2Nj в точке N2, а окружность точек А4, А5 и А4'5 пересекает прямую А4, Nj в точке N3. Вес построенного МД5равенр3\А

Проблема Штейнера па поверхности <р в пространстве Е3. Допустим, что поверхность q> не имеет никаких особенностей. Тогда для множества точек А¡, i ~ 1, 2, .... т и Л,- е q> можно поставить задачу на построение связывающей линии кратчайшей длины. Эта линия поверхности по прежнему будет представлять собой дерево с дополнительными вершинами типа N. КД на поверхности <р имеет свойства, которые идентичны свойствам в пространстве Докажем, что для КД на поверхности <р остается в силе свойство дополнительнных вершин, т. с. ветви, исходящие из ¿V-точки, образуют между собой углы, равные 120°. Пусть А, В, С~ различные точки поверхности и точка N е (р минимизирует сумму длин p(N, А), p(N, В), p(N, С) геодезических линий, соединяющих точку N соответственно с точками А, В и С: p(N, А) + p(N, В) + p(N, С) = min. Покажем, что каждый угол при N между геодезическими линиями AN, BN, CN равен 120°. Принимаем, что p(N, А) = а; p(N, В) = b; p(N, С) = с. Рассмотрим геодезический эллипс е, т. е. множество точек Z, для которых p(Z, А) + p(z, В) = а + b и геодезическую окружность p(Z, С) = с. Эти замкнутые кривые касаются в точке N, иначе точка У будет внутри обоих кривых, p(Y, А) + p(Y, В) < а + Ъ и р(У. С) < с. Это противоречит условию, согласно которому точка N минимизирует приведенную выше сумму.

Поскольку геодезическая NC встречается с окружностью p(Z, С) = с под прямым углом, она пересекает эллипс ортогонально. По результатам классической дифференциальной геометрии углы а тл fi равны (рис. 23,в). Таким образом, AÑC = BÑC. Аналогично, рассматривая геодезические эллипсы p(Z, А) + p(Z, С) = а + с и p(Z, А) +p(Z, С) = b + с, докажем, что ANB = BÑC и аРв = ANC. Отсюда следует, что каждый угол при N между геодезическими линиями AN, BN, CN равен 120°. Если ABC — геодезический треугольник на поверхности <ри угол при вершине А меньше 120°, то

р(А, В) + р(А, С) >p(N, А) + p(N, В) + p(N, С).

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

Построение КД, связывающего компланарное множество плоских фигур. Тривиально, что разработанные алгоритмы могут быть распространены для построения КД, связывающего заданное множество шаров. В частности, для определения КД, связывающего компланарное множество кругов k¡, к2, ..., кт с центрами в точках A¡,

А2, .... Ат и радиусами г}, г2, ..., rm k¡ = 0), достаточно определить КД точек A¡, Л2, ..., Ат. Если имеется компланарное множество различных фигур /}, f2, ..., f¡ = 0,f¡ * 0), то надо определить расстояния между ними. Расстояние между фигурами fj и Ji определяется как min{\FjF¡\}, где точки Fj е fj и F¡ е f¡. При этом надо строить области Дирихле вокруг фигур fj и ft. В работе предложены способы определения областей Дирихле для различных фигур, что позволило разработать методику построения КД, связывающего компланарное множество плоских фигур.

2.3. Методика определения кратчайших связывающих линий в пространствах с расстоянием первого порядка и с полярной метрикой

[2, 6, 14, 16, 18, 42]. В результате исследования практических приложений алгоритмов построения КД для оптимизации инженерных сетей возникла необходимость в рассмотрении наряду с обычным евклидовым расстоянием и других видов расстояний.

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

Для того, чтобы дерево служило моделью электроосветительной сети, оно должно удовлетворять следующему требованию: ветви дерева должны «расти» только в высотном, широтном и глубинном направлениях. Следовательно, необходимо рассмотреть метрическое пространство, в котором расстояние между точками А, (х¡, у ¡, и А2(х2, у2- 22) определяется по формуле

й(Аь А2) = \х, - х2\ + IVI ~У2\ + I2/" г2\- (2.4)

Это расстояние называется расстоянием первого порядка в отличие от евклидова расстояния. Геометрия пространства, где расстояние между точками определяется по формуле (2.4), изучена не достаточно. Чтобы иметь некоторые представления о метрическом пространстве с расстоянием первого порядка отметим, что роль окружности играет параллелограмм, роль сферы — октаэдр. На плоскости с евклидовым расстоянием две точки могут быть соединены, как известно, кратчайшей линией единственным образом.

На плоскости с расстоянием первого порядка существует бесчисленное множество линий, соединяющих две точки кратчайшим путем. Исключение составляют точки, расположенные на одной прямой, параллельной координатной оси х(у ши г). Путем модификации вышеприведенного алгоритма определения КД в пространстве с евклидовым расстоянием получена методика решения задачи о кратчайшем соединении точек в пространстве с расстояниями первого порядка. При этом упрощается построение эквидистанционой поверхности, представляющей собой объединение многогранников трех типов. На рис. 24 приведен пример КД/0, связывающего точки А¡(21, 8, 8), А2(19, 1, 11),А3(18, 17, 4), А4(1б, 3, 9), А5(14, 10, 13), Аб(10, 6, 1), А?(8, 14, 9), А8(6, 8, 16), Л9(5, 16. 5), А ¡о(2, 5, 11) в трехмерном пространстве с расстояниями первого порядка.

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

КД на плоскости с полярной метрикой. Для точек А1(р1, (р1) и А2(Р2, <Рг) плоскости с фиксированной полярной системой координат можно определить функцию

\Р1+Р2- если \(р1-(?2\ ¿2; й(А,, А2) = |р1- р21 + |р1(<р1 - (р^, если р2 < р2; (2.5) ИР/ - Р21 + \Рг(<Р1 - 9А если р1>р2,

где рг, ср1 — полярные координаты точки Л?; р2, (р2—полярные координаты точки А2.

Вещественное число с1(А1, А2), определяемое по формуле (2.5), названо полярным расстоянием между точками А] и А2. Действительно, функция (2.5) обладает свойствами: неотрицательности, симметричности, невырожденности и неравенствам треугольника. Нами исследована геометрия плоскости с полярной метрикой. В частности, на плоскости с полярной метрикой существует четыре различных вида отрезков, названных радиальным, дуговым, магистральным и радиально-дуговым. «Окружность» также имеет четыре различных вида. Если радиус меньше расстояния от центра до полюса, то окружность имеет форму четырехугольника, две стороны которого являются отрезками спирали Архимеда и другие две стороны ~ отрезками гиперболической спирали. На рис. 25 приведен пример КД/5, связывающего множество из 15 точек плоскости с полярной метрикой.

КД в пространстве с цилиндрической метрикой. В трехмерном пространстве с фиксированной цилиндрической системой координат для множества точек А/(р0 фь г{) можно поставить задачу о построении кратчайщего связывающего дерева, имеющего ветви трех типов: тип р, тип ср, тип 2. Ветви типа р представляют собой отрезки прямых, пересекающих ось г под прямым углом. Ветви типа (р представляют собой отрезки дуг окружностей с центром на оси г, а ветви типа г — отрезки прямых, параллельных оси г. Расстояние

между точками Aj(pj, q>j, zj) и A2(p2, <P2, z2)> вычисляемое из равенства

f ¡Pi - P2I + ¡Pi(<Pi - V2)I + 121 ~ Ы если pi < p2;

d(A¡, A2) = (2.6)

1-1 Pi - P2I + W<Pl "92)1 + \z]~z2\. если pj>p2,

где pj, q>j, zi — цилиндрические координаты точки A¡, p2, cp2, z2— цилиндрические координаты точки А и |Ф1 -ф2| < 2, названо цилиндрическим расстоянием. Отметим некоторые частные случаи;

1) если р,- = var, (pt = const, z,- = var, то задача сводится к построению КД для компланарного множества точек с расстоянием первого порядка;

2) если Pi = const, <pt = var, zf = var, то данные точки принадлежат поверхности цилиндра вращения. Построив развертку цилиндра, можно свести этот случай к предыдущему;

3) если р{ = var, <pi = var, z,- = const, то данные точки принадлежат плоскости, перпендикулярной оси г. При этом определяется связывающее КД на плоскости с полярной метрикой.

3. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИЙ В УЧЕБНЫЙ ПРОЦЕСС

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

Анализ учебников и учебных пособий по начертательной геометрии и инженерной графике показал, что большинство из них не отвечает современным требованиям, устарели как по содержанию, так и по методике изложения. Они написаны без учета изменений в учебных программах средних учебных заведений и содержат ненужные и второстепенные материалы, которые приводят к бессмысленным перегрузкам обучающихся. В них отсутствуют новые научные результаты, необходимые для компьютерной графики и САПР, что снижает качество подготовки специалистов. Поэтому возникла необходимость в определении и формировании оптимального содержания и создании рациональной методики изложения материалов в учебниках и учебных пособиях по графическим дисциплинам [29, 46, 50, 52, 57, 59].

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

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

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

во-вторых, получаемый студентом объем знаний должен быть достаточным, чтобы достичь необходимого уровня развития студентов и способность к переходу на более высокий уровень;

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

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

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

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

—постоянную практическую направленность теоретического материала;

—обязательную постепенность перехода от отдельных геометрических фактов к их обобщениям;

—равномерность распределения теоретических сведений по всему курсу;

— обязательность перехода от простого к сложному;

—постоянная опора на наглядно-интуитйвные представления;

—посильность и целесообразность геометрического языка (терминологии и символики).

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

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

—курс начертательной геометрии и инженерной графики должен быть направлен на формирование содержательных геометрических обобщений;

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

Этот методический принцип реализуется через содержание обучения по следующим направлениям:

—последовательный переход от известного материала к логически с ним связанному материалу;

—включение новых геометрических знаний и опыта в системеу уже усвоенных знаний и опыта;

—постепенное повышение уровня обобщения геометрических понятий с систематическим включением понятий предыдущего уровня обобщения в обобщенное геометрическое понятие;

—доступность вводимых геометрических терминов и символов и их практическую целесообразность на этапе первого ознакомления с ними;

—планомерность и постепенность в накоплении опыта применения геометрических методов (эпюр Монжа, аксонометрия, перспектива и др.).

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

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

Начертательная геометрия [22, 24, 38, 39, 48, 49, 53, 63, 64]. Учебный план каждой специальности представляет собой сложную суперсистему, а каждая учебная дисциплина является ее подсистемой. Одной из таких подсистем является начертательная геометрия, которая имеет вход и выход. Вход это учебные предметы (геометрия, черчение и др.), изученные в сузах и необходимые для понимания начертательной геометрии. Поэтому методика преподавания и изложения начертательной геометрии определяется уровнем подготовленности поступающих на первый курс студентов.

66

Изменения учебных планов и программ сузов должны учитываться в учебной литературе вузов. Выход это учебные дисциплины, которые базируются на знании по начертательной геометрии. К ним относятся большинство общетехнических дисциплин и дисциплины по специальности. Содержание начертательной геометрии должно быть таково, чтобы обеспечить глубокое и осмысленное понимание студентами указанных выше дисциплин. Это достигается согласованием рабочей программы заведующими соответствующих кафедр. Таким образом, вход определяет методику преподавания данной дисциплины, а выход — ее содержание. В свою очередь каждая учебная дисциплина является достаточно сложной системой по отношению всех разделов, определяющих ее содержание и рассматриваемых как подсистемы. Систему начертательной геометрии можно расчленить на шесть подсистем: методы построения обратимых чертежей; линия и поверхность; геометрические преобразования чертежей; позиционные задачи; метрические задачи и комплексные задачи. Каждая из этих подсистем имеет некоторую самостоятельность, что подтверждено существенно выраженными внутренними связями между отдельными ее темами. Связи между педсяошами на рта. 26 покачаны стрелками. Стрелка, направленная, например от первой системы ко второй, означает, что при изучении второй системы используются некоторые сведения из первой системы. Изучение этих связей позволяет определить оптимальную последовательность изложения этих подсистем. Из рисунка видно, что подсистема методов построения обратимых чертежей не зависит от остальных подсистем. В то же время все остальные подсистемы зависят от нее. Поэтому она должна излагаться в начале курса. К подсистеме комплексных задач идут стрелки от всех подсистем; это означает, что ее следует изучать в последнюю очередь. Завершением курса служит обзорная лекция, посвященная взаимосвязям между отдельными подсистемами. Как видно из вышеизложенного, графо-геометрическое моделирование позволяет определить оптимальную структуру начертательной геометрии. При этом решается задача: найти кратчайший путь, содержащий все вершины графа. Кроме оптимальной структуры изложения материалов графо-геометрическое моделирование раскрывает, в какой степени связаны между собой отдельные темы курса. Особое

Вход

Выход Рис. 26

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

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

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

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

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

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

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

Инженерная графика [23, 32, 33, 35, 36, 51, 58, 60]. За последние годы инженерная графика перетерпела как качественные, так и количественные изменения. Теперь она изучает наиболее общие закономерности построения графических изображений, основанные на современные разделы математики и вычислительной техники. Некоторые темы курса, считавшиеся ранее важными, потеряли свое значение, и наоборот, вопросы, которые, признавались второстепенными, ныне оказались актуальными. Появилось бурно развивающееся новое направление — машинная графика. Кроме того, в программу инженерной графики необходимо включить результаты новых научных исследований и изложить ее на уровне современных требований. Таким образом объем информации, включаемой в общий курс инженерной графики, увеличился в несколько раз. Нужна такая методика преподавания инженерной графики, которая позволила бы при имеющейся сетке часов в учебном плане изложить этот предмет на уровне, соответствующем требованиям стандарта специалиста. Здесь мы имеем дело, с математической точки зрения, с задачей на оптимальное управление. Целевой функцией служит хорошо разработанная рабочая программа.

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

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

пособия и методические указания, которые наряду с традиционными материалами содержат новые, полученные нами результаты. Например, в рабочие программы специальностей 2101, 2106, 2201 и 2206 включена тема «Схемы». Вводим понятие о наглядности схемных изображений. Схема считается наглядной, если сс легко прочитать. Прочитать схему — это означает извлечь содержащуюся в ней информацию. В результате сравнения и анализа различных изоморфных схем было установлено, что наглядные схемы имеют минимальное число пересечений ветвей. Возникает вопрос, можно ли данную схему начертить так, чтобы она не имела точек пересечения кроме узлов? Если нельзя, то как расположить на схеме ее узлы, чтобы иметь минимальное число точек пересечения ветвей. Этот вопрос связан с планарностью графа, соответствующего схеме. Центральной теоремой о планарности графа является теорема Понтрягина-Куратовского: граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к С5 или G33. Здесь через G5 обозначен полный пятивершинный граф, а через G33 — шестивершинный. Оба графа G5 и G33 нельзя вычертить на плоскости так, чтобы ветви не пересекались в точках, отличных от них вершин, т. е. они являются непланарными. Теорема Понтрягина-Куратовского позволяет выявить, является ли данный граф планарным, но не дает способа построения плоского изображения схемы. Предложен алгоритм для вычерчивания плоского изображения схемы. Если граф схемы является непланарным, то алгоритм позволяет вычертить схему с минимальным числом пересечений ветвей.

Автоматизация чертежно-конструктореких работ [34, 41, 44, 54, 55]. Одноименный курс, разработанный автором, включен в учебный план специальности 1702 и проводятся занятия (18 часов лекций и 36 часов лабораторно-практических занятий) с 1984-85 учебного года. «Автоматизация чертежно-конструкторских работ (АЧКР)» является естественным продолжением курсов «Инженерная графика» и «Информатика и программирование». В нем излагаются вопросы подготовки и ввода в компьютер данных, содержащихся на чертежах, а также вывода геометрической информации на графический дисплей или графопостроитель. Особое внимание уделяется машинной графике (МГ) — основной подсистеме САПР. Интерактивная МГ позволяет улучшить качество, сократить сроки и стоимость проектирования технических устройств. Проектирование (конструирование)

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

Учебное пособие АЧКР ознакомит читателей с понятиями: САПР, машинная (компьютерная) графика, графический дисплей, световое перо, графопостроитель, АРМ и т. д. В нем имеются сведения о технических средствах МГ и программных средствах САПР. Из программных средств отмечены графические расширения алгоритмических языков высокого уровня: СМОГ, ПАФ-КФ, ГРАФОР. Более подробно рассматривается ГРАФОР, представляющий собой библиотеку из более четырехсот подпрограмм. Затрагиваются арифметические основы вычислительной техники и вопросы кодирования графической информации.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

2. Методика решения позиционных и метрических задач многомерного пространства путем применения предложенных в работе преобразований графо-геометрических моделей гиперплоскостей, т-плоскостей, прямых и точек.

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

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

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

5. Введены в рассмотрение графы Даламбера, возможных перемещений и Даламбера-Лагранжа. Указанные графы служат графо-геометрическими моделями принципа Даламбера, метода возможных перемещений и уравнения Даламбера-Лагранжа. Предложена методика составления таких графов.

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

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

8. На основе геометрического анализа графов электротехнических объектов установлена минимальная размерность моделирующего пространства: электрическая цепь, состоящая из п элементов, моделируется «-мерным пространством и добавление нового элемента увеличивает размерность моделирующего пространства на единицу. Электрическая цепь в установившемся режиме соответствует точке, а изменение входного сигнала вызывает перемещение этой точки по некоторой линии в многомерном пространстве.

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

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

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

11. Исследованы различные обобщения ПШ: многомерное обобщение, минимальные деревья, ПШ на поверхности, КД, связывающее компланарное множество плоских фигур. Получены практические алгоритмы определения связывающих КД для каждого перечисленного выше обобщения ПШ.

12. Сформулирована более общая проблема об оптимальных связывающих деревьях, частными случаями которой являются КС, ПШ, задачи Вебера и коммивояжера.

13. Разработан универсальный итерационный алгоритм построения КД в многомерном пространстве, использующий операции «введения Штейнера» и «штейнализация», обладающий достаточно быстрой сходимостью и обеспечивающий наперед заданную точность решения задач.

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

15. Изучена геометрия пространства с цилиндрическими расстояниями, частным случаем которого является плоскость с полярной метрикой. Установлено, что на такой плоскости существует четыре вида «отрезков», четыре вида «окружностей» и т. д., а в пространстве с цилиндрическими расстояниями КД «растет» только в трех направлениях.

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

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

17.Разработанные методики и алгоритмы переданы в НИИ, ПИ и предприятий для практического применения, а также внедрены в учебный процесс КазНТУ и некоторых других вузов РК.

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

ОСНОВНЫЕ РАБОТЫ, ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Изображение элементов л-мерного пространства методом графов // Изв. АН Каз ССР. Сер. физико-математическая. — Алма-Ата, 1969. № 3, — С. 42 — 48.

2. Построение кратчайшей линии, связывающей л точек в двумерном и трехмерном пространствах Г. Минковского // Материалы научно-технической конференции МАИ. — М: МАИ, 1970. — С. 6 — 7.

3 Оптимальное решение одной многоэкстремальной задачи II Вестник АН Каз ССР. — Алма-Ата, 1971. № 1. — С. 66 — 68.

4. Отображения гиперплоскостей с помощью графов и их приложения к задачам теоретической механики (в соавторстве) // Математика и механика. Вып. VII. часть I. — Алма-Ата, 1972. — С. 153 — 158.

5. Графическое решение одной экстремальной задачи II Вопросы математики и механики. — Алма-Ата: КазГУ, 1973. — С. 25 — 31.

6. К вопросу построения связывающего дерева с расстояниями первого порядка // Вопросы математики и механики. — Алма-Ата: КазГУ, 1973. — С. 32 — 40.

7. Приложения направленных графов к задачам статики (в соавторстве) // Вопросы математики и механики. — Алма-Ата: КазГУ, 1973. —С. 114— 120.

8. Приложения сигнальных графов к задачам динамики (в соавторстве) // Вопросы математики и механики. — Алма-Ата: КазГУ, 1973. С. 121 — 130.

9. Определение оптимальной конфигурации оросительной, сети методом кратчайших соединений компланарного множества равномерно расположенных точек (в соавторстве) II Проектирование строительных гидротехнических сооружений на оросительных системах. — Ташкент: Труды ТИИ и МСХ. Вып. 62, 1974. — С. 75 — 79.

10. Графический алгоритм обобщенной проблемы Я. Штейнера // Прикладная геометрия и инженерная графика. Вып. I. — Алма-Ата: КазПТИ, 1974. — С. 13 — 19.

11. Моделирование с помощью сигнальных графов многомерного евклидова пространства // Прикладная геометрия и инженерная графика. Вып. 1. — Алма-Ата: КазПТИ, 1974. — С. 13 — 19.

12. Сигнальные графы как модели многомерного линейного пространства // Материалы зональной научно-методической конференции по прикладной геометрии и инженерной графике. — Омск: ОмПТИ, 1975. — С. 166 — 167.

13. Геометрический смысл графов электрических целей // Электротехника. Вып. 2. — Алма-Ата: КазПТИ, 1975. — С. 16 — 22.

14. Графический алгоритм кратчайшего соединения множества точек в цилиндрических координатах II Технические науки. Вып. 15. — Алма-Ата: КазПТИ, 1975. — С. 136 — 141.

15. Моделирование с помощью графов задач теоретической механики // Прикладная геометрия и инженерная графика. Вып. 2. — Алма-Ата: КазПТИ, 1976. — С. 34 — 37.

16.0 кратчайших связывающих деревьях в пространстве с расстояниями первого порядка // Прикладная геометрия и инженерная графика. Вып. 2. —Алма-Ата: КазПТИ, 1976. — С. 45 — 52.

17.0 кратчайших связывающих деревьях // Технология машиностроения и автоматизация. Вып. 6. — Алма-Ата: КазПТИ,

1977. — С. 78 — 79.

18. Геометрия плоскости с полярной метрикой // Прикладная геометрия и инженерная графика. Вып. 3. — Алма-Ата: КазПТИ,

1978, —С. 10 — 15.

19.0 кратчайших соединениях компланарных фигур // Прикладная геометрия и инженерная графика. Вып. 3. — Алма-Ата: КазПТИ, 1978. — С. 82 — 86.

20 Об одном геометрическом алгоритме связывающих деревьев II Материалы всесоюзной конференции по САПР и инженерной графике. — Орел: НТО Машпром, 1978. — С. 45 — 48.

21.0 проблеме связывающих деревьев // Прикладная геометрия и инженерная графика. Вып. 27. — Киев: Будаелышк, 1979. - С. 50 — 51.

22. Задачник-минимум по инженерной графике. Часть 1. Начертательная геометрия. — Алма-Ата: НМК МВиССО Каз ССР, 1979. 1,5 п. л.

23.Сызу (пособие для поступающих в вузы на казахском языке).

— Алма-Ата: КазПТИ, 1979. 3 п. л.

24. Начертательная геометрия: Учеб. пособие. — Алма-Ата: КазПТИ, 1979. 5 п. л.

25. Конструирование каустической поверхности // Начертательная геометрия и черчение. — Алма-Ата: КазПТИ, 1981. — С. 16-19.

26. Задачник-минимум по инженерной графике. Часть 2. Черчение (в соавторстве). — Алма-Ата: МВиССО КазССР, 1981. 1,3 п. л.

27. Подсчет числа деревьев, связывающих п точек пространства (в соавторстве) // Тезисы докладов и сообщений на XVI научной конференции. — Алма-Ата: КазПТИ, 1982. — С. 15 — 16.

28. Временные рекомендации по определению схемы трассирования водопроводных сетей (в соавторстве). — Алма-Ата: Минводхоз КазССР, 1983. 1 п. л.

29. Содержание и актуальные вопросы преподавания инженерной графики // Роль инженерной графики и машинного проектирования в подготовке специалистов для народного хозяйства. — Ленинград: ЛПИ, 1984, — С. 14 — 15.

30. Некоторые обобщения проблемы Я. Штейнера // Начертательная геометрия и черчение. — Алма-Ата: КазПТИ, 1985.

— С. 5—11.

31. Составление дифференциальных уравнений динамической системы с помощью теории графов (в соавторстве) II Начертательная геометрия и черчение. —Алма-Ата: КазПТИ, 1985. — С. 20 — 25.

32. Проблемное обучение и НИРС по инженерной графике // Сборник научно-методических статей по начертательной геометрии и инженерной графике. Вып. II. — М.: Высшая школа. — С. 38 — 41.

33. Инженерная графика для студентов геологоразведочного факультета (в соавторстве). —-Алма-Ата: КазПТИ, 1985. 3 п. л.

34. Проблемы использования вычислительной техники при преподавании начертательной геометрии, черчения и инженерной графики (в соавторстве) // Использование вычислительной техники при подготовке инженерных кадров. — Караганда: КарПТИ, 1986. — С. 67 — 69.

35. Инженерно-геологическая графика (в соавторстве). —- Алма-Ата. КазПТИ, 1986. 4,2 п. л.

36.Сызу: Учебное пособие. — Алматы: Мектеп, 1986. 7 п. л.

37.0 графическом моделировании инженерных сетей // Начертательная геометрия и машинная графика в практике решения инженерных задач. — Омск: ОмПТИ, 1986. — С. 20 — 22.

38. Выполнение эпюр № 3 по начертательной геометрии (методические указания к ОГР). — Алма-Ата: КазПТИ, 1986. 1.5 н.л.

39.Сызба геометрия: Учебник по начертательной геометрии. — Алматы: Мектеп, 1987. 10 п. л.

40. Геометрическое моделирование в инженерной графике // Пути совершенствования инженерно-графических курсов. — Орджоникидзе: СКГМИ, 1988. — С. 4 — 5.

41. Автоматизация чертежно-конструкторских работ (в соавторстве). — Алма-Ата. КазПТИ, 1988. 3 п. л.

42. Аналоги коники в пространстве с расстояниями первого порядка // Вопросы преобразования и применения ЭВМ в начертательной геометрии. — Алма-Ата: КазПТИ, 1988. — С. 17 — 27.

43. Геометрические построения и канонические проекции (в соавторстве). — Алма-Ата: КазПТИ, 1987. 2 п.л.

44. Разработка программ на ГРАФОРЕ для выполнения чертежей плоских фигур. — Алма-Ата: КазПТИ, 1989. 2 п.л.

45.Моделирование с помощью теории графов в прикладной геометрии // Геометрическое моделирование инженерных объектов и технологических процессов. — Омск: ОмПТИ, 1989. — С. 24 — 28.

46. Вопросы специализации в курсах начертательной геометрии и инженерной графики // Компьютеризация и специализация обучения по графическим дисциплинам. — Новочеркаск: НПИ, 1990. — С. 27 — 28.

47. Краткий русско-казахский словарь терминов начертательной геометрии и черчения. — Алма-Ата: КазПТИ, 1990. 2 п. л.

48.Сызба геометрия есептершщ минимум!. — Алматы: КазПТИ, 1990. 2 п. л.

49.Сызба геометриядан орындалган графикалык, жу мы стар (в соавторстве). — Алматы: КазПТИ, 1990. 5 п. л.

50. Условные графические обозначения и схемные изображения в курсе инженерной графики // Проблемы методологии и методики преподавания дисциплин: прикладная механика и инженерная графика. — Ленинград: ЛЭТИ, 1990. — С. 69 — 70.

51.Сызу, 2-бел1м. Черчение, Ч. 2: — Учеб. пособие для средних учебных заведений. — Алматы: Рауан, 1990, 8 п. л.

52. Структура, содержание и методика преподавания начертательной геометрии в Казахском политехническом институте // Десятый научно-методический семинар по инженерной и машинной графике. - Полтава, ПИСИ, 1991. - С. 23 — 24.

53. Сызыкдык, сызба геометрияньщ непздерк — Алматы: КазПТИ, 1991.3 п. л.

54. Элементы компьютерной геометрии в курсе инженерной графики // Компьютерная геометрия и графика в инженерном образовании. Материалы всесоюзной конференции. — Нижний Новогород: НПИ, 1991. — С. 55.

55.Построение сопряжений с помощью ЭВМ // Преобразование и конструирование кривых и поверхностей. — Алматы: КазПТИ, 1992. _С. 42 — 49.

56. Салу есептерш шешудеп параметрлж эте И Информатика, физика, математика. — Алматы: 1993, № 3. — С. 10 — 16.

57. Преподавание инженерной графики во втузах Республики Казахстан // Проблемы графической подготовки инженера. — ¿Минск: БГПТА, 1992. — С. 48 — 49.

58. Конструкторлык кужаттардьщ б1рьщтай жуйесшщ мемлекеток стандартары (в соавторстве). — Алматы: КазАШИ, 1993. 3 п. л.

59. Пути активизации деятельности студентов при изучении графических дисциплин // Актуальные методы обучения... — Бишкек: КирТУ, 1992. — С. 92 — 95.

60. Курсовая работа по инженерной графике (в соавторстве). — Алматы: КазПТИ, 1993. 2 п. л.

61.Сигнальные графы как геометрические модели многомерных объектов (в соавторстве) // Актуальные вопросы современной науки и техники. — Алматы: КазНТУ, 1994. — С. 84 — 87.

62.Технология определения кратчайших связывающих линий средствами интерактивной машинной графики // Актуальные вопросы современной науки и техники. — Алматы: КазНТУ, 1994. — С. 87 — 90.

63. Краткий конспект лекций по начертательной геометрии. — Алматы: КазНТУ, 1994. 6 п. л.

64. Сызба геометрия есептерк Учебное пособие по начертательной геометрии (в соавторстве). — Алматы: Бшм, 1995. 15 п. л.

Есмуханов Жанузак, Мухптулы. Автоматтандырылган хобалау хуйелершдеп графо-геометрпалык, модельдеу. — Алматы: К,аз¥ТУ, 1995, 84 б.

Рылыми баяндама туршде жазылган докторлык, диссертацияда графтар теориясыньщ кемепмен квпелшсмд! кендспктердщ, механикалык, к,урылымдар мен электр т^збектерМц автоматтандырылган жобалау жуйелершде пайдаланылатын геометриялык, модельдерш куру тесшдер1 усынылган. Кепвлшемд! кещстк асажазыктьщтардьщ узд к аз жиыны ретшде к,арыстырылып, оныц баск,а элементтер! асажазык,тыктыц графтары арк,ылы модельденген. Механикалык, к,урылымдар мен электр тобсктершщ графтары кепелшемд! графтар екеш дэлелденген. Сондьщтан теориялык, механика, электротехника жэне баскд техникалык, гылымдар есептерш графо-геометриялык, модельдеу арк,ылы кепелшемд! кещстжтеп позициялык, жане метрикалык; есептерге келт1руге болатыны керсетшген.

Жазык.тык,га бершген нуктелер жиынын езара жалгастыратын туйык,талмаган кыск^а сызыкты аньщтау эд1стемеа табылган. Рылыми едебиегге Штейнердщ проблемасы деп аталатын бул есеп жеке жагдайы болатын б1рнеше проблемалар зерттелген. Эр турл1 елшемдеп метрикалык, кещспк ушш б1ршш1 регп, полярлык, жене цилиндрлж кдшык,тыцтар ескершш, керсетшген нуктелер мен фигураларды косатын тшмдо сызьщтарды салу алгоритмдер! тужырымдалган.

Диссертацияда алынган нэтижелер сызба геометрия, инженерлж графика жене сызу — конструкторлык, жумыстарды автоматтандыру пвндер1 бойынша автор жазган окулык,тар мен ок,у к,уралдарына енпзшген. Осындай бугшп кушпц талантарьша сай окдлудыц акдтраттандырылган технологиясьш жузеге асыратын ецбектер! к,азак, жэне орыс тшдершде жарык, керген.

Сурет 27. Библиогр.: 64 атау

Esmukhanov Zhanuzak Mukhiiovich.

The graph-geometrical modelling in CAD of technical systems. — Almaty: KazNTU, 1995 — 84 p.

In doctoral thesis which was written in the form of scientific report on the border of specialities «05. 13. 12 — CAD» and «05. 01. 01 — Applied geometry and engineering graphics», geometrical models of multidimensional space, mechanical systems and electric chains to use in CAD with the help of graph theory had been elaborated. Multidimensional space is considered as continuous multitude of hyperplanes and the models of all other elements are defined by means of synthesis of hyperplane models. It was found that the graphs of mechanical systems and electrical chains are multidimensional spaces. Therefore the solution of problems of theoretical mechanics, electrical engineering and other technical sciences can be brought to the solution of position and metrical problems in multidimensional space by means of graph-geometrical modelling.

On the basis of graph-geometrical modelling the method of defining the «shortest trees» connecting the fixed points of the plane have been obtained. AH kinds of generalizations of this problem have been investigated which in scientific literature is called the problem of Shteiner. The geometry of metric space with the distances of first rate and polar metrics have been investigated. Algorithims for optimal connecton of the given multitude of line points in space with different metrics and size have been given.

The received results are used by the author when writing manuals in descriptive geometry, engineering graphics and automatization of drawing-design works which meet the requirements of information in education and are published in Russian and Kazakh.

11.27, lib.64

Подписано в печать Тираж 120 экз. Формат 60x84 1/16. Бумага типографская № 1. Объем 5 п. л. Заказ №

Издание Казахского национального технического университета, Алматы, ул. акад. Сатпаева, 22