Графов числовые характеристики

функции, заданные на множестве графов и принимающие значения из нек-рого множества чисел. Ниже приведен ряд Г. ч. х. и их наиболее употребительные обозначения. Наиболее простыми Г. ч. х. являются число вершин и число ребер (дуг) графа G. Цикломатическим числом [img: http://localhost:8080/file/010429-142.jpg] графа Gназ. наименьшее число ребер, удаление к-рых приводит к графу без циклов; [img: http://localhost:8080/file/010429-143.jpg] где т - число ребер, п - число вершин, k - число компонент связности графа G. Числом вершинной связности [img: http://localhost:8080/file/010429-144.jpg] [числом реберной связности [img: http://localhost:8080/file/010429-145.jpg] ] наз. наименьшее количество вершин (ребер) графа G, удаление к-рых приводит к несвязному графу или тривиальному графу (т. е. графу, состоящему из одной вершины). Плотность [img: http://localhost:8080/file/010429-146.jpg] есть наибольшее число вершин в полном подграфе графа G;число независимости, или число внутренней устойчивости, [img: http://localhost:8080/file/010429-147.jpg] есть наибольшее число попарно несмежных вершин графа G(при этом попарно несмежные вершины графа Gобразуют внутренне устойчивое множество). Хроматическим числом [img: http://localhost:8080/file/010429-148.jpg] [реберным хроматическим числом [img: http://localhost:8080/file/010429-149.jpg] ] наз. наименьшее количество цветов, к-рыми можно раскрасить вершины (ребра) графа Gтак, чтобы любые смежные вершины (ребра) были окрашены разными цветами (см. также Графа раскраска). Числом внешней устойчивости [img: http://localhost:8080/file/010429-150.jpg] наз. наименьшее количество вершин такого подмножества Wмножества вершин графа G, что любая вершина, не принадлежащая W, смежна по крайней мере с одной вершиной из W. Древесность [img: http://localhost:8080/file/010429-151.jpg] есть наименьшее число непересекающихся по ребрам остовных лесов графа G, объединение к-рых есть граф G. Крупность [img: http://localhost:8080/file/010429-152.jpg] - это наибольшее число непересекающихся по ребрам неплоских подграфов графа G. Толщина [img: http://localhost:8080/file/010429-153.jpg] - это наименьшее число плоских подграфов, объединение к-рых есть G. Число скрещиваний- это наименьшее число попарных пересечений ребер графа Gпри расположении его на плоскости. Род [img: http://localhost:8080/file/010429-154.jpg] графа Gесть наименьший род двумерной ориентируемой поверхности, на к-рой можно уложить граф Gбез пересечения его ребер (см. Графа укладка). Нек-рые числовые характеристики относят данному графу количества подграфов определенного типа, напр, число остовных деревьев, число гамильтоновых циклов н т. д. Существуют характеристики, зависящие от параметра [img: http://localhost:8080/file/010429-155.jpg] (напр., число полных подграфов с kвершинами), совокупность этих характеристик может быть задана многочленом [img: http://localhost:8080/file/010429-156.jpg] - аналогом производящей функции. Многие из таких многочленов можно находить рекуррентно, применяя операции над графами - удаление вершины или ребра, стягивание ребра и др. возникает необходимость изучения взаимосвязи различных Г. ч. х. На нек-рых множествах Г. ч. х. достигают своих экстремальных значений, при нахождении к-рых часто удается описать графы, на к-рых они достигаются. Тогда нахождение экстремальных значений сводится к исследованию таких графов. Для изучения графов, у к-рых рассматриваемая характеристика принимает заданное значение, оказывается полезным исследование свойств критических графов (см. Граф экстремальный).