Граф

Материал из Letopisi.Ru — «Время вернуться домой»
Перейти к: навигация, поиск


Логотип Википедии

В Википедии тоже есть статья по теме
«Граф_(математика)».

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

Граф или неориентированный граф G — это упорядоченная пара G := (V, E), для которой выполнены следующие условия:

  • V это непустое множество вершин или узлов,
  • E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

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


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

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

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

Примеры структуры графов


На следующем рисунке представлены 2 сообщества, которые связаны между собой мостом 5 - 10

Характеристики графа

  • Модульность или блочность - насколько внутри графа просматривается структура сообществ? В случайном графе модульность Q=0. В неслучайных графах, где прослеживаются сообщества Q от 0.3 до 0.7


Роли, которые мы можем выделить для узлов графа:

  • Большие рыбы - узлы, с которыми связано множество других узлов
  • Мосты или хабы - узлы, которые связывают разные сообщества
  • одиночки - узлы, связанные с 1-2-мя узлами. Хуже жизнь только у сирот, которые не связаны ни с кем.

Литература

  • Barabási,, A. L. (2002). Linked: The new science of networks. Cambridge, MA: Perseus Publishing, 229 p.
  • Barabási, Albert-László. 2003. "Linked: How Everything is Connected to Everything Else and What It Means for Business, Science, and Everyday Life." New York: Plume.
  • Milgram St. (1967) "The Small World Problem". Psychology Today, 1(1), May 1967. pp 60 – 67
  • 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
Персональные инструменты
Инструменты
Акция ВЫХОДИ В ИНТЕРНЕТ 2015

организаторы проекта
PH International
www.Iteach.ru
Корпорация Intel
Компания ТрансТелеКом