Граф Веба
Объектная модель Всемирной паутины основана на теории графов дискретной математики. Ниже представлены понятия графа, интерпретированные к практике проектирования и управления гипертекстом. Консорциум W3C в спецификациях использует термины node, link, linked data, semantic relationship. В семантическом Вебе гиперссылки это не столько указатели, сколько отношения между сущностями. Эти отношения выражают семантические связи для создания взаимосвязанного осмысленного пространства. Именно поэтому в русскоязычном переводе я интерпретирую эти термины как «узел» и «связь».
Граф Всемирной паутины
Сеть(Web) — граф с размеченными элементами.
Ориентированная сеть — ориентированный граф, не содержащий контуров.
Граф (Graph) — пространство связанных узлов.
Элемент графа (Element) — узел или связь между узлами графа.
Граф Веба и любые его фрагменты изображают в виде схемы, содержащей точки и линии.
Точки изображают узлы. Заполненная (чёрная) точка обозначает ветку — узел, содержащий другие узлы. Незаполненная (белая) точка обозначает лист — терминальный узел, не содержащий другие узлы.
Линии отображают отношения между узлами. Толстая линия отражает отношения ветки, отношения с другими узлами. Тонкая линия отражает отношение с терминальным узлом.
Например,
■━ Корневой узел
┣━■ Узел ветки
┃ └─□ Терминальный узел, лист
┣━■ Узел ветки
┃ ┗━■ Узел ветки
┃ ┗━■ Узел ветки
┃ └─□ Терминальный узел, лист
┗━■ Узел ветки
└─□ Терминальный узел, листОриентированный, направленный граф, орграф (Directed graph, dirgaph) — граф, содержащий упорядоченные пары элементов; узлы связаны только одной связью.
Ориентированный связный граф — граф, который одновременно ориентированный и связный.
Ациклический граф — граф без циклов.
Конечный граф — граф, имеющий конечное количество узлов и связей между ними.
Всемирная паутина — конечный граф, несмотря на огромное количество узлов.
Дерево (Tree) — ациклический (не содержащий циклов) связный граф.
Сверхстройное дерево — дерево с единственным узлом степени больше 2.
Лес (Forest) — граф в виде набора несвязанных деревьев.
Полный граф — граф, в котором любой узел имеют связь хотя бы с одним другим узлом.
Планарный граф — граф, который можно изобразить на плоскости без пересечения связей между узлами. Изоморфен плоскому графу.
Плоский граф — граф, в котором никакие две связи не имеют общих узлов, кроме инцидентного им обеим узла. Связи не пересекают друг друга.
Гиперграф графа — граф, в котором связь может соединять не только два узла, но и любое множество узлов.
В качестве примера гиперграфа можно привести гиперссылку, которая указывает на вебсайт в целом, как на коллекцию узлов (вебстраниц).
Мультиграф — граф, в котором пара узлов имеет более чем одну связь. При этом существуют связи противоположных направлений.
В практике Веба можно встретить ситуации, когда вебстраница содержит гиперссылку, указывающую на другую вебстраницу. В то же время на другой вебстранице существует гиперссылка, указывающая на первую вебстраницу. Другой пример, библиографическая ссылка, которая в сноске содержит обратную ссылку.
Нераделимый граф — связный, непустой, не имеющий точек сочленения граф.
Нормированный граф — ориентированный граф без циклов.
Размеченный граф — граф, узлы и связи которого имеют цифровые или символьные метки. Графическое надписывание меток узлов и связей. Метки образуют два класса: класс меток узлов и класс меток связей.
Соответственно элементы языка HTML разделяют на два класса: класс меток узлов и класс меток гиперссылок.
Простой граф — граф, в котором нет кратных связей и петель.
Тождественный граф — абсолютно несимметричный граф, у которого возможен единственный автоморфизм.
Турнир — ориентированный граф, в котором каждая пара узлов имеет одну связь.
Пример турнира — строка символов (слово, метка). Между символами лишь одно отношение: линейная последовательность.
Единицы измерения графа
Перечисление графов — число неизоморфных графов в заданном классе графов.
Порядок графа(Order) — количество узлов графа Веба.
Размер графа (Size) — количество связей графа Веба.
Степень, валентность узла (Degree, Valency) — количество связей данного узла, инцидентных другим узлам.
Узловое покрытие — пространство узлов графа, в котором каждый узел инцидентен хотя бы одному другому узлу графа.
Применительно для Веба узловое покрытие связано с поиском изолированных узлов.
Вес узла (Node weight) — количественное значение, поставленное в соответствие узлу графа.
Вес узла применяют для ранжирования узлов гипертекста. Например, для установления порядка пунктов меню. Каждый пункт меню связан с узлом (вебстраницей), в метаданных которого указано значение веса.
Окрестность порядка k — список узлов на заданном расстоянии k от указанного узла.
Диаметр дерева (diameter of a tree) — максимальная длина (в связях) кратчайшего пути в дереве между любыми двумя узлами.
Радиус дерева (radius of a tree) — наименьший из эксцентриситетов узлов связного графа.
Высота дерева — наибольшая длина пути от корня графа к самому крайнему листу этого графа.
Одним из способов применения высоты дерева служит измерение вложенности. Например, вложенность (высота дерева) более трёх пунктов меню вызывает сложности в ориентации пользователя.
Длина маршрута — количество связей в маршруте.
Длина пути — количество связей пути. Если задана длина связи, то длина пути будет равна сумме длин связей.
Расстояние между узлами — длина пути орграфа между заданными узлами. Если такого пути не существует, расстояние полагают равным бесконечности.
Полустепень входа орграфа — число входящих в узел связей.
Полустепень выхода орграфа — число выходящих из узла связей.
Спектр графа — значения матрицы смежности с учётом кратных связей.
Число узлового покрытия — размер наименьшего узлового покрытия графа.
Число независимости — размер наибольшего независимого количества узлов графа.
Число паросочетаний — размер наибольшего паросочетания графа.
Число покрытия связями — размер наименьшего покрытия связями графа.
Энергия графа_ — сумма абсолютных величин собственных значений матрицы смежности графа.
Матрица достижимости графа — матрица, содержащая данные о существовании путей между узлами дерева (орграфа).
Матрица инцидентности графа — матрица, содержащая данные об инцидентности узлов и связей графа. Строки содержат список узлов, столбцы — список связей. Ненулевое значение в ячейке матрицы указывает отношение между узлом и связью (инцидентность). В ориентированном графе каждой связи ставят значение «1» в строке начального узла и «-1» в строке конечного узла. Если связи нет, то ячейку либо оставляют пустой (NULL), либо ставят «0».
Матрица смежности графа — матрица, содержащая данные о смежности узлов графа. Квадратная матрица с узлами по строкам и столбцам. Содержит нули по главной диагонали. Ячейка матрицы содержит целочисленное значение о направленности связи.
Операции над графами
Если существуют два или более графов, у которых нет пересечения ни между узлами, ни между связями, то над такими графами возможны следующие операции.
Объединение графов (Union) — граф, объединяющий узлы и связи между узлами объединяемых графов.
Соединение графов (graph join) — граф, в котором все узлы одного графа получают соединение с узлами другого графа.
Произведение графов (Cartesian product) — граф, у которого количество узлов равно декартову произведению узлов начальных графов. Произведение лишь повторяет (дублирует) существующие связи между узлами.
Композиция графов (lexicographical product) — граф, с количеством узлов, равным декартову произведению узлов начальных графов. Композиция образует связи между между всеми узлами.
Дополнение графа — граф над теми же узлами, что и исходный, но узлы связаны только тогда, когда в исходном графе нет отношения.
Пример применения дополнения графа. Пусть существует вебсайт сетью гиперссылок между вебстраницами. Если не все вебстраницы имеют ссылки друг на друга, то всегда можно построить другой вебсайт с такими гиперссылками, которые отсутствуют в начальном вебсайте.
Подграф графа — граф, содержащий подмножество узлов исходного графа и некоторое подмножество инцидентных им связей. По отношению к подграфу исходный граф называют суперграфом.
Порождённый подграф — граф, порождённый подмножеством узлов и связей исходного графа. Содержит не обязательно все узлы графа, но эти узлы имеют такие связи как в исходном графе.
Например если скопировать несколько вебстраниц с сохранением гиперссылок между этими вебстраницами. Получим порождённый граф с некоторыми узлами.
Суперграф графа — граф, содержащий подграф.
Минор графа — граф, который можно получить из исходного графа путём удаления и стягивания связей.
Изоморфизм графов — два графа изоморфные, если существует перестановка узлов, при которой они совпадают. В изоморфных графах существует взаимное и однозначное соответствие между узлами и связями, которое сохраняет смежность и идентичность графа. Графы отличны лишь названиями своих узлов.
Изоморфизм широко распространённая практика Веба. Например, англоязычной Википедии изоморфна русскоязычная Википедия. Каждой вебстранице (узлу) англоязычной соответствует русскоязычная вебстраница (узел). Каждой гиперссылке (связи) между англоязычными вебстраницами (узлами) соответствует подобная гиперссылка между русскоязычными вебстраницами.
Разрез графа — набор связей, удаление которых сделает граф несвязным.
Сечение графа — набор связей, удаление которых разделит граф на два изолированных подграфа.
Узел графа
Узел, вершина, точка графа (Node, Vertex, Point) — объект в пространстве Веба.
База графа — узел графа, из которого достижим любой узел графа.
Корень дерева (Root) — выбранный узел орграфа с нулевой степенью захода, в котором присутствуют только начальные связи и отсутствуют концевые отношения.
_Лист дерева, терминальный узел (Leaf) — узел дерева с единственной связью. Узел, в котором существуют только конечные (входящие) связи и отсутствуют начальные (исходящие) отношения.
Ветвь, ветка (Branch) — узел, в котором присутствуют как начальные, так и конечные связи.
Изолированный узел(Isolated node) — узел, не имеющий связей ни с одним другим узлом.
Формально изолированный узел расположен вне пространства графа. Веб, как семантическая сеть, требует связности, чтобы все узлы имели хотя бы одну связь с другими узлами. Поиск изолированных узлов и привязка их к пространству существующих узлов — одна из проблем архитектуры Веба.
Независимые узлы — попарно независимые узлы, без связей между собой.
Окружение узла — список узлов, смежных с указанным.
Центральный узел — узел, на котором эксцентриситет узлов радиуса дерева достигает своего минимума.
Взвешенный узел — узел графа, имеющий значение веса.
Связь между узлами
Связь, дуга, ребро (Edge, Line) — ориентированное отношение между узлами графа Веба.
Связность графа — существование пути между любыми узлами графа.
Связный граф — граф, в котором связанны все узлы.
Сильная связность графа — между узлами существуют прямая и обратная связь (гиперссылки); путь из исходного узла в другой, а также из другого в исходный.
Инцидентность связи — взаимоотношение между узлами и связью между ними. Связь всегда сосуществует с узлами, без узлов нет связи между этими узлами. Не существует связи между связями или узла между узлами.
Упорядоченная пара элементов — связь между начальным и конечным узлами.
Начальный узел связи — узел ориентированного графа в начале связи.
Конечный узел связи — узел ориентированного графа в конце связи.
Например, гиперссылка в тексте это упорядоченная пара элементов графа, в которой:
- текущая вебстраница, на которой расположена гиперссылка, это начальный узел;
- вебстраница, на которую указывает гиперссылка (URL), это конечный узел.
Во Всемирной паутине объекты связаны семантическими отношениями. Семантические отношения задают направленность отношений между узлами графа Веба.
Упорядоченный граф — граф, в котором связи, выходящие из узла, однозначно размечены упорядоченными маркерами (например, цифрами).
Петля узла — связь узла с самим собой.
На вебсайтах можно встретить гиперссылки, которые указывают на текущую вебстраницу. Это бессмысленно и следует находить и удалять подобные гиперссылки.
Смежность — отношение либо между узлами, либо между связями.
Смежные, соседние узлы (Neighbours, Adjacent) — узлы, инцидентные одной связи; связанные между собой.
Смежные связи (Аdjacent edges) — все связи инцидентные одному узлу.
Смешанный граф — граф, который содержит как ориентированные, так и неориентированные связи.
Паросочетание связей — набор попарно несмежных связей.
Совершенное паросочетание — паросочетание, содержащее все узлы графа.
Мост — связь, удаление которой увеличивает количество компонент связности графа.
Маршрут — конечная последовательность узлов, в которой каждый узел (кроме последнего) имеет связь со следующим в последовательности узлов.
Цепь — маршрут связей без повторения узлов.
Путь, ориентированный маршрут — конечная последовательность узлов и связей, в которой каждый элемент инцидентен предыдущему и последующему.
Например, путь применяют для отображения навигации пользователя по вебстраницам одного вебсайта. Строка узлов показывает последовательность переходов от корня до текущей вебстраницы.
Простой путь — путь, все узлы которого различные попарно. Простой путь дважды не проходит через один узел.
Путь в орграфе — последовательность узлов, для которых существуют связи. Для этого пути существует начальный узел, промежуточные узлы и конечный узел.
Цикл, контур — замкнутая цепь.
Простой цикл — простой путь, у которого один и тот же узел служит началом и концом пути.
Семантические отношения
Всемирная паутина представляет собой семантическое пространство с иерархической структурой отношений между узлами. В качестве примера семантики можно привести отношение агрегации и композиции «целое-часть» между узлами.
Целое — объект состоящий из частей.
Часть — составляющая некоторого объекта, представляющего целостность.
И целое, и часть это объекты. И, как любые объекты, они узлы графа.
Класс объектов — объекты, имеющие общие свойства.
Подкласс объектов — объекты, имеющие дополнительные свойство относительно своего класса.
Экземпляр класса — объект с конкретными значениями свойств.