Граф
Материал из Letopisi.Ru — «Время вернуться домой»
(Различия между версиями)
(→Характеристики графа) |
|||
| (не показаны 11 промежуточных версий 1 участника) | |||
| Строка 2: | Строка 2: | ||
В математической теории графов и информатике граф — это совокупность объектов со связями между ними. | В математической теории графов и информатике граф — это совокупность объектов со связями между ними. | ||
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. | Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. | ||
| + | |||
| + | '''Граф''' или '''неориентированный граф''' G — это упорядоченная пара G := (V, E), для которой выполнены следующие условия: | ||
| + | :* V это непустое множество вершин или узлов, | ||
| + | :* E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых '''рёбрами'''. | ||
Простейший [[граф]] | Простейший [[граф]] | ||
| Строка 19: | Строка 23: | ||
Теория графов получила широкое развитие в 50-е годы XX века в связи со становлением кибернетики и развитием вычислительной техники, когда началось систематическое изучение графов и их применение в теории программирования и при построении вычислительных машин. Для представления графов было разработано множество программных средств. Одним из наиболее популярных остается разработанный специалистами лаборатории AT&T пакет утилит по автоматической визуализации графов [[Graphviz]]. | Теория графов получила широкое развитие в 50-е годы XX века в связи со становлением кибернетики и развитием вычислительной техники, когда началось систематическое изучение графов и их применение в теории программирования и при построении вычислительных машин. Для представления графов было разработано множество программных средств. Одним из наиболее популярных остается разработанный специалистами лаборатории AT&T пакет утилит по автоматической визуализации графов [[Graphviz]]. | ||
| + | === Примеры структуры графов === | ||
| − | + | <graphviz> | |
| + | digraph W { | ||
| + | layout="fdp" ; | ||
| + | // rankdir=LR ; | ||
| + | 1 -> 2 ; | ||
| + | 2 -> 3 ; | ||
| + | 3 -> 1 ; | ||
| + | } | ||
| + | </graphviz> | ||
| + | |||
| + | |||
| + | |||
| + | <graphviz> | ||
| + | digraph W1 { | ||
| + | layout="fdp" ; | ||
| + | // rankdir=LR ; | ||
| + | 1 -> 2 ; | ||
| + | 2 -> 3 ; | ||
| + | 3 -> 4 ; | ||
| + | 4 -> 5 ; | ||
| + | 5 -> 1 | ||
| + | } | ||
| + | </graphviz> | ||
| + | |||
| + | <graphviz> | ||
| + | digraph W2 { | ||
| + | layout="fdp" ; | ||
| + | // rankdir=LR ; | ||
| + | 1 -> 2 ; | ||
| + | 2 -> 3 ; | ||
| + | 3 -> 4 ; | ||
| + | 4 -> 5 ; | ||
| + | 5 -> 1 ; | ||
| + | 1 -> 4 ; | ||
| + | 2 -> 5 ; | ||
| + | 5 -> 3 ; | ||
| + | } | ||
| + | </graphviz> | ||
| + | |||
| + | На следующем рисунке представлены 2 сообщества, которые связаны между собой мостом '''5 - 10''' | ||
| + | <graphviz> | ||
| + | digraph W3 { | ||
| + | layout="fdp" ; | ||
| + | // rankdir=LR ; | ||
| + | 1 -> 2 ; | ||
| + | 2 -> 3 ; | ||
| + | 3 -> 4 ; | ||
| + | 4 -> 5 ; | ||
| + | 5 -> 1 ; | ||
| + | 1 -> 4 ; | ||
| + | 2 -> 5 ; | ||
| + | 6 -> 7 ; | ||
| + | 6 -> 8 ; | ||
| + | 8 -> 9 ; | ||
| + | 9 -> 10 ; | ||
| + | 10 -> 7; | ||
| + | 5 -> 10 ; | ||
| + | } | ||
| + | </graphviz> | ||
| + | |||
| + | === Характеристики графа === | ||
| + | * Модульность или блочность - насколько внутри графа просматривается структура сообществ? В случайном графе модульность 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,, 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. | * 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. | ||
Текущая версия на 12:30, 16 января 2012
В математической теории графов и информатике граф — это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Граф или неориентированный граф 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
