pr-4-grafy-252732fa200666


Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:

Графы. Деревья. Примеры графовМодель управления предприятием (школой, театральным коллективом и т. д.) очень удобно представлять в виде графа.Система «Школьный урок», состоящая из следующих элементов: ученик, учитель, учебник, тетрадь, классный журнал, классная доска, мел, парта, учительский стол, классная комната. Круговорот воды в природе. Повторение Граф – это множество точек, некоторые из которых соединены между собой линиями (отрезками, дугами). Служит для наглядного представления связей между объектамиПутем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.Простой путь – путь, в котором никакое ребро не встречается дважды.Циклом называется путь, в котором совпадают начало с концом.Висячей вершиной называется вершина, из которой выходит ребро. Граф, в котором построены все возможные ребра, называется полным графом. Деревом называется любой связный граф, не имеющий циклов . ПовторениеЗадача. В Тридевятом царстве лишь один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в Дальний (возможно с пересадкой).Решение: 1. Построим граф, в качестве вершин графа – города государства. 2. Необходимо доказать, что столица и город Дальний находятся в одном компоненте связности графа. 3. Предположим противное: граф не связный, город Д. и С. находятся в разных компонентах связности. 4. Рассмотрим компоненту связности, содержащую столицу. Тогда в этой компоненте связности из одной вершины (столицы) выходит 21 ребро, а из остальных – по 20 ребер. Таким образом в этом графе (компоненте связности) ровно одна нечетная вершина. Противоречие.

ПовторениеУпр.1 В графе 4 вершин, каждая из которых имеет индекс 3. Сколько у него ребер? Нарисуйте такой граф.Упр.2 В графе 5 вершин, каждая из которых имеет индекс 4. Сколько у него ребер? Нарисуйте такой граф.Упр.3 Может ли граф иметь пять вершин, в каждой из которых сходится три ребра? ПовторениеЗадачи, приводящие к графамЗадача 1. Лист бумаги Плюшкин (Н. В. Гоголь «Мертвые души») разрезает на три части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листков он вновь разрезает на три более мелкие части и так далее. Сколько Плюшкин получает листиков бумаги,если разрезает k листов?Решение. Будем считать листы бумаги вершинами графа. При разрезании одного листка на три части число листков увеличивается на два (появляются три новых вместо одного). Если же было разрезано k листов, то образовалось1+2k листов.Задача 2. Утверждают, что в одной компании из пяти человек каждый знаком с двумя другими. Возможна ли такая компания?Решение. Каждого из этой компании будем считать вершиной графа. Двое знакомых соединим ребром. Из рассматриваемой компании нельзя выделить ни «четырехугольник», ни «треугольник», поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию. То есть схема знакомства единственная. (Всякую схему, напоминающую многоугольник, принято называть циклом. Древние греки «цикл» называли «колесом».)Задача 3. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.Решение. Переведем условие задачи на язык графов. Каждому из шахматистов поставим в соответствие вершину графа, соединим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим партию друг с другом. Получим граф с девятью вершинами. Степени его вершин равняются числу партий, сыгравших с соответствующими игроками. Покажем, что во всяком графе с девятью вершинами всегда найдутся хотя бы две вершины одинаковой степени. Каждая вершина графа с девятью вершинами может иметь степень, равную0,1,2,...7,8. Предположим, что существует граф , все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0,1,2,3,4,5,6,7,8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершинаA степени0, то в нем не найдется вершина B со степенью 8,так …



ЗАКОНОМЕРНОСТИ СТЕПЕНЬ ВЕРШИНЫ1) Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.2) Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа.Число нечетных вершин любого графа четно.

ИЗОМОРФИЗМ ИЗОМОРФИЗМ Изоморфны ли графы в парах Решение под буквой А Изоморфны ли графы в парах ЦИКЛ Циклом называется замкнутый путь, не проходящий дважды через одну и ту же вершинуНа рис. а: 1-2-3-4-1 и 5-6-7-5На рис. б: 1-5-6-7-1, 1-2-3-4-5-1, 1-2-3-4-5-6-7-1 Задача 1 В королевстве 16 городов. Король хочет построить такую систему дорог, чтобы из каждого города можно было попасть в каждый, минуя не более одного промежуточного города, и чтобы из каждого города выходило не более 5 дорог.  Докажите, что это возможно.  Разновидности графовСвязныйДеревоПлоский ДЕРЕВЬЯ Деревом называется связный граф, не имеющий циклов. ДЕРЕВЬЯ Дерево – это граф, в котором любые две вершины соединены простым путем (простой путь – путь, в котором никакое ребро не встречается дважды). Вершина, из которой выходит ровно одно ребро, называется висячей. Лемма. В дереве есть вершина, из которой выходит ровно одно ребро. ДЕРЕВЬЯ Задача 2. В стране Древляндия 101 город, и некоторые из них соендинены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?Решение: 1. Граф Древляндии – дерево с висячей вершиной.2. Удалим эту вершину вместе с ее ребром. Осталось дерево.3. Удаляем очередную висячую вершину вместе с ее ребром.4. На 100 шаге получили граф, состоящий из одной вершины.5. Вывод: удалено 100 ребер – сто дорог. ДЕРЕВЬЯ Теорема. В дереве число вершин на единицу больше числа ребер. Верно и обратное утверждение. ДЕРЕВЬЯ Задача 3. Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски? Решение. 1. Волейбольная сетка – граф, вершины – узлы сетки, ребра – веревочки.2. Искомый граф – дерево.ДЕРЕВЬЯ Задача 3. Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски? Решение. 3. Посчитаем число ребер дерева:51*601=30651 – количество вершин30651-1=30650 – количество ребер4. Начальное количество ребер: 601*50+600*51=606505. Ответ: 60650-30650=30000ДЕРЕВЬЯ Задача 3. Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски? ДЕРЕВЬЯ Задача 4. В некоторой стране 30 городов, при чем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый? Задача 5. Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным. Задача 6. В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно , с пересадками). Докажите, что можно побывать в каждом городе, совершив не более 198 перелетов. ПЛОСКИЙ ГРАФ Граф, который можно нарисовать так, чтобы его ребра не пересекались (нигде, кроме вершины), называется плоским. А) В) С) ПЛОСКИЙ ГРАФ Заметим, что правильно нарисованный плоский граф разбивает плоскость на куски.Обозначим:К – число таких кусков плоскости (учитывая внешний кусок плоскости)В – число вершин графаР – число ребер графаПример: В=4, Р=6, К=4

Приложенные файлы

  • pptx 18223337
    Размер файла: 357 kB Загрузок: 0

Добавить комментарий