- Главная
- Математика
- Задачи, приводящие к теории графов. Основные понятия и определения. (Лекция 13)
Содержание
- 2. Историческая записка Леонард Эйлер (1707-1783)- швейцарец по происхождению. Приехал в Санкт-Петербург в 1727 году. Не было
- 3. Приложения теории графов - Задача о кратчайшей цепи составление расписания движения транспортных средств, размещение пунктов скорой
- 4. Задачи, приводящие к теории графов Попробуйте нарисовать закрытый конверт одним росчерком, т.е., не отрывая карандаша от
- 5. Задача о Кёнигсбергских мостах Впервые над задачей описанного выше типа задумался Леонард Эйлер после посещения города
- 6. Задача о трех домах и трех колодцах Всегда ли можно изобразить граф на плоскости так, чтобы
- 16. Дополнительные графы. Самодополнительные графы
- 21. Скачать презентацию
Слайд 2
Историческая записка
Леонард Эйлер (1707-1783)- швейцарец по происхождению. Приехал в Санкт-Петербург в
Историческая записка
Леонард Эйлер (1707-1783)- швейцарец по происхождению. Приехал в Санкт-Петербург в
1727 году. Не было такой области математики XVIII века, в которой Эйлер не достиг бы заметных результатов. Например, решая головоломки и развлекательные задачи, Эйлер заложил основы теории графов, ныне широко используемой во многих приложениях математики.
Напряженная работа повлияла на зрение ученого, в 1766 году он ослеп, но и после этого продолжал работу, диктуя ученикам свои статьи.
Эйлер умер в 76 лет и был похоронен на Смоленском кладбище Санкт-Петербурга. В 1957 году его прах был перенесен в Александро-Невскую лавру.
Напряженная работа повлияла на зрение ученого, в 1766 году он ослеп, но и после этого продолжал работу, диктуя ученикам свои статьи.
Эйлер умер в 76 лет и был похоронен на Смоленском кладбище Санкт-Петербурга. В 1957 году его прах был перенесен в Александро-Невскую лавру.
Слайд 3
Приложения теории графов
- Задача о кратчайшей цепи
составление расписания движения транспортных средств,
размещение
Приложения теории графов
- Задача о кратчайшей цепи
составление расписания движения транспортных средств,
размещение
пунктов скорой помощи,
размещение телефонных станций.
- Задача о максимальном потоке
анализ пропускной способности коммуникационной сети
организация движения в динамической сети
оптимальный подбор интенсивностей выполнения работ
задача о распределении работ
- Задача об упаковках и покрытиях
оптимизация структуры ПЗУ
размещение диспетчерских пунктов городской транспортной сети
- Раскраска в графах
распределение памяти в ЭВМ
проектирование сетей телевизионного вещания
- Связность графов и сетей
проектирование кратчайшей коммуникационной сети
синтез структурно-надежной сети циркуляционной связи
анализ надежности стохастических сетей связи
- Изоморфизм графов и сетей
структурный синтез линейных избирательных цепей
автоматизация контроля при проектировании БИС
- Изоморфное вхождение и пересечение графов
локализация неисправности с помощью алгоритмов поиска МИПГ
покрытие схемы заданным набором типовых подсхем
- Автоморфизм графов
конструктивное перечисление структурных изомеров для
производных органических соединений
синтез тестов цифровых устройств
размещение телефонных станций.
- Задача о максимальном потоке
анализ пропускной способности коммуникационной сети
организация движения в динамической сети
оптимальный подбор интенсивностей выполнения работ
задача о распределении работ
- Задача об упаковках и покрытиях
оптимизация структуры ПЗУ
размещение диспетчерских пунктов городской транспортной сети
- Раскраска в графах
распределение памяти в ЭВМ
проектирование сетей телевизионного вещания
- Связность графов и сетей
проектирование кратчайшей коммуникационной сети
синтез структурно-надежной сети циркуляционной связи
анализ надежности стохастических сетей связи
- Изоморфизм графов и сетей
структурный синтез линейных избирательных цепей
автоматизация контроля при проектировании БИС
- Изоморфное вхождение и пересечение графов
локализация неисправности с помощью алгоритмов поиска МИПГ
покрытие схемы заданным набором типовых подсхем
- Автоморфизм графов
конструктивное перечисление структурных изомеров для
производных органических соединений
синтез тестов цифровых устройств
Слайд 4
Задачи, приводящие к теории графов
Попробуйте нарисовать закрытый конверт одним росчерком, т.е.,
Задачи, приводящие к теории графов
Попробуйте нарисовать закрытый конверт одним росчерком, т.е.,
не отрывая карандаша от бумаги и не проводя дважды один и тот же отрезок.
А если конверт распечатать?
А если конверт распечатать?
Слайд 5
Задача о Кёнигсбергских мостах
Впервые над задачей описанного выше типа задумался Леонард
Задача о Кёнигсбергских мостах
Впервые над задачей описанного выше типа задумался Леонард
Эйлер после посещения города Кенигсберга (ныне Калининград).
В городе было семь мостов через реку Прегель.
Гостям города предлагали задачу: пройти по всем мостам ровно один раз. Никому из гостей не удавалось справиться с задачей.
Эйлер отметил на карте города по одной точке на каждом берегу реки и на каждом острове.
Затем он соединил эти точки в соответствии с расположением мостов. Задача обхода мостов свелась к задаче изображения одним росчерком следующей картинки
В городе было семь мостов через реку Прегель.
Гостям города предлагали задачу: пройти по всем мостам ровно один раз. Никому из гостей не удавалось справиться с задачей.
Эйлер отметил на карте города по одной точке на каждом берегу реки и на каждом острове.
Затем он соединил эти точки в соответствии с расположением мостов. Задача обхода мостов свелась к задаче изображения одним росчерком следующей картинки
B
A
C
D
Слайд 6
Задача о трех домах и трех колодцах
Всегда ли можно изобразить граф
Задача о трех домах и трех колодцах
Всегда ли можно изобразить граф
на плоскости так, чтобы его ребра не пересекались? Впервые этот вопрос возник при решении старой головоломки. Вот как ее описывает Льюис Кэрролл.
В трех домиках жили три человека, неподалеку находилось три колодца: один с водой, другой с маслом, а третий с повидлом. Однако хозяева домиков перессорились и решили провести тропинки от своих домиков к колодцам так, чтобы эти тропинки не пересекались. Первоначальный вариант по этой причине их не устраивал.
В трех домиках жили три человека, неподалеку находилось три колодца: один с водой, другой с маслом, а третий с повидлом. Однако хозяева домиков перессорились и решили провести тропинки от своих домиков к колодцам так, чтобы эти тропинки не пересекались. Первоначальный вариант по этой причине их не устраивал.
Слайд 7
Слайд 8
Слайд 9
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14
Слайд 15
Слайд 16
Дополнительные графы.
Самодополнительные графы
Дополнительные графы.
Самодополнительные графы
Слайд 17
Слайд 18
Слайд 19
Следующая -
Программирование Lego-роботов