Связный подграф - граф
Cтраница 1
Связный подграф графа G называется его связной компонентой. Множество вершин связной компоненты называется областью связности графа. [1]
Максимальный n - связный подграф графа G называется его n - связной компонентой или просто п-компонентой. [2]
Максимальный 1) - связный подграф графа G называется его п-компонентой. В частности, 1-компоненты графа G - это его нетривиальные компоненты, а 2-компоненты - его блоки, содержащие по крайней мере 3 вершины. [3]
В § 9 мы определили остовное дерево связного графа как связный подграф графа G, не содержащий циклов и включающий каждую вершину изб. Ясно, что остовное дерево не может содержать в качестве собственного подграфа другое остовное дерево. [4]
Покажем теперь, что S содержит четыре вершины, которые являются общими точками ( точками пересечений) с / и Е и расположены на S в чередующемся порядке. Каждый связный подграф внутреннего графа, включая 1, который пересекается только с S ] / i.i [, можно перевести во внешний граф на грань, ограниченную Р и S. [5]
Доказательство утверждается 6.2.2. Пусть X - граф Кэли группы относительно порождающего множества S. Тогда существует конечный связный подграф L графа X такой, что граф XL, полученный из X удалением ребер L и всех получившихся изолированных вершин, состоит в точности из п бесконечных компонент. G такой, что gL ] L пусто, и, таким образом, gL лежит целиком внутри некоторой компоненты У из XL. Теперь в точности одна из компонент Y gL бесконечна, и граф LU ( y) - связен, откуда X gL имеет не более двух бесконечных компонент. [6]
G ( двудольного или нет) называется допустимым, если оно принадлежит некоторому совершенному паросочетанию графа G. В противном случае ребро называется запрещенным. Граф G назовем элементарным, если все допустимые ребра в нем порождают связный подграф графа G. Термин элементарный для таких графов был предложен Хетейи в 1960 г., хотя идея рассмотрения этих графов возникла значительно раньше - ее можно найти еще у Кенига в его статье 1915 г.. В случае двудольных графов существует еще несколько полезных определений этого понятия. [7]
G, удаление к-рых приводит к несвязному графу. Максимальный по включению fe - связный подграф графа G наз. [8]
 |
Иллюстрация нестрогого сравнения.| Пример нестрогого сравнения. [9] |
Другими словами, V есть множество всех возможных сопоставлений между вершинами. А есть множество всех сопоставлений совместимых вершин. Задача наилучшего сравнения в случае бесконечных COSTN и COSTA заключается в нахождении самого большого множества сопоставлений совместимых вершин. Это равносильно поиску максимальной клики в графе соединений, где клика есть полностью связный подграф графа G, а максимальная клика - это клика, не являющаяся подмножеством множества вершин другой клики. Следовательно, задача сводится к нахождению максимальной клики. [10]
Граф является связным, если каждая пара вершин связана цепью. Изолированная вершина является компонентой, и каждая вершина содержится в одной и только в одной компоненте. Направленный граф - сильно связный, если для каждой пары ( Vit Vj) вершина Vi достижима из Vj и наоборот. Сильно связной компонентой графа G ( для краткости - сильной компонентой) является сильно связный подграф графа G, максимальный относительно включения ребер. [11]
В этом случае группу п ( У, X, v) называют иногда древесным произведением. Из этих рассуждений следует в силу существования нормальных форм из теорем 2.2.4 и 2.2.5, что если Х0 - любой связный подграф графа X и ( о, XQ) - ограничение (, X) до АО, то для любой вершины v из Х0 естественное отображение п ( / ь XQ, v) - n ( Q /, X, v) есть вложение. [12]
Неориентированный граф G связен, если существует хотя бы один путь в G между каждой парой вершин vt и Vj. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Говорят, что ориентированный граф сильно связен, если для каждой пары вершин vt и Vj существует по крайней мере один ориентированный путь из Vi в Vj и по крайней мере один из v в иг. Граф, состоящий из единственной изолированной вершины, является ( тривиально) связным. Максимальный:) связный подграф графа G называется связной компонентой или просто компонентой G. Несвязный граф состоит из двух или более компонент. Максимальный сильно связный подграф называется сильно связной компонентой. [13]
Предположим теперь, что не каждое ребро в графе В1к ( С) является перешейком. Тогда по теореме 1.45 в В1к ( С) существует цикл. Пусть Н - объединение всех блоков В, отличных от блока В. Используя теорему 1.25 ( возможно, несколько раз), получаем, что Я - связный подграф графа О. [14]
Страницы: 1