Семинар Доом " Применение графов "
Графом в математике называется конечная совокупность точек (называемых вершинами) соединенных друг с другом линиями ( ребрами)графа.
При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции – вершины графа, а соединяющие их пути – ребра. Граф на рисунке изображает схему дорог между селами М, А, Б, В. Из пункта М надо завести продукты в два из трех сел (А, Б, С)Расстояние между МА=3 км, АС=2 км, МВ=4 км, ВС=1 км, МС=3 км, АВ=5 км.
Существует много различных маршрутов поездки. Как выбрать наикротчайший путь? Составим граф на котором легко увидеть возможные маршруты.
Расставим вдоль его ребер цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Получим, что наименьшее расстояние равно 4. Подобные задачи возникают часто при нахождении наилучших вариантов развозки товаров по магазинам, материалов по стройкам.
В строительстве графы используются при планировании проведения работ.
Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л. воды, и имеется две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л. воды и оставить в ведре 4 л., т.е. разлить воду поровну в ведро и большую кастрюлю.
Ситуацию в каждый момент можно описать тремя числами (x,y,z), где x – количество литров воды в ведре, y – в большой кастрюле, z – в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0), если наполним меньшую кастрюлю.
В результате получаем два решения : одно в 7 ходов, другое в 8 ходов.
Подобным образом можно составить граф любой позиционной игры : шахмат , шашек, крестиков-ноликов, где позиции станут вершинами, а направленные отрезки между ними будут означать , что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.
Однако для шахмат и шашек такой граф будет очень большим , поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры в крестики-нолики на доске 3*3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков вершин.
Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.
