Порожденный подграф

Cтраница 3

Девять запрещенных подграфов для реберных графов. [31]

Если выполняется последнее, то вершина v должна быть смежной со всеми четырьмя вершинами двух треугольников, и, следовательно, граф G содержит G3 ( см. рис. 8.3) как порожденный подграф. [32]

Порожденным подграфом 2) 6, называется граф ( Ха, Т), для которого Х сг X и для каждой вершины XI (; Хв, Т3 ( х Г ( х) П - в - Таким образом, порожденный подграф состоит из подмножества вершин X, множества вершин исходного графа и всех таких дуг графа С, у которых конечные и начальные вершины принадлежат подмножеству Хв. Часто бывает удобно обозначать подграф 6, просто символом ( X), мы будем в дальнейшем использовать такое обозначение, если нет опасности внесения путаницы. [33]

Перечислению 2-раскрашенных графов был посвящен § 4.3, а корневые графы, у которых в качестве корня выделялся некото-рый порожденный подграф, изучались в предыдущем параграфе - Предметом данного параграфа является распространение этих исследований на случай перечисления таких корневых графов, у которых в качестве корня берется не обязательно порожденный подграф; затем предполагается применить полученные выводы к перечислению m - раскрашенных графов. [34]

Перечислению 2-раскрашенных графов был посвящен § 4.3, а корневые графы, у которых в качестве корня выделялся некоторый порожденный подграф, изучались в предыдущем параграфе - Предметом данного параграфа является распространение этих исследований на случай перечисления таких корневых графов, у которых в качестве корня берется не обязательно порожденный подграф; затем предполагается применить полученные выводы к перечислению иг-раскрашенных графов. [35]

Порожденным подграфом 2) G, называется граф ( Хв, Г8), для которого Xs с X и для каждой вершины Xi 6 s - Га ( xt) Г ( xt) f) Xs. Таким образом, порожденный подграф состоит из подмножества вершин X, множества вершин исходного графа и всех таких дуг графа G, у которых конечные и начальные вершины принадлежат подмножеству Ха. Часто бывает удобно обозначать подграф Ga просто символом ( Xs), мы будем в дальнейшем использовать такое обозначение, если нет опасности внесения путаницы. [36]

Пусть К - произвольная компонента би-курсального подграфа № графа С. Тогда К есть порожденный подграф графа С. Кроме того, всякое соединяющее ребро для К либо является проникающим в компоненту К, либо уникур-сальным из своего конца, содержащегося в К. [37]

Поскольку № - порожденный подграф графа О, то один конец ребра А ( обозначим его через х) находится в В, а другой ( конец у) в В не содержится. [38]

Наконец, Байнеке [4] и Робертсон ( не опубликовано) нашли все подграфы, которые не могут встречаться в реберных графах. Напомним, что порожденным подграфом называется подграф, максимальный на данном множестве вершин. Треугольник Т графа G называется нечетным, если в G имеется вершина, смежная с нечетным числом вершин в Т, и четным в противном случае. [39]

Довольно часто возникает задача поиска таких подмножеств множества вершин X графа G, которые обладают определенным, наперед заданным свойством. X, для которого порожденный подграф ( S) является полным. Или какова максимальная мощность подмножества S, такого, что граф ( S) - вполне несвязный. Она состоит в нахождении минимально возможной мощности таких подмножеств S множества X, что любая вершина из X - S достижима из S с помощью путей единичной длины. [40]

Легко проверить, что ни один из девяти графов, приведенных на рис. 8.3, не допускает разбиение множества ребер на полные подграфы, удовлетворяющее указанному выше условию. Окончательный результат вытекает из того, что каждый порожденный подграф реберного графа сам должен быть реберным графом. [41]

Ясно, что если ud G, то G3 - порожденный подграф графа G; таким образом, ud § G. [42]

Оно связано с построением парной группы путем незначительной переделки соответствующей симметрической группы. Эта модификация легко обобщается на корневые графы, у которых корень представляет собой произвольный порожденный подграф ( см. Харари и Палмер [1]), могущий быть и графом, и орграфом, и мультиграфом. [43]

Перечисление корневых ( непомеченных) графов является чуть менее очевидным ( см. Харари [4]) i Оно связано с построением парной группы путем незначительной переделки соответствующей симметрической группы. Эта модификация легко обобщается на корневые графы, у которых корень представляет собой произвольный порожденный подграф ( см. Харари и Палмер [1 ]), могущий быть и графом, и орграфом, и мультиграфом. [44]

Довольно часто возникает задача поиска таких подмножеств множества вершин X графа О, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества 8 с X, для которого порожденный подграф ( 5) является полным. Или какова максимальная мощность подмножества 5, такого, что граф ( 5) - вполне несвязный. Она состоит в нахождении минимально возможной мощности таких подмножеств 5 множества X, что любая вершина из X - б1 достижима из с помощью путей единичной длины. Решение этой задачи дается так называемым числом доминирования графа С. [45]

Страницы: 1 2 3 4