Семинар ДООМ "Основные понятия теории графов."

Версия 20:16, 2 декабря 2007 (просмотреть исходный код) Егорчева Светлана Валентиновна (обсуждение | вклад) ← Предыдущая правка		Текущая версия на 14:45, 10 января 2008 (просмотреть исходный код) Васильева Александра (обсуждение | вклад)
(не показаны 15 промежуточных версий 1 участника)
Строка 9:		Строка 9:
	прививать самостоятельность, нестандартность мышления, интерес к математике.		прививать самостоятельность, нестандартность мышления, интерес к математике.
−	''' ХОД УРОКА:'''	+	<h2><font color="A52A2A">'''ХОД УРОКА:'''</font></h2>
		+
	''Рассмотрим следующую задачу:''		''Рассмотрим следующую задачу:''
−	Между планетами введено космическое сообщение по следующим маршрутам:	+	<pre>Между планетами введено космическое сообщение по следующим маршрутам:
−	З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?	+	З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?</pre>
	'''РЕШЕНИЕ:'''		'''РЕШЕНИЕ:'''
−	Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие  маршруты. Получается следующий чертеж: (рис.1)
−	(рис.1)	+	Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим
		+	названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие  маршруты. Получается следующий чертеж: (рис.1)
		+	[[Изображение:risss1.gif]]
		+	(рис.1)
	Глядя на него можно ответить, что от З до М добраться нельзя.		Глядя на него можно ответить, что от З до М добраться нельзя.
Строка 29:		Строка 32:
	Ребята мы решили эту задачу с помощью графов.		Ребята мы решили эту задачу с помощью графов.
−	<pre>'''ОПРЕДЕЛЕНИЕ:''' ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков, прямых или кривых (ребра графов).</pre>	+	<h5><font color="A52A2A">'''ОПРЕДЕЛЕНИЕ:
		+
		+	ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков, прямых или кривых (ребра графов)'''.</font></h5>
	Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)		Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)
Строка 37:		Строка 42:
	Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.		Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.
−	'''Сформулируем некоторые закономерности, присущие  определенным графам:'''	+	<h4><font color="blue">'''Сформулируем некоторые закономерности, присущие  определенным графам:'''</font> </h4>
	'''1)''' Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.		'''1)''' Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Строка 55:		Строка 60:
	'''8)''' Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.		'''8)''' Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.
−	Разберем еще некоторые понятия, необходимые для решения задач, используя графы.	+	<h4><font color="blue">'''Разберем еще некоторые понятия, необходимые для решения задач, используя графы.'''</font></h4>
−	Путем в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении  не повторяется дважды.	+
−	Циклом называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.	+	<h5><font color="A52A2A">'''Путем'''</font></h5>в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении  не повторяется дважды.
		+
		+	<h5><font color="A52A2A">'''Циклом'''</font></h5>называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.
	Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.		Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.
−	Деревом называется любой  связный граф , не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий.	+
		+	<h5><font color="A52A2A">'''Деревом'''</font></h5>называется любой  связный граф , не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий.
	(рис.2)		(рис.2)
		+	[[Изображение:riss2.gif]]
−		+
−	(рис.2)	+	''Рассмотрим задачу, которую легко можно решить, используя теорию графов.''
−	Рассмотрим задачу, которую легко можно решить, используя теорию графов.	+
	'''ЗАДАЧА.'''		'''ЗАДАЧА.'''
−	Красный,  синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?	+	<pre>Красный,  синий, желтый и зеленый карандаши лежат в четырех коробках по одному.
		+
		+	Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке,
		+
		+	а красный не лежит в желтой. В какой коробке лежит каждый карандаш?</pre>
	'''РЕШЕНИЕ:'''		'''РЕШЕНИЕ:'''
−	обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш, то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.	+	<pre>обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке,
−		+	пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,
−	(рис. 4) (рис.5)	+
		+	то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.</pre>
		+
		+	[[Изображение:risss4.gif]]
−	Для следующей задачи постройте граф, соответствующей решению задачи.	+	''Для следующей задачи постройте граф, соответствующей решению задачи.''
	'''ЗАДАЧА.'''		'''ЗАДАЧА.'''
−	В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз. Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой. Сколько пар проведено и сколько еще осталось?	+	<pre>В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена.
		+
		+	Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.
		+
		+	Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой.
		+
		+	Сколько пар проведено и сколько еще осталось?</pre>
	'''РЕШЕНИЕ:'''		'''РЕШЕНИЕ:'''
−	(рис.6) Изобразим данные задачи в виде схемы. Участники – это точки, сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно , проведено 7 игр, осталось провести – 8 игр.	+	[[Изображение:riss6.gif]]
		+
		+	<pre> Изобразим данные задачи в виде схемы. Участники – это точки,
		+
		+	сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно ,
		+
		+	проведено 7 игр, осталось провести – 8 игр.</pre>
		+
		+	'''ДОМАШНЕЕ ЗАДАНИЕ:'''
		+	Решите с помощью графов.
		+	'''ЗАДАЧА:'''
		+	<pre>В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена.
		+	Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три.
−	'''ДОМАШНЕЕ ЗАДАНИЕ:'''	+	Сколько лет Лене?
−	Решите с помощью графов.	+	'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет. </pre>
−	'''ЗАДАЧА:''' В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена. Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три. Сколько лет Лене?	+
−	'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет.	+
	Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.		Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.
−	[[Категория:Проект ДООМ]]	+	[[Категория:Проект ДООМ 2007-2008 (1 цикл)]]

---

Текущая версия на 14:45, 10 января 2008

участник: Трифонова Валентина Артемьевна, 022.

ЦЕЛИ:

познакомиться с определением графов и его сопутствующими понятиями ;

разобрать закономерности, по которым строятся графы и с помощью них решаются логические задачи;

прививать самостоятельность, нестандартность мышления, интерес к математике.

Содержание 1 ХОД УРОКА: 1.1 Сформулируем некоторые закономерности, присущие определенным графам: 1.2 Разберем еще некоторые понятия, необходимые для решения задач, используя графы. 1.2.1 Путем 1.2.2 Циклом 1.2.3 Деревом

ХОД УРОКА:

Рассмотрим следующую задачу:

Между планетами введено космическое сообщение по следующим маршрутам: 

З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?

РЕШЕНИЕ:

Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим

названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: (рис.1)

(рис.1)

Глядя на него можно ответить, что от З до М добраться нельзя.

Ребята мы решили эту задачу с помощью графов.

ОПРЕДЕЛЕНИЕ: ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков, прямых или кривых (ребра графов).

Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.) Графы упрощают решение многих логических задач, экономических, физических и других. Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры. Рассмотрим процесс соединения вершин графа ребрами. Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.

Сформулируем некоторые закономерности, присущие определенным графам:

1) Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

2) Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива для любого графа.

3) Если степени всех вершин графа равны, то граф называется однородным.

4) Число нечетных вершин любого графа четно.

5) Невозможно начертить граф с нечетным числом нечетных вершин.

6) Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.

7) Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.

8) Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.

Разберем еще некоторые понятия, необходимые для решения задач, используя графы.

Путем

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

Циклом

называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.

Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.

Деревом

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

(рис.2)

Рассмотрим задачу, которую легко можно решить, используя теорию графов.

ЗАДАЧА.

Красный,  синий, желтый и зеленый карандаши лежат в четырех коробках по одному. 

Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке,

 а красный не лежит в желтой. В какой коробке лежит каждый карандаш?

РЕШЕНИЕ:

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

пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,

 то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.

Для следующей задачи постройте граф, соответствующей решению задачи.

ЗАДАЧА.

В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. 

Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.

 Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой. 

Сколько пар проведено и сколько еще осталось?

РЕШЕНИЕ:

 Изобразим данные задачи в виде схемы. Участники – это точки,

 сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно , 

проведено 7 игр, осталось провести – 8 игр.

ДОМАШНЕЕ ЗАДАНИЕ: 

Решите с помощью графов.

ЗАДАЧА:

В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена. 

Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три. 

Сколько лет Лене?

'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет. 

Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.