(5 оценок, среднее: 4,80 из 5)
Загрузка...
Учебная работа. Реферат: Графы
Городское образовательной учреждение – МОУ Гимназия №47
Екатеринбург, 2000
Введение
слово «граф» в арифметике значит картину, где нарисовано несколько точек, некие из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач), сетевые графики строительства, где верхушки – действия, означающие окончания работ на неком участке, а ребра, связывающие эти верхушки, — работы, которые может быть начать по совершении 1-го действия и нужно выполнить для совершения последующего.
Теория графов является частью как топологии, так и комбинаторики. То, что это топологическая теория, следует из независимости параметров графа от расположения вершин и вида соединяющих их линий. А удобство формулировок комбинаторных задач в определениях графов привела к тому, что теория графов стала одним из мощнейших аппаратов комбинаторики.
понятие о графах
Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» — пишу. Обычными графами являются схемы авиалиний, которые нередко вывешивается в аэропортах, схемы метро, а на географических картах – изображение стальных дорог (рис. 1). Избранные точки графа именуются его верхушками, а соединяющие их полосы – ребрами.
Употребляет графы и дворянство. На рисунке 2 приведена часть генеалогического дерева известного дворянского рода. тут его верхушки – члены этого рода, а связывающие их отрезки – дела родственности, ведущие от родителей к детям.
слово «дерево» в теории графов значит граф, в каком нет циклов, другими словами в каком недозволено из некой верхушки пройти по нескольким разным ребрам и возвратиться в ту же верхушку. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков меж родственниками.
Не тяжело осознать, что граф – дерево постоянно можно изобразить так, чтоб его ребра не пересекались. Этим же свойством владеют графы, образованные верхушками и ребрами выпуклых полиэдров. На рисунке 3 приведены графы, надлежащие 5 правильным полиэдрам. В графе соответственном тетраэдру, все четыре верхушки попарно соединены ребрами.
Разглядим граф с пятью верхушками, попарно соединенными друг с другом (рис. 4). Тут ребра графа пересекаются. Нереально его изобразить так, чтоб пересечений не было, как нереально выполнить намерения 3-х человек, обрисованных Льюсом Кэрроллом.
Они жили в 3-х домиках, недалеко от их находились три колодца: один с водой, иной с маслом, а 3-ий с повидлом, и прогуливались к ним по тропинкам, изображенным на рисунке 5. В один прекрасный момент эти люди перессорились и решили провести тропинки от собственных домов к колодцам так, чтоб эти тропинки не пересекались. На рисунке 6 изображена еще одна попытка проложить такие тропы.
Графы, изображенные на рисунках 4 и 5, как оказывается, играют решающую роль при определение для всякого графа – является ли он плоским, другими словами может ли он быть изображен на плоскости без пересечения его ребер. Польский математик Г. Куратовский и академик Л. С. Понтрягин независимо обосновали, что если граф не является плоским, то в нем «посиживает» хотя бы один из графов, изображенных на рисунках 4 и 5, другими словами «полный пятивершинник» либо граф «домики – колодцы».
Графами являются блок – схемы программ для ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач), сетевые графики строительства, где верхушки – действия, означающие окончания работ на неком участке, а ребра, связывающие эти верхушки, — работы, которые может быть начать по совершении 1-го действия и нужно выполнить для совершения последующего.
Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то таковой граф именуют направленным.
Стрелка от одой работы к иной на графе, изображенном на рис. 7, значит последовательность выполнения работ. недозволено начинать установка стенок, не окончив строить фундамент, чтоб приступить к отделке, необходимо иметь на этажах воду и т. д.
Около вершин графа указаны числа – длительность в деньках соответственной работы . Сейчас мы можем выяснить меньшую вероятную длительность строительства. Для этого из всех путей по графу в направлении стрелок необходимо избрать путь, у которого сумма чисел при верхушках большая. Он именуется критичным методом (на рис. 2 он выделен карим цветом). В нашем случае получаем 170 дней. А если уменьшить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критичный путь станет проходить не через эту верхушку, а через верхушки, надлежащие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться только на 10 дней.
На рис.8 изображена схема дорог меж селами М, А, Б, В, Г.
тут любые две верхушки соединены меж собой ребром. Таковой граф именуется полным. Числа на рисунке указывают расстояния меж селами по сиим дорогам. Пусть в селе М находится почта и почтальон должен развезти письма по остальным четырем селам. Существует много разных маршрутов поездки. Как из их избрать наикратчайший? Проще всего проанализировать все варианты. Создать это поможет новейший граф(понизу), на котором просто узреть вероятные маршруты. Верхушка М вверху – начало маршрутов. Из нее можно начать движение 4-мя разными методами: вА, в Б, в В, в Г. Опосля посещения 1-го из сел остается три способности продолжения маршрута, позже две, позже дорога в крайнее село и вновь в М. Всего 4 3 2 1 = 24 метода.
Расставим вдоль ребер графа числа, обозначающие расстояния меж селами, а в конце всякого маршрута напишем сумму этих расстояний по маршруту. Из приобретенных 24 чисел меньшими являются два числа по 28км, надлежащие маршрутам М-В-Б-А-Г-М и М-Г-А-Б-В-М. Это один и этот же путь, но пройденный в различных направлениях Заметим, что граф на рис. 8 тоже можно создать направленным, указав направление сверху вниз на любом из ребер, что соответствовало бы направлению движения почтальона. Подобные задачки нередко появляются при нахождении наилучших вариантов развозки продуктов по магазинам, стройматериалов по стройкам.
Графы нередко употребляют для решения логических заморочек, связанных с перебором вариантов. Для примера разглядим такую задачку. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и бросить в ведре 4 л, т. е. разлить воду поровну в ведро и огромную кастрюлю.
Ситуацию в любой момент можно обрисовать 3-мя числами, где А-количество л. воды в ведре, Б- в большенный кастрюле, В — в наименьшей. В исходный момент ситуация описывалась тройкой чисел ( 8, 0, 0), от нее мы можем перейти в одну из 2-ух ситуаций: ( 3, 5, 0),если наполним водой огромную кастрюлю, либо ( 5, 0, 3), если наполним наименьшую кастрюлю.
В итоге получаем два решения: одно в 7 ходов, другое в 8 ходов.
Схожим образом можно ставить граф хоть какой позиционной игры: шахмат, шашек, «крестиков – ноликов», где позиции станут верхушками, а направленные отрезки меж ними будут означать, что одним ходом можно перейти от одной позиции к иной, по направлению стрелки.
Но для шахмат и шашек таковой граф будит весьма огромным, так как разные позиции в этих играх исчисляются миллионами. А вот для игры «крестики – нолики» на доске 3 * 3 соответственный граф нарисовать не так тяжело, хотя и он будет содержать несколько 10-ов ( но не миллионов) вершин.
Свойство графов не зависят от того, соединены верхушки отрезками либо кривыми линиями, что дает возможность исследования их параметров при помощи одной из юных наук – топологии.
В первый раз базы теории графов возникли в работе Л. Эйлера, где он описывал решение головоломок и математических веселительных задач. Обширное развитие теория графов получила с 50-х гг. 20 в. в связи со становлением кибернетики и развитием вычислительной техники.
В определениях графов просто формулируется и решается задачка о предназначении на должности. А конкретно: если имеется несколько свободных должностей и группа лиц, желающих их занять, при этом любой из претендентов имеет квалификацию для нескольких должностей, то при каких критериях любой из претендентов сумеет получить работу по одной из собственных специальностей?
характеристики графов не зависят от того, соединены верхушки отрезками либо кривыми линиями. Это дает возможность исследования их параметров при помощи одной из юных наук – топологии, хотя сами задачки теории графов являются обычными задачками комбинаторики.
Вот несколько задач теории графов. Задачка о эйлеровом пути: отыскать путь по ребрам графа, проходящий по любому ребру ровно один раз. Таковой путь существует только в том случае, если граф – связный, т. е. от каждой его верхушки к каждой иной можно пройти по ребрам графа, и из каждой верхушки, не считая, быть может, 2-ух, выходит четное число ребер. На графе, изображенном на рис. 3,а, он есть, а на рис. 3,б его нет.
Хроматическим числом графа именуется меньшее количество красок, при помощи которых можно так раскрасить верхушки графа, что любые две верхушки, соединенные ребром, окрашиваются при всем этом в различные цвета. Длительное время арифметики не могли решить эту делему: довольно ли 4 красок, для того чтоб раскрасить произвольную видеокарту так, чтоб любые две стороны, имеющие общую границу, были покрашены различными красками? Если изобразить страны точками – верхушками графа, соединив ребрами те верхушки, для которых надлежащие им страны граничат , то задачка сведется к последующей: правильно ли, что хроматическое число хоть какого графа, размещенного на плоскости, не больше 4? Положительный ответ на этот вопросец был только не так давно получен при помощи ЭВМ (Электронная вычислительная машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач).
Используя графы можно решать задачки. Вот, к примеру, как смотрится крайняя южноамериканская версия известной задачки Дьюдени:
1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не непременно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, движутся трое пассажиров с теми же фамилиями. В предстоящем всякого пассажира мы будем уважительно именовать «мистер» (м-р)
2. М-р Робинсон живет в Лос-Анджелесе.
3. Кондуктор живет в Омахе.
4. М-р Джонс издавна позабыл всю алгебру, которой его учили в институте.
5. Пассажир – однофамилец кондуктора живет в Чикаго.
6. Кондуктор и один из пассажиров, узнаваемый спец по математической физике, хотя в одну церковь.
7. Смит постоянно выигрывает у кочегара, когда им случается встречаться за партией в бильярд.
Как фамилия машиниста?
тут 1-5 – номера ходов, в скобках – номера пт задачки, на основании которых изготовлены ходы (выводы).
Дальше следует из п.7, что кочегар не Смит, как следует, Смит-машинист.
Заключение
В реальном реферате рассмотрены математические графы, области их внедрения, принято решение несколько задач при помощи графов. Графы довольно обширно используются в арифметике, технике, экономике, управлении. Познание основ теории графов нужно в разных областях, связанных с управлением созданием, делом (к примеру, сетевой график строительства, графики доставки почты). Не считая того, работая над рефератом, я освоил работу на компе в редакторе текста WORD. Таковым образом, задачки реферата выполнены.
Перечень литературы
1. Энциклопедический словарь молодого математикаСост.А.П.Савин.- М.: Педагогика, 1989
2. Квант №6 1994г.
3. М.Гарднер «Математические досуги»М.: мир, 1972
]]>