ГРАФА СВЯЗНОСТЬ это:

ГРАФА СВЯЗНОСТЬ

- одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом реберной связности [обозначение ] наз. наименьшее число ребер графа G, удаление к-рых приводит к несвязному графу. Граф G наз. k-связным, если и k-pеберно связным, если . Максимальный по включению k-связный подграф графа G наз. его k-cвязной компонентой; 1-связная компонента иаз. компонентой связности. При исследовании коммуникационных и логических сетей числа связности соответствующих графов можно интерпретировать как степень надежности этих сетей.

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

Для любых целых существует граф G, у к-рого Если граф G имеет пвершин и , то . Говорят, что множество Sвершин, ребер или вершин п ребер разделяет вершины и и v, если ии vпринадлежат разным компонентам связности графа G-S, полученного из G удалением элементов множества S. Справедливы следующие утверждения.

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

Лит.:[1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966. А. А. Сапоженко.


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

Смотреть что такое "ГРАФА СВЯЗНОСТЬ" в других словарях:

  • Связность графов — Содержание 1 Связность 2 Примеры 3 Теорема несвязности графов …   Википедия

  • Связность графа — Связный граф граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует по крайней мере один путь. Содержание 1 Примеры применения 2 Связность для орграфов …   Википедия

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

  • ГРАФ — множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,… …   Математическая энциклопедия

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

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

  • МАТРОИД — гиперграф специального вида. М. определяется заданием множества Vэлементов и семейства подмножеств множества У, называемых независимыми множествами, для к рых выполняются следующие аксиомы: 1) пустое множество независимо; 2) каждое подмножество… …   Математическая энциклопедия

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

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) …   Википедия

Книги

Другие книги по запросу «ГРАФА СВЯЗНОСТЬ» >>


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

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