Информационные модели на графах. Деревья

Граф – это средство наглядного представления состава и структуры системы, совокупность точек, соединенных между собой линиями.

Точки называются вершинами графа. Они могут изображаться точками, кружочками, прямоугольниками и пр.
Линии, соединяющие вершины, называются дугами (если задано направление от одной вершины к другой) или ребрами (если направленность двусторонняя).

Граф, в котором все линии направленные, называется ориентированным, в противном случае - неориентированным.
Две вершины, соединенные дугой или ребром, называются смежными.
Линия, выходящая из некоторой вершины и входящая в неё, называется петлёй.

Петля
Вершина
Дуга
Ребро

Графы используются во многих областях человеческой деятельности
Знакомую всем схему метрополитена можно рассмотреть как граф. Вершинами являются станции метро, линии отражают рельсовую связь между станциями.

Этот пример относится к органической химии. Известно, что свойства химических веществ, называемых углеводородами, зависят не только от того, из какого количества атомов углерода и водорода состоит молекула, но и от способа их соединения, структуры молекулы.

Этот пример относится к медицине. Как известно, у разных людей кровь отличается по группе. Всего групп крови четыре. В нормальных условиях номер группы крови роли не играет, а вот при переливании, играет и весьма существенную. Дело в том, что не все группы крови совместимы. Возможность переливания крови разных групп может быть отражена с помощью графа.

О некоторых типах графов
Взвешенный (размеченный) граф – это граф, в котором с вершинами или линиями связана некоторая дополнительная информация. Это информация называется весом вершины или линии.

Цепь, начальная и конечная вершины которой совпадают, называется циклом.
Граф с циклом называется сетью.
О некоторых типах графов

Такой граф называется семантической сетью.

Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.
Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой)

Иерархическую структуру имеет школа

Состав прикладного ПО

Отличительная особенность - между любыми двумя вершинами дерева существует единственный путь.
Дерево не содержит циклов и петель.
Корень дерева - одна главная вершина.
Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня.
Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим».
Вершины, не имеющие порожденных вершин, называются листьями.
Дерево - граф иерархической системы.

Схема отношений
«является разновидностью»

Лесенка
Рептилии
Черепахи
Крокодилы
Клювоголовые
Чешуйчатые
Ящерицы
Змеи

Многоуровневая иерархическая файловая система
Если на диске хранятся сотни и тысячи файлов, то для удобства поиска файлы организуются в многоуровневую иерархическую файловую систему, которая имеет «древовидную» структуру (имеет вид перевернутого дерева).

Путь к файлу
В путь к файлу входят записываемые через разделитель "\" логическое имя диска и последовательность имен вложенных друг в друга каталогов, в последнем из которых находится данный нужный файл.
C:\Рефераты\
C:\Рефераты\Физика\
C:\Рефераты\Информатика\
C:\Рисунки\

Полное имя файла
Путь к файлу вместе с именем файла называют полным именем файла.
C:\Рефераты\Физика\Оптические явления.doc
C:\Рефераты\Информатика\Интернет.doc
C:\Рефераты\Информатика\Компьютерные вирусы.doc
C:\Рисунки\Закат.jpg
C:\Рисунки\ Зима.jpg

Операционная система позволяет получить на экране компьютера изображение файловой системы в виде дерева.

Д/з:Назовите полные имена всех файлов