Большая Советская энциклопедия

    раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории — граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих некоторые (а может быть, и все) пары вершин. При этом пары вершин могут соединяться несколькими ребрами. Примеры графов: множество городов (вершины графа), например Московской области, и соединяющие их дороги (ребра графа); элементы электрической схемы и провода, соединяющие их. На рис. 1 изображен граф, вершинами которого являются станции городского метрополитена, а ребрами — пути, соединяющие соседние станции (одна из задач: указать какой-либо маршрут от станции А к станции В).Граф называется ориентированным, если на ребрах задана ориентация, т. е. указан порядок прохождения вершин. Наконец, в Г. т. изучаются графы, у которых ребрам приписаны какие-либо веса (или символы), а также графы, в которых выделены особые вершины, называются полюсами. Примеры: диаграмма состояний автомата, сеть ж.-д. путей с указанием на дугах их длин или пропускных способностей. На рис. 2 приведена схема автомобильных дорог между Москвой и Таллином; надо, например, выбрать маршрут минимальной общей длины пути из Москвы в Таллин (эти два города — полюсы сети); сравнение двух маршрутов Москва — Ленинград — Таллин и Москва — Витебск — Рига — Таллин показывает, что путь через Ленинград короче (1049 км).

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

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

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

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

  1. Источник: Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.



  2. Большой энциклопедический словарь

    ГРАФОВ ТЕОРИЯ - раздел математики, особенность которого - геометрический подход к изучению объектов. Основное понятие теории - граф - задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа - схема метрополитена: множество станций (вершины графа) и соединяющих их линий (ребра графа).

  3. Источник: Большой Энциклопедический словарь. 2000.



  4. Химическая энциклопедия

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

    Некоторые основные понятия. Граф-совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 1,л). Если на графе линии ориентированы (т. е. стрелками показано направление связи вершин), они наз. дугами, или ветвями; если неориентированы,-ребрами. Соотв. граф, содержащий только дуги, наз. ориентированным, или орграфом; только ребра-неориентированным; дуги и ребра-смешанным. Граф, имеющий кратные ребра, наз. мультиграфом; граф, содержащий только ребра, принадлежащие двум его непересекающимся подмножествам (частям),-двудольным; дуги (ребра) и (или) вершины, к-рым отвечают определенные веса или числовые значения к.-л. параметров,-взвешенным. Путь в графе-чередующаяся последовательность вершин и дуг, в к-рой ни одна из вершин не повторяется (напр., a, b на рис. 1,a); контур-замкнутый путь, в к-ром первая и последняя вершины совпадают (напр.,f, h); петля-дуга (ребро), к-рая начинается и кончается в одной и той же вершине. Цепь графа-последовательность ребер, в к-рой ни одна из вершин не повторяется (напр., с, d, e); цикл-замкнутая цепь, в к-рой ее начальная и конечная вершины совпадают. Граф наз. связным, если любая пара его вершин соединена цепью или путем; в противоположном случае граф наз. несвязным.

    Дерево-связный неориентированный граф, не содержащий циклов или контуров (рис. 1,б). Остовпый подграф нек-рого графа-его подмножество, содержащее все вершины и лишь определенные ребра. Остовное дерево нек-рого графа-его остовный подграф, представляющий собой дерево. Графы наз. изоморфными, если существует взаимно однозначное соответствие между совокупностями их вершин и ребер (дуг).

    Для решения задач Г. т. и ее приложений графы представляют с помощью матриц (смежности, инцидентности, двустрочных и др.), а также спец. числовых характеристик. Напр., в матрице смежности (рис. 1,в) строки и столбцы отвечают номерам вершин графа, а ее элементы принимают значения 0 и 1 (соотв. отсутствие и наличие дуги между данной парой вершин); в матрице инцидентности (рис. 1 )строки отвечают номерам вершин, столбцы-номерам дуг, а элементы принимают значения 0, + 1 и - 1 (соотв. отсутствие, наличие дуги, входящей в вершину и выходящей из нее). наиб. употребительные числовые характеристики: число вершин ( т), число дуг или ребер (n), цикломатич. число, или ранг графа ( п Ч т + k, где k- число связных подграфов в несвязном графе; напр., для графа на рис. 1,б ранг будет: 10-6+ 1 =5).

    Применение Г. т. базируется на построении и анализе разл. классов химических и химико-технологических графов, к-рые наз. также топология, моделями, т. е. моделями, учитывающими только характер связи вершин. Дуги (ребра) и вершины этих графов отображают хим. и хим.-технол. понятия, явления, процессы или объекты и соответственно качеств. и количеств. взаимосвязи либо определенные отношения между ними.

    1120-23.jpg

    Рис. 1. Иллюстрация некоторых основных понятий: а-смешанный граф; б-осговное дерево (сплошные дуги a, h, d, f, h) и нек-рый подграф (пунктирные дуги с, с, д, k, I) орграфа; в, г-матрицы соотв. смежности и инцидентности орграфа.

    Теоретические задачи. Хим. графы дают возможность прогнозировать хим. превращения, пояснять сущность и систематизировать нек-рые осн. понятия химии: структуру, конфигурацию, конформации, квантовомех. и статистико-мех. взаимодействия молекул, изомерию и др. К хим. графам относятся молекулярные, двудольные и сигнальные графы кинетич. ур-ний р-ций.

    Молекулярные графы, применяемые в стереохимии и структурной топологии, химии кластеров, полимеров и др., представляют собой неориентированные графы, отображающие строение молекул (рис. 2). Вершины и ребра этих графов отвечают соотв. атомам и хим. связям между ними.

    1120-24.jpg

    Рис. 2. Молекулярные графы и деревья: а, б - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).

    В стереохимии орг. в-в наиб. часто используют мол. деревья -остовные деревья мол. графов, к-рые содержат только все вершины, соответствующие атомам С (рис. 2, а и б). Составление наборов мол. деревьев и установление их изоморфизма позволяют определять мол. структуры и находить полное число изомеров алканов, алкенов и алкинов (рис. 2, в).

    Мол. графы дают возможность сводить задачи, связанные с кодированием, номенклатурой и структурными особенностями (разветвлепность, цикличность и т. п.) молекул разл. соед., к анализу и сопоставлению чисто мат. признаков и св-в мол. графов и их деревьев, а также соответствующих им матриц. Для выявления количеств. корреляций между строением молекул и физ.-хим. (в т. ч. фармакологическими) св-вами соед. разработано более 20 т. наз. топологич. индексов молекул (Винера, Балабана, Хосойи, Плата, Рандича и др.), к-рые определяют с помощью матриц и числовых характеристик мол. деревьев. Напр., индекс Винера 3 + m)/6,> где т- число вершин, отвечающих атомам С, коррелирует с мол. объемами и рефракциями, энтальпиями образования, вязкостью, поверхностным натяжением, хроматографич. константами соед., октановыми числами углеводородов и даже физиол. активностью лек. препаратов.

    Важными параметрами мол. графов, используемыми для определения таутомерных форм данного в-ва и их реакционной способности, а также при классификации аминокислот, нуклеиновых к-т, углеводов и др. сложных прир. соединений, являются спедняя 1120-25.jpg и полная (Н)информац. емкости. Параметр 1120-26.jpg вычисляется по ф-ле энтропии информации Шеннона:, где t-> вероятность принадлежности вершин 1120-27.jpg m графа i-тому виду, или классу эквивалентности, k; i =1120-28.jpg, Параметр 1120-29.jpg1120-30.jpg (см. также Энтропия). Изучение мол. структур типа неорг. кластеров или лент Мёбиуса сводится к установлению изоморфизма соответствующих мол. графов путем их укладки (вложения) в сложные многогранники (напр., полиэдры в случае кластеров) или спец. многомерные пов-сти (напр., римановые). Анализ мол. графов полимеров, вершины к-рых отвечают мономерным звеньям, а ребра-хим. связям между ними, позволяет объяснить, напр., эффекты исключенного объема, приводящие к качеств. изменениям прогнозируемых св-в полимеров.

    1120-31.jpg

    Рис. 3. Графы реакций: а-двудольный; б-сигнальный ур-ний кинетики; r1, г 2 -р-ции; а 16 -реагенты; k-константы скорости р-цнй; s-комплексния переменная преобразования Лапласа>.

    С применением Г. т. и принципов искусственного интеллекта разработано программное обеспечение информационно-поисковых систем в химии, а также автоматизиров. систем идентификации мол. структур и рационального планирования органич. синтеза. Для практич. реализации на ЭВМ операций выбора рациональных путей хим. превращений на основе ретросинтетич. (см. Ретросинтетический анализ )и синтонного принципов используют многоуровневые разветвленные графы поиска вариантов решений, вершины к-рых соответствуют мол. графам реагентов и продуктов, а дуги изображают превращения в-в.

    1120-32.jpg

    Рис. 4. Одноконтурная химико-технологическая система и соответствующие графы: а-структурная схема; б, в-материальные потоковые графы соотв. по общим массовым расходам и расходу компонента А; г- тепловой потоковый граф; д-фрагмент системы ур-ний (f1 - f6) материального баланса, полученной из анализа графов на рис. 4, б и в; е-двудольный информационный орграф; ж-информационный граф, I-смеситель; II-реактор; III-ректификационная колонна; IV-холодильник; I1-I8 -технол. потоки; q-массовый расход; H-энтальпия потока; i. s и i*, s*- соотв. реальные и фиктивные источники и стоки материальных и тепловых потоков; с-концентрация реагента; V-объем реактора>.

    Матричные представления мол. графов разл. соединений эквивалентны (после преобразования соответствующих элементов матриц) матричным методам квантовой химии. Поэтому Г. т. применяют при выполнении сложных квантово-хим. расчетов: для определения числа, св-в и энергий мол. орбиталей, напр. в комплексных соед., прогнозирования реакционной способности сопряженных альтернантньгх и неальтернантных полиенов, выявления ароматич. и антиароматич. св-в в-в и др.

    Для изучения в хим. физике возмущений в системах, состоящих из большого числа частиц, используют т. наз. диаграммы Фейнмана-графы, вершины к-рых отвечают элементарным взаимодействиям физ. частиц, ребра-их путям после столкновений. В частности, эти графы позволяют исследовать механизмы колебательных р-ций и определять устойчивость реакционных систем.

    Для выбора рациональных путей превращения молекул реагентов при заданном множестве известных взаимод. используют двудольные графы р-ций (вершины соответствуют молекулам и этим р-циям, дуги-взаимод. молекул в р-ции; рис. 3,a). Такие графы позволяют разрабатывать диалоговые алгоритмы выбора оптим. путей хим. превращений, для к-рых требуется наим. число промежуточных р-ций, миним. число реагентов из перечня допустимых или достигается наиб. выход продуктов.

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

    Прикладные задачи. Для решения многомерных задач анализа и оптимизации химико-технол. систем (ХТС) используют след. химико-технол. графы (рис. 4): потоковые, информационно-потоковые, сигнальные и графы надежности. К потоковым графам, представляющим собой взвешенные орграфы, относятся параметрические, материальные по общим массовым расходам физ. потоков и массовым расходам нек-рых хим. компонентов либо элементов, а также тепловые графы. Перечисленные графы соответствуют физ.-хим. превращениям в-в и энергии в данной ХТС.

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

    Материальные потоковые графы отображают изменения расходов в-в в ХТС. Вершины графов отвечают аппаратам, в к-рых трансформируются общие массовые расходы физ. потоков и массовые расходы нек-рых хим. компонентов или элементов, а также источникам и стокам в-в потоков либо данных компонентов; соотв. дуги графов отвечают физ. потокам или физ. и фиктивным (хим. превращения в-в в аппаратах) источникам и стокам к.-л. компонентов, а веса дуг равны массовым расходам обоих типов. Тепловые потоковые графы отображают балансы теплоты в ХТС; вершины графов соответствуют аппаратам, в к-рых изменяются расходы теплоты физ. потоков, и, кроме того, источникам и стокам тепловой энергии системы; дуги отвечают физ. и фиктивным (физ.-хим. превращения энергии в аппаратах) тепловым потокам, а веса дуг равны энтальпиям потоков. Материальные и тепловые графы используют для составления программ автоматизиров. разработки алгоритмов решения систем ур-ний материальных и тепловых балансов сложных ХТС.

    Информационно-пстоковые графы отображают логико-информац. структуру систем ур-ний мат. моделей ХТС; применяются для составления оптим. алгоритмов расчета этих систем. Двудольный информац. граф (рис. 4, е)неориентированный или ориентированный граф, вершины к-рого отвечают соотв. ур-ниям l >-f6 и переменным 1 - V,> а ветви отображают их взаимосвязь. Информац. граф (рис. 4, ж) - орграф, изображающий порядок решения ур-ний; вершины графа отвечают этим ур-ниям, источникам и приемникам информации ХТС, а ветви-информац. переменным.

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

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

    Для создания комплексов программ автоматизир. синтеза оптим. высоконадежных произ-в (в т. ч. ресурсосберегающих) наряду с принципами искусств. интеллекта применяют ориентированные семантические, или смысловые, графы вариантов решений ХТС. Эти графы, к-рые в частном случае являются деревьями, изображают процедуры генерации множества рациональных альтернативных схем ХТС (напр., 14 возможных при разделении ректификацией пятиком'понентной смеси целевых продуктов) и процедуры упорядоченного выбора среди них схемы, оптимальной по нек-рому критерию эффективности системы (см. Оптимизация).

    Г. т. используют также для разработки алгоритмов оптимизации временных графиков функционирования оборудования многоассортиментных гибких произ-в, алгоритмов оптим. размещения аппаратуры и трассировки трубопроводных систем, алгоритмов оптим. управления химико-технол. процессами и произ-вами, при сетевом планировании их работы и т. д.

    Лит.. Зыков А. А., Теория конечных графов, [в. 1], Новосиб., 1969; Яцимирский К. Б., Применение теории графов в химии, Киев, 1973; Кафаров В. В., Перов В. Л., Мешалкин В. П., Принципы математического моделирования химико-технологических систем, М., 1974; Кристофидес Н., Теория графов. Алгоритмический подход, пер. с англ., М., 1978; Кафаров В. В., Перов В. Л., Мешал кин В. П., Математические основы автоматизированного проектирования химических производств, М., 1979; Химические приложения топологии и теории графов, под ред. Р. Кинга, пер. с англ., М., 1987; Chemical Applications of Graph Theory, Balaban A.T. (Ed.), N.Y.-L., 1976. В. В. Кафаров, В. П. Мешалкин.

  5. Источник: Химическая энциклопедия



  6. Энциклопедический словарь

    гра́фов тео́рия

    раздел математики, особенность которого — геометрический подход к изучению объектов. Основное понятие теории — граф — задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих некоторые пары вершин. Пример графа — схема метрополитена: множество станций (вершины графа) и соединяющих их линий (рёбра графа).

    * * *

    ГРАФОВ ТЕОРИЯ

    ГРА́ФОВ ТЕО́РИЯ, раздел математики, особенность которого — геометрический подход к изучению объектов. Основное понятие теории — граф — задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа — схема метрополитена: множество станций (вершины графа) и соединяющих их линий (ребра графа).

  7. Источник: Энциклопедический словарь



  8. Математическая энциклопедия

    - область дискретной математики, особенностью к-рой является геометрич. подход к изучению объектов. Основной объект Г. т.- граф и его обобщения. Первые задачи Г. т. были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). Одним из первых результатов в Г. т. явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кенигсбергских мостах. Сформулированная в сер. 19 в. проблема четырех красок ( см. Четырех красок задача).также выглядит как развлекательная задача, однако попытки ее решения привели к появлению нек-рых исследований графов, имеющих теоретическое и прикладное значение. В сер. 19 в. появились работы, в к-рых при решении практич. задач были получены результаты, относящиеся к Г. т. Так, напр., Г. Кирхгоф [2] при составлении полной системы уравнений для токов и напряжений в электрич. схеме предложил по существу представлять такую схему графом и находить в этом графе остовиые деревья, с помощью к-рых выделяются линейно независимые системы контуров. А. Кэли [3], исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил нек-рые из них. В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике, биологии, экономике, социологии и т. д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В нач. 20 в. графы стали использоваться для представления нек-рых математич. объектов и формальной постановки различных дискретных задач; при этом наряду с термином "граф" употреблялись и. другие термины, напр, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 монографии Д. Кёнига [4] термин "граф" стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 20-30-х гг. 20 в. появились первые результаты, относящиеся к изучению свойств связности, пла-нарности, симметрии графов, к-рые привели к формированию ряда новых направлений в Г. т. Значительно расширились исследования по Г. т. в конце 40-х - начале 50-х гг., прежде всего в силу развития кибер нетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетич. систем, интерес к Г. т. возрос, а проблематика Г. т. существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач Г. т. были разработаны методы их решения, напр., один из таких методов позволяет решать задачи о построении максимального потока через сеть (см. Поток в сети). Для отдельных классов графов (деревья, плоские графы и т. д.), к-рые изучались и ранее, было показано, что решения нек-рых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.). Характеризуя проблематику Г. т., можно отметить, что нек-рые направления носят более комбинаторный характер, другие - более геометрический. К первым относятся, напр., задачи о подсчете и перечислении графов с фиксированными свойствами, задачи о построении графов с заданными свойствами. Геометрический (топологический) характер носят многие циклы задач Г. т., напр, графов обходы, графов укладки. Существуют направления, связанные с различными классификациями графов, напр, по свойствам их разложения. Примером результата о существовании графов с фиксированными свойствами может служить критерий реализуемости чисел степенями вершин нек-рого графа: набор целых чисел сумма к-рых четна, можно реализовать степенями вершин графа без петель и кратных ребер тогда и только тогда, когда для любого выполняется условие

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

    где Для числа неизоморфных графов без петель и кратных ребер с вершинами было показано, что

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

    В другом направлении исследований Г. т. изучаются маршруты, содержащие все вершины пли ребра графа (см. Графа обход).

    Известен простой критерий существования маршрута, содержащего все ребра графа: в связном графе цикл, содержащий все ребра и проходящий по каждому ребру один раз, существует тогда и только тогда, когда все вершины графа имеют четные степени. В случае обхода множества вершин графа имеется только ряд достаточных условий существования цикла, проходящего по всем вершинам графа по одному разу.

    Характерным специфическим направлением Г. т. является цикл задач, связанный с раскрасками графов, в к-ром изучаются разбиения множества вершин (ребер), обладающие определенными свойствами, напр, смежные вершины (ребра) должны принадлежать различным множествам (вершины или ребра из одного множества окрашиваются одним цветом; см. Графа раскраска). Было доказано, что наименьшее число цветов, достаточное для раскраски ребер любого графа без петель с максимальной степенью , равно а для раскраски вершин любого графа без петель и кратных ребер достаточно цветов.

    Существуют п другие циклы задач (см. Покрытия и упаковки, Графа укладка. Графов числовые характеристики);нек-рые из них сложились под влиянием различных разделов математики. Так, под влиянием топологии производится изучение вложений графов в различные поверхности. Напр., было получено необходимое и достаточное условие вложения графа в плоскость (критерий Понтрягина- Куратовского): граф является плоским тогда и только тогда, когда он не содержит подграфов, получаемых с помощью подразбиения ребер из полного 5-вершинного графа и полного двудольного графа с тремя вершинами в каждой доле. Под влиянием алгебры стали изучаться группы автоморфизмов графов (см. Графа автоморфизм). В частности, было доказано, что каждая конечная группа изоморфна группе автоморфизмов нек-рого графа. Влияние теории вероятностей сказалось на исследовании графов случайных. Многие свойства были изучены для "почти всех" графов; напр, было показано, что почти все графы с n вершинами связаны, имеют диаметр 2, обладают гамильтоновым циклом (циклом, проходящим через все вершины графа по одному разу).

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

    Большое значение в Г. т. имеют алгоритмические вопросы. Для конечных графов, т. е. для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для Г. т. имеет построение эффективных алгоритмов, находящих точное или приближенное решение. Для нек-рых задач такие алгоритмы построены, напр., для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока.

    Результаты и методы Г. т. применяются при решении транспортных задач о перевозках, для нахождения оптимальных решений задачи о назначениях, для выделения "узких мест" при планировании и управлении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технологич. процессов, в построении различных дискретных устройств, в программировании и т. д.

    Лит.; [1] Euler L., в кн.: Commentationes Arithmetical Collectae, St. Peterburg, 1766, с. 66-70; [2] Kirchhoff G., "Poggendorf Annalen", 1847, Bd 72, S. 497-508; [3] Cayley A., "Collected Mathematical papers", Camb. 1854 v. 3, p. 242; [4] КonigD., Theorie der endlichen und unendhchen Graphen, 2 ed., N. Y., 1950; [5] Верж К., Теория графов и ее применение, пер. с франц., М., 1962; [6] 3ыков А. А., Теория конечных графов, [в.1], Новосиб., 1969 [7] Xарари Ф., Теория графов, пер. с англ., М., 1973; [8] Козырев В. П., в кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, т. 10, 1972, с. 25-74; [9] Наrary F., Palmer Е., Graphical enumeration, N. Y. - L., 1973.

    В. В. Алексеев, В. П. Козырев, А. А. Сапоженко.

  9. Источник: Математическая энциклопедия



  10. Большой энциклопедический политехнический словарь

    раздел математики, особенность к-рого - геом. подход к изучению объектов. Осн. понятие теории - граф - задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих нек-рые пары вершин. Пример графа - схема метрополитена: множество станций (вершины графа) и соединяющих их линий (рёбра графа).

  11. Источник: Большой энциклопедический политехнический словарь



  12. Естествознание. Энциклопедический словарь

    раздел математики, особенность к-рого - геом. подход к изучению объектов. Осн. понятие теории - граф - задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих нек-рые пары вершин. Пример графа - схема метрополитена: множество станций (вершины графа) и соединяющих их линий (рёбра графа).

  13. Источник: Естествознание. Энциклопедический словарь



  14. Большой Энциклопедический словарь

  15. Источник: