Большая Советская Энциклопедия (ГР)

  Одной из первых работ по Г. т. можно считать работу Л. Эйлера (1736), относящуюся к решению головоломок и математических развлекательных задач. Первые глубокие результаты были получены в 1-й половине 20 в. в связи с решением задач построения электрических цепей и подсчёта химических веществ с различными типами молекулярных соединений. Однако широкое развитие Г. т. получила лишь с 50-х гг. в связи со становлением кибернетики и развитием вычислительной техники, когда Г. т. существенно обогатилась и новым материалом, и новыми подходами и когда началось систематическое изучение графов с разных точек зрения (структурной, информационной и т. д.). Именно в это время формулировались проблематика и методы Г. т. Г. т. находит применение в теории программирования и при построении вычислительных машин, в изучении физических, химических и технологических процессов, в решении задач планирования, в лингвистических и социологических исследованиях и т. д. Г. т. имеет тесные связи как с классическими, так и с новыми разделами математики; это — топология, алгебра, комбинаторный анализ, теория чисел, теория минимизации булевских функций. Г. т. включает большое число разнообразных задач. Одни из них группируются в отдельные направления, другие стоят более изолированно. Среди сложившихся разделов Г. т. следует отметить задачи, относящиеся к анализу графов, определению различных характеристик их строения, например выяснение связности графа: можно ли из любой вершины попасть в любую; подсчёт графов или их частей, обладающих заданными свойствами, например подсчёт количества деревьев с заданным числом рёбер (дерево — неориентированный граф без циклов); решение транспортных задач, связанных с перевозками грузов по сети. Решен ряд задач по синтезу графов с заданными свойствами, например построение графа с заданными степенями вершин (степень вершины — число выходящих из неё рёбер). Имеет прикладное и теоретическое значение задача о выяснении возможности расположения графа на плоскости без самопересечений его рёбер (т. е. является ли данный граф плоским), задача о разбиении графа на минимальное число плоских графов. Для некоторых задач Г. т. (выше были приведены далеко не все) были разработаны методы их решения. Среди них: метод Пойя перечисления и подсчёта графов с заданными свойствами, теорема и алгоритм Форда — Фалкерсона для решения транспортной задачи, «венгерский» алгоритм решения задачи о назначениях и т. д. Почти все задачи теории конечных графов (практически интересны именно графы с конечным числом вершин) могут быть решены путём перебора большого числа вариантов (т. н. полный перебор), поэтому для них требуется построение эффективных алгоритмов и использование быстродействующих вычислительных машин. Такими задачами являются: задача о раскраске вершин графа, задача об определении идентичности двух графов, коммивояжёра задача . Есть задачи, требующие принципиального ответа, например задача о раскраске плоских графов, задача о восстановлении графа по его подграфам.

  Лит.: Берж К., Теория графов и её применения, пер. с франц., М., 1962; Оре О., Графы и их применение, пер. с англ., М., 1965; Зыков А. А., Теория конечных графов. I, Новосибирск, 1969.

Рис. 2 к ст. Графов теория.

Рис. 1 к ст. Графов теория.

Графология

Графоло'гия (от графо... и ...логия ), учение о почерке, исследование его с точки зрения отражающихся в нём свойств и психических состояний пишущего. Почерк — разновидность выразительных движений , особенность которых состоит в том, что они являются «саморегистрирующимися» и поэтому всегда доступными изучению. Взгляд на почерк как определенное выражение человека восходит к античности (Теофраст и др.), первые опыты Г. — к эпохе Возрождения (сочинения итальянского учёного К. Бальди, 1622). В качестве специальной дисциплины Г. возникает во 2-й половине 19 в. во Франции [Ж. Мишон, введший самый термин «Г.» (1872), Крепьё-Жамен]; почерк рассматривался при этом как система устойчивых графических признаков, каждому из которых соответствует определенное свойство характера. С конца 19 в. складывается немецкая школа Г. (Г. Мейер, В. Прейер и особенно Л. Клагес ); в противовес изолированному толкованию отдельных признаков развивается представление о двузначности и даже многозначности каждого отдельного графического знака, конкретное значение которого определяется лишь на уровне анализа почерка как «целостной формы» (Клагес). Данные Г. применяются для исследования индивидуальных особенностей человека в психологии, а также в медицине и криминалистике в качестве средства психологической и физиологической диагностики наряду с др. методами, например тестами .

  Ю. Н. Попов.