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

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

функции, заданные на множестве графов и принимающие значения из нек-рого множества чисел. Ниже приведен ряд Г. ч. х. и их наиболее употребительные обозначения. Наиболее простыми Г. ч. х. являются число вершин и число ребер (дуг) графа 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.

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



Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "ГРАФОВ ЧИСЛОВЫЕ ХАРАКТЕРИСТИКИ" в других словарях:

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

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

  • ГРАФ СЛУЧАЙНЫЙ — вероятностная модель, предназначенная для изучения частотных характеристик различных параметров графов. Под Г. с. обычно понимается нек рый класс графов на к ром задано распределение вероятностей. Произвольный конкретный граф Gиз наз. реализацией …   Математическая энциклопедия

  • ПОКРЫТИЯ И УПАКОВКИ — комбинаторные конфигурации, связанные с многозначным отображением одного множества на другое. Пусть заданы множества Vи Еи многозначное отображение Г множества Ена множество V. Пусть Г(е). образ элемента при отображении Г и для любого пусть Г(С) …   Математическая энциклопедия

  • ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… …   Математическая энциклопедия

  • Поиск количественных соотношений структура-свойство — Поиск количественных соотношений структура свойство  процедура построения моделей, позволяющих по структурам химических соединений предсказывать их разнообразные свойства. За моделями, позволяющими прогнозировать количественные… …   Википедия

  • QSAR — Поиск количественных соотношений структура свойство  процедура построения моделей, позволяющих по структурам химических соединений предсказывать их разнообразные свойства. За моделями, позволяющими прогнозировать количественные… …   Википедия

  • ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… …   Математическая энциклопедия

  • ГРАФА УКЛАДКА — графа вложение, отображение вершин и ребер графа соответственно в точки и непрерывные кривые нек рого пространства такое, что вершины, инцидентные ребру, отображаются в концы кривой, соответствующей этому ребру. Правильной укладкой наз. укладка,… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»