9.4. Графы

9.4. Графы

Графом называется множество вершин, произвольным образом соединенных друг с другом. (Дерево — частный случай графа.) Не будем слишком углубляться в эту тему, поскольку теория и терминология весьма сложны. Очень скоро мы перешли бы от информатики в область чистой математики.

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

Под графом мы обычно понимаем неориентированный граф. Попросту говоря, в нем не проставлены стрелки на соединительных линиях; две вершины либо соединены, либо нет. Между тем в ориентированном графе (орграфе) могут быть «улицы с односторонним движением»; из того, что вершина x соединена с вершиной у, не следует, что верно и обратное. Наконец, во взвешенном графе ребрам можно назначать веса. Например, вес может выражать «расстояние» между вершинами. Мы ограничимся только этими основными видами графов; интересующегося читателя отсылаем к многочисленным учебникам информатики и математики.

В Ruby, как и во многих других языках, граф можно представить разными способами, например в виде настоящей сети взаимосвязанных объектов или в виде матрицы, в которой хранятся ребра графа. Мы рассмотрим оба способа и на примерах покажем, как можно манипулировать графами.

Данный текст является ознакомительным фрагментом.



Поделитесь на страничке

Похожие главы из других книг:

ЛЕКЦИЯ № 10. Графы

Из книги автора

ЛЕКЦИЯ № 10. Графы 1. Понятие графа. Способы представления графа Граф – пара G = (V,E), где V – множество объектов произвольной природы, называемых вершинами, а Е – семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство Е могут содержать


Глава 13 Сведение задач к подзадачам. И/ИЛИ-Графы

Из книги автора

Глава 13 Сведение задач к подзадачам. И/ИЛИ-Графы Представление в виде И/ИЛИ-графов наиболее хорошо приспособлено для задач, которые естественным образом разбиваются на взаимно независимые подзадачи. Примерами таких задач могут служить поиск маршрута, символическое


3. ТРЕБОВАНИЯ К ПРОГРАММНЫМ ДОКУМЕНТАМ. СОДЕРЖАЩИМ ТЕКСТ, РАЗБИТЫЙ НА ГРАФЫ

Из книги автора

3. ТРЕБОВАНИЯ К ПРОГРАММНЫМ ДОКУМЕНТАМ. СОДЕРЖАЩИМ ТЕКСТ, РАЗБИТЫЙ НА ГРАФЫ 3.1. Программные документы, содержащие текст, разбитый на графы, при необходимости разделяют на разделы и подразделы, которые не нумеруют. Допускается линии, разграничивающие строки и графы, не