Критическая масса. Как одни явления порождают другие

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

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

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

Рис. 15.3. Схема лондонского метрополитена в виде типичного реляционного графа. Положения станций (вершины) и расстояния между ними лишь приблизительно соответствуют истинным значениям. Серая линия в нижней части рисунка условно обозначает русло Темзы.