Файл: Решение задач с применением графов при подготовке к огэ по информатике.docx

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

Задачи: Систематизировать и расширить представления учащихся о графах; формировать познавательный интерес к изучению информатики; развивать мыслительные процессы учащихся (анализ, систематизация, классификация)

Ходурока:

Организационный момент. Приветствие учащихся, проверка готовности к уроку. Домашнее задание – пробный вариант ОГЭ. Тетради с решением собрать в конце урока. С вопросами можно подойти на кружковом занятии (7 урок).

Мотивационный момент.

Вместо предисловия

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

В нашей школе учащиеся очень часто стали выбирать экзамены по информатике.

При подготовке к ОГЭ и ЕГЭ у многих учащихся возникают трудности при решении тех или иных задач, однако, многие типы задания можно решить очень просто с помощью графов.
Определения выучить

1. Граф – это наглядное средство представления состава и

структуры системы.

2. Граф – это конечное множество точек, некоторые из которых соединены линиями.

3. Точки – называются вершинами, а соединяющие их линии – ребрами.

4. Цепь – это путь по вершинам и ребрам графа, включающий любое ребро не более одного раза.

5. Ориентированный граф – это граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений.

6. Цикл – это цепь, начальная и конечная вершины которой совпадаю. Граф с циклами называют сетью.

7. - Что такое дерево? Ответ: Дерево – это граф, представленный в виде иерархической системы.

8. Взвешенный граф – это граф, у которого вершины или ребра (дуги) характеризуются некоторой
На слайде задание Пример 1. Какая модель позволяет легко и просто решать такие задачи? Граф. В ОГЭ по информатике для 9 класса 3 типа задач можно легко решить, используя теорию графов. Для начала вспомним, что называют графом.

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

Первый тип задач – задания В3.

	A	B	C	D	E	F
A		3	5			15
B	3			4
C	5			1
D		4	1		2	6
E				2		1
F	15			6	1

Пример 1. Между населѐнными пунктами A, B, C, D, E, F построены дороги, протяжѐнность которых (в километрах) приведена в таблице. Передвигаться можно только по дорогам, указанным в таблице.

1) 9

2) 11

3) 13

4) 15

Определите длину кратчайшего пути между пунктами A и F. Решение:

1. 
   Точками A, B, C, D, E, F, расположенными по кругу, обозначим населенные пункты.
   
2. 
   Если в таблице есть число, соединяем точки отрезком и подписываем сверху это число.
   
3. 
   Отмечаем конечный пункт (в нашем случае это F) и рассматриваем пункты, из которых можно в него попасть. (в нашем случае это A, E, D). В свою очередь в пункт E можно попасть из D, а в пункт D – из C и B. В пункты C и B попадаем из A. Получили начальный пункт. Изобразим дерево всех возможных путей из A в F.
   
4. 
   Вычислим длины полученных дорог.
   
5. 
   AF=15, ACDEF=9, ABDEF=10, ACDF=12, ABDF=13.
   
6. 
   Выбираем длину кратчайшего пути – 9, в предложенных вариантах это ответ №1.
   

Ученик у доски

Пример 2. Между населѐнными пунктами A, B, C, D, E построены дороги, протяжѐнность которых (в километрах) приведена в таблице. Передвигаться можно только по дорогам, указанным в таблице.

	A	B	C	D	E
A		2	5	1
B	2		1
C	5	1		3	2
D	1		3
E			2

1) 4

2) 5

3) 6

4) 7

Определите длину кратчайшего пути между пунктами A и E. Ответ: №2.