Сохраните летнее настроение в новом учебном году! –90% на доступ к материалами по вашему предмету или классу

СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Выбрать материалы

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Был в сети 09.06.2025 13:36

Бодров Сергей Иванович

10 625

3 964

Подписчики

Подписки

Специализация

Прочее

Обо мне Блог Файлы Тесты Галерея Активность Награды

Практическая работа. Использование теории графов

Категория: Информатика

27.10.2017 18:24

Цель: научиться определять зависимости между элементами системы с помощью теории графов.

Просмотр содержимого документа
«Практическая работа. Использование теории графов»

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ЛУГАНСКОЙ НАРОДНОЙ РЕСПУБЛИКИ

"КИРОВСКАЯ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №3"

Практическая работа

урока информатики

Тема: “Использование теории графов”

Составитель: учитель информатики II категории

Петров Денис Сергеевич

2017 г.

Цель: научиться определять зависимости между элементами системы с помощью теории графов.

Задача: для любых 3 произвольных систем построить графы структуры и соответствующие им матрицы смежности (взяв любые 5-7 элементов системы).

Выполнение работы

Маршрут "Таксист"

	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Х8	Х9	Х10
Х1	0	1	1	0	0	0	0	0	0	0
Х2	1	0	1	1	1	1	1	1	1	1
Х3	1	1	0	1	1	1	1	1	1	1
Х4	0	1	1	0	1	1	1	1	1	1
Х5	0	1	1	1	0	1	1	1	1	1
Х6	0	1	1	1	1	0	1	1	1	1
Х7	0	1	1	1	1	1	0	1	1	1
Х8	0	1	1	1	1	1	1	0	1	1
Х9	0	1	1	1	1	1	1	1	0	1
Х10	0	1	1	1	1	1	1	1	1	0

М „Т”=

Матрица смежности неориентированного графа

Беларусь (х1)

Украина (х2)

Россия (х3)

Англия (х4)

Іспания (х5)

США (х6)

Бразилия (х7)

Канада (х8)

Португалия (х9)

Франция (х10)

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

Стармир "Привет"

	Х1	Х11	Х12	Х13	Х14	Х15	Х2	Х21	Х22	Х23	Х3	Х31	Х32	Х33	Х34	Х35	Х36	Х4	Х41	Х42
Х1	0	1	1	1	1	1	1	0	0	0	1	0	0	0	0	0	0	1	0	0
Х11	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Х12	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Х13	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Х14	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Х15	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Х2	1	0	0	0	0	0	0	1	1	1	1	0	0	0	0	0	0	1	0	0
Х21	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
Х22	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
Х23	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
Х3	1	0	0	0	0	0	1	0	0	0	0	1	1	1	1	1	1	1	0	0
Х31	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
Х32	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
Х33	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
Х34	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
Х35	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
Х36	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0
Х4	1	0	0	0	0	0	1	0	0	0	1	0	0	0	0	0	0	0	1	1
Х41	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
Х42	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0

Матрица смежности ориентированного графа

Швеция(х21) Австрия(х22) Лихтенштейн(х23)

Германия(х2)

Канада(х11) Белорусь(х31)

Сейшельские о-ва(х12) Украина(х32)

США(х1) Росія(х3)

Багамськие о-ва(х13) Молдавия(х33)

Куба(х14) Латвия(х34)

Бразилия(х15) Литва(х35)

Польша(х36)

Китай(х4)

Казахстан(41) Япония(х42)

Ориентированний граф

Вокруг света до конца лета "Путешественник"

	Х	Х1	Х11	Х12	Х2	Х21	Х22	Х23	Х3	Х31	Х32
Х	0	1	0	0	0	0	0	0	0	0	0
Х1	1	0	1	1	0	0	0	0	0	0	0
Х11	0	0	0	0	1	0	0	0	0	0	0
Х12	0	0	0	0	1	0	0	0	0	0	0
Х2	0	0	0	0	0	1	1	1	0	0	0
Х21	0	0	0	0	0	0	0	0	1	0	0
Х22	0	0	0	0	0	0	0	0	1	0	0
Х23	0	0	0	0	0	0	0	0	1	0	0
Х3	0	0	0	0	0	0	0	0	0	1	1
Х31	1	0	0	0	0	0	0	0	0	0	0
Х32	1	0	0	0	0	0	0	0	0	0	0