2015-02-27
631
Пример 1. Точки могут означать биологические виды организмов в экосистеме. Тогда рёбра могут показывать трофические связи между видами, т.е. определять пути передачи энергии от одного вида к другому (кто кого ест). В этом случае рёбра должны иметь вид однонаправленных стрелок, поскольку энергия обычно передаётся в одном направлении. Граф с рёбрами в виде стрелок называется ориентированным.
Пример 2. Точки могут означать нервные клетки, а рёбра – нервные волокна, их соединяющие. В этом случае стрелки могут быть противоположно направленными (↔), поскольку электрические импульсы могут двигаться между двумя клетками в противоположных направлениях по разным волокнам.
Из примеров понятно, что с помощью графов можно описывать любые множества систем, взаимодействующих определённым образом. При этом теория графов позволяет рассчитать число возможных вариантов взаимодействий (число возможных графов) при заданном количестве вершин. Например, если количество вершин n = 1, то количество графов Pg = 1; при двух вершинах (n = 2, Pg= 4) мы получим следующие 4 варианта графов:
|
|
|
1) 2) 3) 4)
Общая формула имеет вид: Pg = 2n(n-1). Можно заметить, что количество графов с ростом n растёт гораздо быстрее, даже чем n !, что показано в табл.6.1. В этой же таблице для сравнения приведены хорошо известные быстрорастущие функции: Р = n2 и Р = n3.
Таблица 6.1
Зависимость вариантов взаимодействий от числа
взаимодействующих элементов «n»
| Количество элементов (вершин) | n | ||||||
| Количество перестановок Pn | n! | ||||||
| Количество графов Pg | 2n(n-1) | ||||||
| Кубическая парабола | n3 | ||||||
| Парабола | n2 |
Одним из первых учёных, кто обратил внимание на комбинаторную природу сложности материальных и особенно живых систем, был английский биолог и специалист в области кибернетики У.Р. Эшби [46]. В одной из своих статей [44] он приводит следующий пример. В ящике, разделённом на 400 ячеек (20х20), в каждую ячейку вмонтирована лампочка. Требуется рассчитать, сколько вариантов зажигания лампочек может быть в данной системе? Эшби определил искомую величину как 1010120и отметил, что человеческий разум не в состоянии оценить масштаб таких чисел. Для того чтобы всё-таки попытаться это сделать, он предложил рассмотреть ничтожно малую долю от указанного числа. А именно, взять долю, какую составляет один атом от всей Вселенной, т.е. данное число надо разделить на 1073. Для упрощения расчётов Эшби делит 1010120на 10100 и приводит результат 1010118, из чего делает справедливый вывод, что даже такая малая доля числа 1010120, как один атом от миллиардов и миллиардов вселенных, остаётся величиной не подвластной оценке нашего разума.
|
|
|
Забавность описанной ситуации состоит ещё в том, что результат 1010118является ошибочным. В действительности вместо показателя степени 118 должен быть показатель 119, 99…9, т.е. число 1010120после
