Что такое теория чисел и как записать это ?

Основные понятия теории графов Теория графов — один из фундаментальных разделов дискретной математики. Све- дения из этого раздела традиционно включались в курсы кибернетики, а затем и информа- тики, поскольку графы оказались очень продуктивным средством информационного (ма- тематического) моделирования структур систем и процессов, представления задач инфор- мационного характера. Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, информационных систем, химических и генетических струк- тур, электрических цепей и других систем сетевой структуры. Обычно теорию графов относят к топологии (потому что во многих случаях рас- сматриваются лишь топологические свойства графов), однако она пересекается со многи- ми разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Граф-модели применяются для эффективного использования ресурсов вычислительной системы (оптимизация использования памяти, регистров, уменьшение обменов между оперативной и внешней памятью и т.д.), организации больших массивов информации (графы данных для повышения эффективности информационного поиска), увеличения степени параллелизма программы, повышения эффективности работы микропроцессор- ных и многомашинных систем (распределение процессоров, обмен сообщениями между процессорами, синхронизация). Решение этих и подобных задач привело к появлению множества граф-моделей, связанных как с программами и структурными данными, так и с вычислительными системами. Основной объект теории графов — граф и его обобщения. Началом теории графов считается 1736 год, когда вышла в свет статья Л. Эйлера с его знамени- тыми рассуждениями о Кенигсбергских мостах. На рисунке 1 представлен схематический план цен- тральной части города Кенигсберг (ныне Калинин- град), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части су- ши, пройдя по каждому мосту один раз, и вернуть- ся в исходную точку. Задача о Кенигсбергских мостах была решена (показано, что решение не существу- ет) Эйлером в 1736 году. Затем около 100 лет эта статья оставалась единственной, а мето- ды теории графов невостребованными практикой. Интерес к графам появился только в середине XIX века благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. С тех пор сфера применений теории графов непрерывно расширялась и сегодня она представляет собой мощную формальную систему, имеющую необозримое множество областей практического применения. При проектировании компьютерных сетей, телевизионных линий, трубопроводов и строительстве дорог необходимо минимизировать затраты на прокладку коммуникаций. Прежде всего, целесообразно выбрать минимальный по длине маршрут прокладки комму- никаций. Например, необходимо соединить телефонным или оптоволоконным кабелем несколько зданий, расстояния между которыми различны. Возникает задача определения маршрута прокладки кабеля минимальной длины, но при этом к каждому зданию. Для решения таких задач часто используют теорию графов. Рисунок 1 – План центральной части го- рода Кенигсберг2 Граф и его виды Геометрическое представление графа — это схемы, состоящие из точек и соеди- няющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 2). Познакомимся с основными понятиями теории графов при решении несложной за- дачи. Задача: Александр, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожа- тий было сделано? Решение: Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени (см. рисунок 3 a), а производимому ру- копожатию — отрезок или часть кривой, соединяющая конкретные точки — имена (рису- нок 3 b). Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — рѐбрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными. Длины отрезков и расположение то- чек произвольны. Например, все три фигуры на рисунке 4 изображают один и тот же граф. Рассмотрим процесс соединения точек А, Б, В, Г, Д рѐбрами. 1. Ситуация, соответствующая моменту, когда рукопожатия ещѐ не совер- шались, представляет собой точечную схему, изображѐнную на рисунке 3 a). Та- кая схема, состоящая из «изолированных» вершин, называется нулевым графом.