ГРАФ ЭКСТРЕМАЛЬНЫЙ это:

ГРАФ ЭКСТРЕМАЛЬНЫЙ

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


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

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


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

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

Лит.:[1] Харари Ф., Теория графов, пер. с англ., М., 1973; [2] Зыков А. А., Теория конечных графов, [в. 1], Новосиб., 1969; [3] Тuran P., "Mat. Fiz. Lapok", 1941, V. 48, p. 436-52. А. А. Сапоженко.


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

Смотреть что такое "ГРАФ ЭКСТРЕМАЛЬНЫЙ" в других словарях:

  • экстремальный граф — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN extremal graph …   Справочник технического переводчика

  • Жоффруа де Мандевиль, 1-й граф Эссекс — Жоффруа де Мандевиль (фр. Geoffrey de Mandeville; ум. в 1144 г.)  один из наиболее влиятельных английских аристократов второй четверти XII века, активный участник гражданской войны в Англии 1135 1154 гг., 1 й граф Эссекс.… …   Википедия

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

  • Готфрид де Мандевиль — Жоффруа де Мандевиль (фр. Geoffrey de Mandeville; ум. в 1144 г.)  один из наиболее влиятельных английских аристократов второй четверти XII века, активный участник гражданской войны в Англии 1135 1154 гг., 1 й граф Эссекс. Благодаря своей частой… …   Википедия

  • Мандевиль, Жоффруа де — Жоффруа де Мандевиль (фр. Geoffrey de Mandeville; ум. в 1144 г.)  один из наиболее влиятельных английских аристократов второй четверти XII века, активный участник гражданской войны в Англии 1135 1154 гг., 1 й граф Эссекс. Благодаря своей частой… …   Википедия

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

  • Готика (культура) — Гот из Германии Готы  представители молодёжной субкультуры, зародившейся в конце 70 х годов XX го века на волне пост панка. Готическая субкультура весьма разнообразна и неоднородна, однако для нее в той или иной степени характерны следующие черты …   Википедия

  • Готика (субкультура) — Гот из Германии Готы  представители молодёжной субкультуры, зародившейся в конце 70 х годов XX го века на волне пост панка. Готическая субкультура весьма разнообразна и неоднородна, однако для нее в той или иной степени характерны следующие черты …   Википедия

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

  • Херка — Гот из Германии Готы  представители молодёжной субкультуры, зародившейся в конце 70 х годов XX го века на волне пост панка. Готическая субкультура весьма разнообразна и неоднородна, однако для нее в той или иной степени характерны следующие черты …   Википедия


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

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