Граф

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

Простейший граф

При графа могут быть представлены самые разные структуры:

• множество городов (вершины графа) и соединяющие их дороги (ребра графа);
• элементы электрической схемы (вершина) и соединяющие их провода (ребра);
• веб-страницы (вершины) и соединяющие их ссылки (ребра).

Теория графов получила широкое развитие в 50-е годы XX века в связи со становлением кибернетики и развитием вычислительной техники, когда началось систематическое изучение графов и их применение в теории программирования и при построении вычислительных машин. Для представления графов было разработано множество программных средств. Одним из наиболее популярных остается разработанный специалистами лаборатории AT&T пакет утилит по автоматической визуализации графов Graphviz . Этот пакет позволяет записывать связи между

• Barabasi, A. L. (2002). Linked: The new science of networks. Cambridge, MA: Perseus Publishing.
• Watts D. 2003, Six Degrees: The Science of a Connected Age, Norton, W. W. & Company, 448p.
• Gilbert N., Troitzsch K. Simulation for the social scientist. McGraw-Hill International, 2005, ISBN 0335216005, 9780335216000, pp. 295