Ученики на Учителя.com


Практическое занятие "Множества и графы"

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 11
МНОЖЕСТВА И ГРАФЫ
Цель работы: ознакомление с множествами, функциями, операциями,
способами их заданий. Построение кругов Эйлера.
Ход занятия: На основе полученных данных рассмотреть операции
объединения, пересечения, разности и дополнения с помощью диаграмм
Эйлера.
Краткие теоретические сведения:
На конкретных примерах покажем выполнение операций над
множествами и способы их заданий, графическое изображение множества с
помощью диаграмм Эйлера.
Пример 1. Найти все подмножества множества А = { 1; 2; 3 }.
Решение:
Подмножествами данного множества являются множества:
{ 1 }, { 2 }, { 3 }, { 1; 2 }, { 1; 3 }, { 2; 3 }, { 1; 2; 3 }, O.
Пример 2. Найдите:
.,\,, АВАВАВА
.3;1,6;5;3;1 == BA
Решение:
Находим:
.5
6;53;1\6;5;3;1\
3;13;16;5;3;1
6;5;3;13;16;5;3;1
=
==
==
==
А
ВА
ВА
ВА
Пример 3. Дано множество: M = { a; u; o; p; c; ы }.
1) написать определяющие слова;
2) задать с помощью матрицы инцидентности;
3) построить модельный граф;
4) построить гиперграф;
5) построить двудольный граф.
Решение:
1)
.,,,,,,,,,,,
4321
acopыccuppoс ====
2) запишем матрицу инцидентности:
ысроиа
.
010101
111000
011010
011100
=Q
3) построим модельный граф:
с (1,2,3,4)
и (2) а (4)
ы (3)
р (1,2,3) о (1,4)
4) построим гиперграф:
5) построим двудольный граф:
Вопросы для самопроверки:
1. Какими способами можно задать множество?
2. Что называется объединением, пересечением множеств?
3. Что называется разностью, дополнением множеств?
4. Отношения, способы их задания и свойства.
и
ы
р
а
0
1
2
3
4
а и о р с ы
о
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 12
ДИФФЕРЕНЦИРОВАНИЕ ГРАФОВ И МОГРАФОВ
Цель работы: ознакомление со взвешенным графом и его матричным
заданием, дифференцированием графов и мографов; приобретение навыка
пользования ими при обработке данных.
Ход занятия:
1. Найти производную от графа по событию, характеризовать число
вхождения каждого из ребер в остовы.
2. Алгоритм построения дерева.
Краткие теоретические сведения:
На конкретных примерах покажем построение дерева по его алгоритму.
Для решения оптимизационных задач введем понятие производной,
основанное на использовании понятия частоты букв в словах некоторой
модели.
Пример 1. Пусть задан граф G (рис.1). Определить частоту участия ребер
в образовании остовов граф G .
Решение:
Граф G содержит 8 остовов (рис. 2). Частоту определим числом
вхождения каждого из ребер в эти остовы.
Рисунок 1 – Граф G
Ребро а участвует 5 раз в образовании остовов, ребро с – 4 раза и т.д. Ребра
а и b содержатся в двух остовах и т.д. Это отношение показывает степень
участия пар ребер в образовании остовов графа.
b d
c
a e
Рисунок 2 – Остовы графа G
Заданное событие определяет модель, матрицу инцидентности. Вычисляя
значения производной на ребрах графа:
5,2
2
4225
2
),(
3
2
5225
2
),(
=
+−
=
+−
=
=
+−
=
+−
=
ac
caca
ab
baba
f
fff
ca
дS
дG
f
fff
ba
дS
дG
и т.д., получаем граф (рис.3).
Рисунок 3 – Модель графа G
Пример 2. Найти распределение пустых подграфов в графе G (рис. 4).
c
a e
b
a e
d
c
a
b d
a
b d b d
c
e
b
c
e
d
a e
c
2,5 2,5
4/3
b d
2,5
3 3
a 4/3 e
1
2 6
3 4 5
Рисунок 4 – Граф G
Сопоставим корню строящегося дерева заданный граф G. Зафиксируем
вершину
.
2
Ее окрестность состоит из четырех вершин, поэтому из первого
корня выводим пять дуг. Концам дуг приписываем из вершин и взвешиваем
дуги неокрестностью этих вершин (рис. 5). Неокрестность содержит только
вершину
,
5
поэтому в третьем ярусе получаем висячую вершину
.
5
Зафиксируем вершину
.
4
Ее неокрестностью в третьем ярусе получаем
висячую вершину
.
4
Образуем еще две дуги из второго корня и т.д.
Согласно закону поглощения, одно из поддеревьев поглощается. Все пустые
подграфы не учитываются при подсчете. Таким образом, имеем пустые
подграфы:
6,3,5,3,1,4,1,5,2
4321
==== EEEЕ
Вопросы для самопроверки:
1. Что называется графом?
2. Дать определение взвешенного графа, способы его задания.
3. Что называется деревом?
4. Алгоритм построения дерева.
2 1 6 4
3
5
4
3 5 3
6 5 1
5,2
1
=Е
4,1
2
=Е
6,3
4
=Е
5
5,3,1
3
=Е
Скачать материал

Математика - еще материалы к урокам: