Семинар Доом " Применение графов "

Версия 12:02, 31 марта 2008

Графом в математике называется конечная совокупность точек (называемых вершинами) соединенных друг с другом линиями ( ребрами)графа.

При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции – вершины графа, а соединяющие их пути – ребра. Граф на рисунке изображает схему дорог между селами М, А, Б, В. Из пункта М надо завести продукты в два из трех сел (А, Б, С)Расстояние между МА=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 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков вершин.

Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.