Теория графов.
презентация к уроку по информатике и икт (9 класс)
Теория графов — раздел дискретной математики, изучающий свойства графов. Она применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электроника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. При этом обычно на графе решаются задачи о достижимости, задачи сетевого планирования, потоковая задача.
Интерес к проблемам теории графов был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса.
Изучение теории графов является актуальным, так как настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять – двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии. Вследствие этого развития предмет теории графов является уже обширным.
Основную проблему в применении теоретико-графовых методов составляет проблема терминологии, так как она далеко не устоялась.
Скачать:
| Вложение | Размер |
|---|---|
 teoriya_grafov_v_informatike.pptx | 440.13 КБ |
Предварительный просмотр:
Подписи к слайдам:
Содержание Введение Теория графов Классические задачи Графы в информатике Заключение
Введение
Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в управлении производством, бизнесе, при построении путей транспортировки и доставки, решении задач. Графы используют в связи с развитием теории вероятностей, математической логики и информационных технологий.
Теория графов
Граф – это некоторое конечное множество точек, называемых вершинами, и конечный набор линий, называемых ребрами, соединяющих некоторые пары точек. А В С D E
Понятия теории графов Степень вершины - число рёбер, выходящих из этой вершины. Граф называется взвешенным , если каждому ребру поставлено в соответствии некоторое число (вес). Ориентированным (орграфом) называется граф, у которого рёбрам присвоено направление. Плоский граф – граф , расположенный в одной плоскости, ребра которого не пересекаются. Полный граф – граф , в котором соединены все вершины всеми возможными способами.
Некоторые свойства графов Если все вершины графа чётные, то можно одним росчерком начертить граф. Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.
Некоторые свойства плоских графов Лемма1. Число рёбер в графе ровно в 2 раза меньше, чем сумма степеней вершин. Лемма2 . Сумма степеней вершин графа чётна. Лемма3 . Число нечётных вершин графа чётно. Лемма4 . Если полный граф имеет n вершин, то количество ребер будет равно
Классические задачи
«Жадные алгоритмы» Требуется проложить железную дорогу, соединяющую несколько городов. Для любой пары городов известна стоимость прокладки пути между ними. Требуется найти наиболее дешёвый вариант строительства. A B C D E A 1.5 1 2 2.5 B 1.5 1.2 3 0.8 C 1 1.2 1.1 09 D 2 3 1.1 2.7 E 2.5 0.8 0.9 2.7
«Жадные алгоритмы» A B C D E
Графы в информатике
Блок-схемы Задача: построить блок-схему попадания дротика в цель в игре « Дартс » Решение: Пусть Х 0 , Y 0 –центр поля R и R 1 – радиусы красного и черного полей X и Y – это координаты стрелы
Решение задач Необходимо указать таблицу, для которой выполняется условие: «Минимальная стоимость прокладки линии от клиента А до клиента B не больше 6 у.е .». A B C D E A 3 1 B 4 2 C 3 4 2 D 1 E 2 2 A B C D E A 3 1 1 B 4 C 3 2 D 1 4 E 1 2 A B C D E A 3 1 4 B 4 2 C 3 4 2 D 1 E 4 2 2 A B C D E A 1 B 4 1 C 4 4 2 D 1 4 E 1 2
Решение задач A B C D E A 3 1 B 4 2 C 3 4 2 D 1 E 2 2 A B C D E A 3 1 4 B 4 C 3 2 D 1 4 E 4 2 A B C D E A 3 1 4 B 4 2 C 3 4 2 D 1 E 4 2 2 A B C D E A 1 B 4 2 C 4 4 2 D 1 4 E 2 2 B E C A D 1 3 2 2 4 B E C A D 1 3 2 2 4 4 B E C A D 1 3 2 4 4 B E C A D 1 2 4 4 2
Решение задач B E C A D 1 3 2 2 4 B E C A D 1 3 2 2 4 4 B E C A D 1 3 2 4 4 B E C A D 1 2 4 4 2 A → C → B стоимость 7 A → C → E → B стоимость 7 A → C → B стоимость 7 A → E → C → B стоимость 10 A → C → B стоимость 7 A → E → B стоимость 6 A → D → C → B стоимость 9
Заключение
На языке теории графов формируются и решаются многие технические задачи, задачи из области экономики, социологии, менеджмента и многие другие. Графы используются для наглядного представления объектов и связи между ними. Но к теории графов также относится целый ряд проблем, не решенных на сегодняшний день.
По теме: методические разработки, презентации и конспекты
Презентация к уроку в 11 классе по теме "Введение в теорию графов"
Данная презентация содержит в себе и информационный материал по теме "Введение в теорию графов" и комплект слайдов с заданиями по теме. Решение на слайдах с заданиями вызывается посредством нажатия на...
Задачи Теории графов
Наряду с живым словом педагога важны различные средства обучения в образовательном процессе. Универсальным средством обучения и воспитания, которое одинаково ценно для учащихся разных возрастных групп...
Элементы теории графов. Способы обхода графов
Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Первая работа по теории графов, принадлежащая известному швейцарскому мат...
Презентация к развивающему занятию "Теория графов"
Данная презентация может быть использована на внеклассных занятиях по математике....
Теория графов: теория и задачи
Данная работа содержит теорию графов и некоторые задачи по данной теме, а так же разработку внеклассного занятия по теме:"Графы"...
Программа элективного курса для предпрофильной подготовки учащихся 9-классов “Элементы теории графов “.
Настоящая работа представляет собой программу элективного курса “ Элементы теории графов “ для предпрофильной подготовки учащихся 9 классов....