Презентация "Графы. Формализация. Решение задач"; 10-11 кл.

Воробьева Людмила Васильевна МБОУ «СОШ № 9» город Вязники, Владимирской обл.

Эти графы изоморфныразличаются формой или расположением вершин и ребер. 1 a 2 c 5 b e d f 3 4 1 a Смежные вершины соединены ребром. b 5 е 2 c d 4 f 3

Символическая a запись графа: 2 c a(1,2); b(1,4); c(2,4); d(3,5); Массив : e(5,4); f(3,4); Ребра 1 2 1 b 5 е d 4 f 3 3 4 5 6 Начало ребра 1 1 2 3 3 4 Конец ребра 2 4 4 4 5 5 Вес ребра a b c f d e

Символическая запись графа: a(1,2); b(1,4); c(2,4); d(3,5); e(5,4); f(3,4); 1 a b 5 е 2 c d 4 f 3 Таблица смежности графа: В е р ш и н ы 1 2 3 4 5 Вершины 1 2 3 4 a b a c f b c f d e 5 d e

a b c d e f g a 0 1 1 1 0 0 0 b 1 0 0 0 1 0 0 c 1 0 0 0 0 1 0 d 1 0 0 0 0 0 0 e 0 1 0 0 0 0 1 f 0 0 1 0 0 0 0 g 0 0 0 0 1 0 0 a b e c f g d

1. Выявление всех элементов объекта 2. Определение всех характеристик объекта( названий, номеров, весов) 3. Установление наличия и вида связи ( односторонняя или двусторонняя) 4. Выбор формы представления вершин и ребер. 5. Представление элементов и связей в графическом виде. 6. Символическая запись графа. 7. Табличная запись графа.

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

С помощью графического редактора изобразите графы, представленные множествами: • Вершины{1,2,3,4,5,6,7}; Ребра{(3,4), (7,4), (1,5), (2,3), (6,5), (1,4), (2,7), (6,7), (2,5), (1,3)} • Вершины{A,B,C,D,E,F}; Ребра{AF, DC,BE,CF,AB,DF,AD,BE,EC}

Источники • Учебник «Информатика и ИКТ»,Гейн А.Г. И др. 10кл., М. Просвещение • Учебник «Информатика и ИКТ»,Гейн А.Г. И др. 11кл.,М. Просвещение • Задачник-практикум ч.1. Семакин И.Г., М. БИНОМ ЛБЗ • Демо-ЕГЭ 2011