Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 5 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

ВВЕДЕНИЕ
В последние годы особую важность приобрели те разделы математики,
которые имеют отношение к развитию цифровых устройств, цифровой связи и
цифровых вычислительных машин. Базой для преподавания этих дисциплин
наряду с классическими методами анализа непрерывных физических моделей
стали алгебраические, логические и комбинаторные методы исследования
различных моделей дискретной математики.
Значительно возросла популярность теории графов - ветви дискретной
математики. Графы встречаются во многих областях под разными названиями:
“структуры” в гражданском строительстве, ”сети” - в электронике, ”социограммы” -
в социологии и экономике, “молекулярные структуры” - в химии, ”дорожные карты”,
электрические или газовые распределительные сети и т.д.
Родившись при решении головоломок и игр, таких, например, как задача о
кенигсбергских мостах и игра Гамильтона, теория графов стала мощным
средством исследования и решения многих задач, возникающих при изучении
больших и сложных систем. Для специалистов по вычислительной технике,
информационным системам и системам цифровой связи теория графов - это
удобный язык выражения понятий из этой области; многие результаты теории
графов имеют непосредственную связь с задачами, с которыми им приходится
сталкиваться. Графическая интерпретация различных моделей графов дана на
рис. 1. Так в виде ориентированных графов можно представить любую
логическую или функционально - логическую схему ( рис. 1а ). На таких графовых
моделях можно, например, оценить быстродействие схемы. Блок - схема
алгоритма может быть представлена вероятностным графом ( рис. 1б ), который
позволяет оценить временные характеристики алгоритма, затраты процессорного
времени, трудоемкость и другие. Графом типа “дерево” можно отобразить
практически любую структуру организации или предприятия ( рис. 1в ).
Широкое применение теория графов получила при исследовании так
называемой проблемы оптимизации, возникающей при конструировании
больших систем как технических, так и программных, например, таких как 
                                      ВВЕДЕНИЕ


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

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

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

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

Страницы