Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.

Презентация:



Advertisements
Похожие презентации
Решение задач с помощью графов. Кенигсбергские мосты Можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
Advertisements

Фигура (граф), которую можно начертить не отрывая карандаш от бумаги, называется уникурсальной.
Научно -исследовательская работа Авторы: Быстрякова Наталья, Шайахметова Алина ученицы 9 В класса МАОУ « СОШ9» г.Нурлат, РТ Руководитель: Мустафина Наталья.
Рисунок одним росчерком пера. Проект по элективному курсу по математике «Круги Эйлера. Графы.» на тему Выполнила ученица 9Б класса средней школы 9 Миронова.
ЕГО ВЕЛИЧЕСТВО ГРАФ. Введение С дворянским титулом «граф» эту тему связывает только общее происхождение от латинского слова «графио» - пишу. ГРА Ф ИО.
Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ. Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ.
V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.
Определение графа Фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или.
Алексеева Е.В., учитель информатики и ИКТ МОУ «Сланцевская СОШ 3» Введение в теорию графов 11 класс начать.
Графы Степень вершины Подсчет числа ребер графа. Разминка… Вставьте недостающие слова в предложения (граф, титул, ребро, вершина) Всем известно, что слово.
Не говори, чему учили, а скажи, что узнал. (Пословица)
Системный подход в моделировании. «Система (от греч. – целое, составленное из частей; соединение) – множество элементов, находящихся в отношениях друг.
Проект: «Графы». Цели проекта: изучить теорию «Граф», изучить теорию «Граф», развить навыки самостоятельной работы, развить навыки самостоятельной работы,
Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,
Работу выполнил ученик 8а класса Кичиков Валерий Кичиков Валерий Учитель Еремеева Н.Н. Учитель Еремеева Н.Н. Работу выполнил ученик 8а класса Кичиков Валерий.
ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год.
Презентация по Информатике Тема: «Графы» Выполнил: Бычков Георгий.
Графы и сети.. Графы. Граф Граф – это средство для наглядного представления элементного состава системы и структуры связей. Составными частями графа являются.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.
Информационные модели на графах Болгова Н.А.- Учитель информатики МБОУ СОШ с УИОП с.Тербуны.
Транксрипт:

Домашнее задание «Применение графа»

ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью множества различных путей перемещения по ребрам между некоторыми парами вершин Граф называется связным если любая пара его вершин связная. Ребро соединяет две вершины графа элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом Вершина Ребро это ориентированное ребро. Дуга ребро, начало и конец которого находятся в одной и той же вершине Петля любой связный граф, не имеющий циклов. Дерево

Кенигсбергские мосты

Можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

Представим задачу в виде графа,где вершины – острова и берега (A,B,C,D), а ребра – мосты Важно, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста.С А Д В

Какие вершины четные, а какие нечетные? Подпишем степени вершин в кружочках. А, B, C, D. Нечетные вершины: А, B, C, D. А В С Д

эйлеровым графом Если граф имеет цикл, содержащий все ребра графа по одному разу (Эйлерова линия),то такой граф называется эйлеровым графом Условия существования Эйлеровой линии: -граф связный -все вершины четные эйлеров граф Другими словами, эйлеров граф – это граф,который можно нарисовать одним росчерком Эйлеров граф

Алгоритм решения задач 1. Нарисовать граф, где вершины – острова и берега, а ребра – мосты. 2. Определить степень каждой вершины и подписать возле нее. 3. Посчитать количество нечетных вершин. 4. Обход возможен: a. ЕСЛИ все вершины – четные, и его можно начать с любого участка. b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей. 5. Обход невозможен, если нечетных вершин больше Сделать ВЫВОД. 7. Указать Начало и Конец пути.

Достроить графы до Эйлеровых А А А Б Б Г Г Д АБ Г В В В В Б

Задача о 15 мостах В некоторой местности через протоки переброшено 15 мостов. А E В F С D

Построим граф, где вершины – острова и берега, а ребра – мосты. Нечетные вершины: D, E. ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен. Его Начало может быть в местности D, а Конец в местности E. А E В F С D

Домашнее задание Можно ли фигуры, изображенные на рисунках, нарисовать одним росчерком ? (решить с помощью графа)