Модели знаний на графах

Граф – это система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (геометрический способ задания графа – см. рисунок 1).
Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – рёбрами.
Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.
Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.
Вершины в графе могут отличаться
друг от друга тем, скольким рёбрам они
принадлежат.

МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ
________________________________________
Маршрутом в графе называется чередующаяся последовательность вершин и рёбер, в которой любые два соседних элемента инцидентны: v0, e1, v1, e2, v2,...,ek, vk.
Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.
Простой путь – путь, в котором ни одна дуга не встречается дважды.
Контур – путь, у которого конечная вершина совпадает с начальной вершиной.
Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).
Цепь цепь – последовательность смежных вершин.
Замкнутая цепь называется циклом. Можно определить простые и элементарные цепи.

ОКНО ПРОГРАММЫ GRAFOANALIZATOR1.3.3
________________________________________

ОКНО ПРОГРАММЫ GRIN
________________________________________

Инструкция к выполнению практической работы № 10
Тема: Модели знаний на графах.
Цель: изучить основы графического представлений графов, простейших свойств графов, получить практический навык задания и визуализации графа на плоскости; закрепить навыки построения графов по образцу в графических средах (программы для графического представления графов).
Методическое и материально-техническое обеспечение:
Инструкция к выполнению практической работы №10.
Презентация «Модели знаний на графах».
Технические средства: персональный компьютер.
Программные средства: Windows XP, Grafoanalizator1.3.3 rus, grin_rus.

Ход работы
Задание 1. Изобразите графы в соответствующих программах. Полученные графы сохранить в свои папки.
Контрольные вопросы:
1. Что такое граф?
2. Какие виды графов бывают?
3. Из чего состоит граф?