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

Материал из ТолВИКИ
(Различия между версиями)
Перейти к: навигация, поиск
 
(не показаны 2 промежуточные версии 1 участника)
Строка 3: Строка 3:
 
При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции – вершины графа, а соединяющие их пути – ребра.
 
При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции – вершины графа, а соединяющие их пути – ребра.
 
Граф на рисунке изображает схему дорог между селами М, А, Б, В. Из пункта М надо завести продукты в два из трех сел (А, Б, С)Расстояние между МА=3 км, АС=2 км, МВ=4 км, ВС=1 км, МС=3 км, АВ=5 км.
 
Граф на рисунке изображает схему дорог между селами М, А, Б, В. Из пункта М надо завести продукты в два из трех сел (А, Б, С)Расстояние между МА=3 км, АС=2 км, МВ=4 км, ВС=1 км, МС=3 км, АВ=5 км.
 +
 +
[[Изображение:id_1165.jpg]]
 +
  
 
Существует много различных маршрутов поездки. Как выбрать наикротчайший путь? Составим граф на котором легко увидеть возможные маршруты.  
 
Существует много различных маршрутов поездки. Как выбрать наикротчайший путь? Составим граф на котором легко увидеть возможные маршруты.  
Строка 23: Строка 26:
 
Свойства графов не зависят от того,  соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.
 
Свойства графов не зависят от того,  соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.
  
[[Категория: Проект ДООМ]]
+
[[Категория:Архив проекта ДООМ 2007-2008 (2 цикл)]]

Текущая версия на 09:10, 22 сентября 2008

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

При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции – вершины графа, а соединяющие их пути – ребра. Граф на рисунке изображает схему дорог между селами М, А, Б, В. Из пункта М надо завести продукты в два из трех сел (А, Б, С)Расстояние между МА=3 км, АС=2 км, МВ=4 км, ВС=1 км, МС=3 км, АВ=5 км.

Id 1165.jpg


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

Расставим вдоль его ребер цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Получим, что наименьшее расстояние равно 4. Подобные задачи возникают часто при нахождении наилучших вариантов развозки товаров по магазинам, материалов по стройкам.

В строительстве графы используются при планировании проведения работ.

Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л. воды, и имеется две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л. воды и оставить в ведре 4 л., т.е. разлить воду поровну в ведро и большую кастрюлю.

Ситуацию в каждый момент можно описать тремя числами (x,y,z), где x – количество литров воды в ведре, y – в большой кастрюле, z – в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0), если наполним меньшую кастрюлю.

В результате получаем два решения : одно в 7 ходов, другое в 8 ходов.

Подобным образом можно составить граф любой позиционной игры : шахмат , шашек, крестиков-ноликов, где позиции станут вершинами, а направленные отрезки между ними будут означать , что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.

Однако для шахмат и шашек такой граф будет очень большим , поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры в крестики-нолики на доске 3*3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков вершин.

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

Личные инструменты
наши друзья
http://аудиохрестоматия.рф/