Тема электронные средства обучения и их использование

Каркасом неориентированного графа называется его подграф, являющийся деревом.
Каркас должен содержать в точности те же вершины, что и исходный граф. Справедливо ут-
верждение, что неориентированный граф имеет каркас, если он связен.
Существует несколько алгоритмов нахождения каркасов в графах, подробно описанные
в специальной литературе. В их числе алгоритмы нахождения каркаса на основе поиска в
глубину и ширину, алгоритм Краскала, алгоритм Прима, алгоритм Эдмондса и другие. Опи-
сание этих алгоритмов встречается в большинстве монографий по теории графов и приложе-
ниям.
Очевидно, что для одного графа существует множество каркасов. Однако, это множе-
ство конечно. Для определения всех возможных каркасов разработаны специальные техно-
логии, основу которых составляют алгоритмы перечисления всех каркасов. К таким алго-
ритмам относятся алгоритм Винтера, алгоритм Чена и некоторые другие.
Таким образом, в рамках описания технологии информационного интегрирования по-
является подход, согласно которому по уже построенному графу понятий можно предъявить
разработчику содержательного наполнения электронного средства обучения набор деревьев-
каркасов, наиболее точно описывающих структуру и содержание образовательной области.
Далее в зависимости от целей и других компонентов методической системы обучения автор
учебного курса или ЭСО должен выбрать один из каркасов (представляющий собой дерево)
для дальнейшей работы.
Деревья обладают рядом свойств, которые полностью характеризуют их. На основе та-
ких свойств можно построить несколько определений дерева, эквивалентных данному выше
(эквивалентность таких определений доказана в теории деревьев):

---

111
§ деревом называется неориентированный граф, любые две вершины которого связаны
с помощью единственного пути,
§ деревом называется неориентированный граф без циклов, добавление любого ребра к
которому приводит к появлению в точности одного цикла,