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

Cтраница 1

Порожденный подграф называется полным, если все его вершины попарно смежны. Число вершин полного подграфа называется его степенью. [1]

Порожденный подграф ( 5Г [ С ]) графа О ( X, Г), где 5Г [0] е X, называется г-подгра-фом, если он г-хроматический. Очевидно, что для фиксированного значения г, вообще говоря, существует много различных максимальных г-подграфов данного графа О. [2]

Порожденный подграф ( ST IG ] графа G ( X, Г), где Sr [ G ] s X, называется г-подгра-фом, если он r - хроматический. Если не существует такого множества Н, что Н: э Sr ( G) и подграф ( Н) является г-хроматическим, то подграф ( ST [ G ]) называется максимальным r - подграфом графа G. Очевидно, что для фиксированного значения г, вообще говоря, существует много различных максимальных г-подграфов данного графа G. [3]

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

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

Сеть to и соответствующий ей граф Т. [6]

Если образовывать всевозможные порожденные подграфы произвольного графа Ге еФ ( л, р) исключением определенного числа вершин из какой-либо его комлоненты, то минимальное число ребер будет иметь подграф, образованный исключением вершин из компоненты с максимальным числом вершин. Причем это минимальное число ребер зависит только от числа исклю но, какие бы ребра графа Т чаемых вершин. [7]

Если граф С и порожденные подграфы О [ X ] и О [ У ] связны, то множество / ( X, У) называется бондом ( или минимальным разрезом, или сечением) графа О. Подграфы О [ X ] и О [ У ] называются торцевыми графами этого бонда. Из приведенного определения следует, что бонд ( XУ) должен быть непустым множеством. Если граф О несвязен, то его бонд определим как бонд какой-либо его компоненты. Заметим, что всякий перешеек графа образует однореберный бонд. Торцевые графы перешейка являются торцевыми графами соответствующего бонда. [8]

Это условие справедливо и для всех порожденных подграфов максимального полного подграфа. Отсюда следует, что произвольный мограф Ч, подчиненный мографу Хелли W, также обладает свойством Хелли. [9]

На рис. 1.4 ( в) показан порожденный подграф графа, приведенного на рис. 1.4 ( а), содержащий только вершины а, х, хэ и x и дуги, которые их связывают. [10]

На рис. 1.4 ( в) показан порожденный подграф графа, приведенного на рис. 1.4 ( а), содержащий только вершины х х %, х3 и x и дуги, которые их связывают. [11]

Простой цикл длины 4 не может быть порожденным подграфом графа интервалов. [12]

Критически несовершенным графом называется несовершенный граф, все порожденные подграфы которого совершенны. Показать, что сильная гипотеза Бержа эквивалентна следующей: каждый критически несовершенный граф является либо нечетным циклом без хорд длины, не меньшей 5, либо его дополнением. [13]

Добавляя все ребра из 2 в подграф №, получаем порожденный подграф УС графа О. [14]

Компонентой связности графа G ( X, U) называется такой его порожденный подграф, который наряду с некоторой вершиной х содержит и все вершины, с которыми х связана маршрутом. Компоненты связности графа G определяют разбиение множества X на подмножества. Граф, состоящий из единственной компоненты связности, называется связным. [15]

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