ГРАФОВ ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ

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

где т - число ребер, п - число вершин, k - число компонент связности графа G. Числом вершинной связности [числом реберной связности ] наз. наименьшее количество вершин (ребер) графа G, удаление к-рых приводит к несвязному графу или тривиальному графу (т. е. графу, состоящему из одной вершины). Плотность есть наибольшее число вершин в полном подграфе графа G;число независимости, или число внутренней устойчивости, есть наибольшее число попарно несмежных вершин графа G(при этом попарно несмежные вершины графа Gобразуют внутренне устойчивое множество). Хроматическим числом [реберным хроматическим числом ] наз. наименьшее количество цветов, к-рыми можно раскрасить вершины (ребра) графа Gтак, чтобы любые смежные вершины (ребра) были окрашены разными цветами (см. также Графа раскраска). Числом внешней устойчивости наз. наименьшее количество вершин такого подмножества Wмножества вершин графа G, что любая вершина, не принадлежащая W, смежна по крайней мере с одной вершиной из W. Древесность есть наименьшее число непересекающихся по ребрам остовных лесов графа G, объединение к-рых есть граф G. Крупность - это наибольшее число непересекающихся по ребрам неплоских подграфов графа G. Толщина - это наименьшее число плоских подграфов, объединение к-рых есть G. Число скрещиваний- это наименьшее число попарных пересечений ребер графа Gпри расположении его на плоскости. Род графа Gесть наименьший род двумерной ориентируемой поверхности, на к-рой можно уложить граф Gбез пересечения его ребер (см. Графа укладка).

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

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

Лит.:[1] 3ыков А. А., Теория конечных графов, [в. 1], Новосиб., 1969; [2] Козырев В. П., в кн.: Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, т. 10, М., 1972, с. 25-75; [3] Xарари Ф., Теория графов, пер. с англ,, М., 1973.

В. П. Козырев.