Семинар Доом " Применение графов " - История изменений

Nika в 05:10, 22 сентября 2008

2008-09-22T05:10:32Z

Демина Татьяна Валерьевна: «Применение графов ID 116» переименована в «Семинар Доом " Применение графов "»

2008-03-31T08:22:13Z

«Применение графов ID 116» переименована в «Семинар Доом " Применение графов "»

Демина Татьяна Валерьевна в 08:02, 31 марта 2008

2008-03-31T08:02:44Z

Демина Татьяна Валерьевна в 07:35, 31 марта 2008

2008-03-31T07:35:16Z

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

2008-03-31T07:31:41Z

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

Новая страница

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

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

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

← Предыдущая		Версия 05:10, 22 сентября 2008
Строка 26:		Строка 26:
	Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.		Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.

−	[[Категория: ~~Проект~~ ДООМ]]	+	[[Категория:Архив проекта ДООМ 2007-2008 (2 цикл)]]

← Предыдущая		Версия 07:35, 31 марта 2008
Строка 22:		Строка 22:

	Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.		Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топология.
		+
		+	[[Категория: Проект ДООМ]]

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