Читать «Критическая масса, как одни явления порождают другие» онлайн - страница 312

Правила построения графа легко сформулировать для случая, когда вершины соответствуют городам, а ребра — соединяющим их дорогам. Если

Рис. 15.2. Типичный граф (а) для некоторой сети связей представляет собой набор точек (вершин), соединенных линиями (ребрами). На рисунке б представлена лишь очень небольшая часть обширного графа, описывающего множество киноактеров, которые играли в фильмах с участием Кевина Бэкона, в фильмах с участием его партнеров и т.д. Список соответствующих фильмов читатель может найти в примечаниях.

расстояния и направления ребер правильно отражают протяженность и направленность дорог, то мы получаем простейшую географическую карту. Для графа, описывающего степень прямого взаимодействия киноактеров (рис. 15.2, б), правила построения определить гораздо сложнее. При построении такого графа непонятно, какую степень близости следует приписывать соседним вершинам графа (в нашем конкретном случае, например, паре актеров Кевин Бэкон — Эдди Альберт), не говоря уже о том, что в описываемой структуре вообще нет никакой направленности. Должен ли Джек Николсон (обладатель ЧБ = 1 за участие в фильме A Few Good Men, 1992) располагаться на том же расстоянии, что и Альберт? Проще всего расположить актеров с одинаковым значением ЧБ на одинаковом расстоянии от центра и не придавать значения направленности ребер, однако мы быстро обнаружим, что это не работает, потому что мы не сможем соединить двух актеров ребром заданной длины, так как они уже разнесены слишком далеко другими связями. Впрочем, напомню читателю, что ничто не обязывает нас рисовать граф на плоскости, так что мы вполне можем построить гораздо более удобный граф в трехмерном пространстве, где он будет напоминать дерево или строительную конструкцию. Более того, поскольку математикам, вообще говоря, безразлично, в пространстве скольких измерений они работают, то что, собственно, мешает нам построить очень красивую десятимерную веб-страницу для любителей кино и чисел Бэкона?

На самом деле в теории графов действительно не важно, каким образом будет изображена диаграмма связей различных актеров, так как при построении необходимо лишь строго следить, чтобы ребра графа точно отражали совместные съемки актеров в одном и том же фильме. Вид графа для математиков не очень важен, поскольку его важнейшие особенности полностью описываются так называемой топологией системы взаимодействий. Абсолютно разные по внешнему виду на рисунке графы могут оказаться топологически идентичными, т. е. математически одинаковыми. В некоторых случаях длины и направления ребер не играют никакой роли, поскольку они отражают только наличие связей между своими вершинами (такие графы называются реляционными). Кроме этого, существуют и так называемые пространственные графы, в которых положение вершин, а также направленность и длина ребер соответствуют реальным параметрам. Разумеется, очень часто мы сталкиваемся со схемами городов, которые, строго говоря, не являются пространственными графами. В качестве примера можно привести схему линий лондонского метрополитена (рис. 15.3), которая позднее стала образцом для многочисленных подражаний. Этот чертеж, созданный Гарри Беком в 1931 году, представляет собой отличный пример реляционного графа, но одновременно содержит и некоторые полезные признаки пространственного графа. Положения станций на схеме лишь приблизительно соответствуют их настоящему географическому расположению, расстояния между станциями приведены примерно, а направления линий метро указаны весьма неточно. Но такая схема очень полезна, поскольку позволяет легко ориентироваться в сложной системе и находить нужные пункты пересадок.