Связность графа

Связность графа

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

Содержание

Примеры применения

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

Связность для орграфов

В связном ориентированном графе из любой вершины в любую существует путь, при этом связный ориентированный граф содержит ровно одну сильно связную компоненту.

Некоторые критерии связности

Здесь приведены некоторые критериальные(эквивалентные) определения связного графа:
Граф называется односвязным (связным), если:
1 У него одна компонента связности
2 Существует путь из любой вершины в любую
3 Существует путь из заданной вершины в любую
4 Содержит связный подграф, включающий все вершины исходного графа
5 Содержит в качестве подграфа дерево,включающее все вершины исходного графа(оно называется остовным)
6 При произвольном делении его вершин на 2 группы всегда существет хотя бы 1 ребро, соединяющее пару вершин из разных групп

См. также

  • теорема Менгера

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Связность графа" в других словарях:

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

  • ГРАФА СВЯЗНОСТЬ — одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к рых (вместе с… …   Математическая энциклопедия

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

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

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

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

  • Теория графов — [graph theo­ry] математическая теория, содержание которой формулируется двояко, в зависимости от трактовки ее исходного понятия граф: теоретико множественной или геометрической. В первом случае предметом теории являются графы как некие объекты,… …   Экономико-математический словарь

  • теория графов — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] теория графов Математическая теория, содержание которой формулируется двояко, в зависимости от трактовки ее… …   Справочник технического переводчика

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

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


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

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