Решение задач с помощью графов

Решение задач на моделирование с помощью графов 

6 класс

Задачи урока: 

обобщение и систематизация представлений учащихся о графических информационных моделях;

выявление преимуществ применения моделирования на графах при решении задач;

содействие успешному усвоению учащимися учебного материала по курсу информатики.

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

Вершины графа представляют отдельные объекты, а ребра между вершинами представляют отношения или связи между этими объектами.

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

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

Еще одним важным примером применения графов является моделирование социальных сетей, таких как Facebook, LinkedIn и Twitter. Графы позволяют анализировать друзей, сообщества, подписчиков и другие связи между пользователями.

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

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

Задание 1. Повторение пройденного материала

Задание 2. Определи элементы взвешенного графа

Задание 3. Виды графов

По рисунку:

 1. Назовите вершины, ребра графа; 

2. Приведите примеры цепей и циклов в графе.

3. Определите, какие два пункта наиболее удалены друг от друга (если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). 

ТЕОРЕТИЧЕСКИЙ БЛОК

1. Столбцы таблицы называются полями, а строки – записями

2. Каждая таблица содержит описание одного типа объектов (человека, бригады, самолета) или одного типа связей между объектами.

3.В каждой таблице есть ключ – некоторое значение, которое отличает одну запись от другой; в таблице не может быть двух записей с одинаковыми значениями ключа

4. На практике часто используют искусственно введенное числовое поле, которое называется идентификатор, ID.

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

Граф состоит из вершин, связанных линиями-ребрами. Вершины графа изображаются кругами, овалами, точками.

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

Неориентированные графы

I. два варианта значения слова “граф”:

1) удобная форма описания структур типа дорожной сети или сети передачи данных;

2) математический объект G := (V, E), где V — это непустое множество вершин, а E — множество ребер (пар вершин).

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

Если, например, на пересечении строки A и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности.

Задание 4.  Решение задачи с помощью матрицы смежности

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

#открыто4ка #вмиреИТ #vmireit #культура&искусство