🗊Презентация Задачи, приводящие к теории графов. Основные понятия и определения. (Лекция 13)

Задачи, приводящие к теории графов. Основные понятия и определения.

Историческая записка Леонард Эйлер (1707-1783)- швейцарец по происхождению. Приехал в Санкт-Петербург в 1727 году. Не было такой области математики XVIII века, в которой Эйлер не достиг бы заметных результатов. Например, решая головоломки и развлекательные задачи, Эйлер заложил основы теории графов, ныне широко используемой во многих приложениях математики. Напряженная работа повлияла на зрение ученого, в 1766 году он ослеп, но и после этого продолжал работу, диктуя ученикам свои статьи. Эйлер умер в 76 лет и был похоронен на Смоленском кладбище Санкт-Петербурга. В 1957 году его прах был перенесен в Александро-Невскую лавру.

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

Задачи, приводящие к теории графов Попробуйте нарисовать закрытый конверт одним росчерком, т.е., не отрывая карандаша от бумаги и не проводя дважды один и тот же отрезок. А если конверт распечатать?

Задача о Кёнигсбергских мостах Впервые над задачей описанного выше типа задумался Леонард Эйлер после посещения города Кенигсберга (ныне Калининград). В городе было семь мостов через реку Прегель. Гостям города предлагали задачу: пройти по всем мостам ровно один раз. Никому из гостей не удавалось справиться с задачей. Эйлер отметил на карте города по одной точке на каждом берегу реки и на каждом острове. Затем он соединил эти точки в соответствии с расположением мостов. Задача обхода мостов свелась к задаче изображения одним росчерком следующей картинки

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

Дополнительные графы. Самодополнительные графы