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

Cтраница 4

Рассмотрим множество всех k 6Е J таких, что они входят в состав каких-либо цепочек влияния на j - й ВХК. Фактически, под влияющей совокупностью далее будет подразумеваться не только RJ, но и порожденный подграф GR. [46]

Граф G называется k - вырожденным, если 6 () & для каждого порожденного подграфа Н графа G. Параметр p & ( G) графа G определяется как наименьшее число подмножеств в разбиении множества вершин графа G, в котором каждое подмножество порождает - вырожденный граф. & ( G) обобщают понятия хроматического числа и вершинной древесности. [47]

Диаграмма взаимосвязей между задачами. [48]

Тогда в матрицах Т из соответствующих ЗНП ( или ЗНР) столбцы будут представлять все порожденные подграфы или остовные подграфы с задаиными свойствами, а строки матриц будут представлять вершины или ребра графа. [49]

Диаграмма взаимосвязей между задачами. [50]

Тогда в матрицах Т из соответствующих ЗНП ( или ЗНР) столбцы будут представлять все порожденные подграфы или остовные подграфы с заданными свойствами, а строки матриц будут представлять вершины или ребра графа. [51]

Мы увидим в нижеследующем уравнении, что эта формула включает в себя цикловой индекс реберной группы дополнения графа Я. Из метода, рассмотренного в предыдущем параграфе при перечислении корневых графов с корнями, представляющими собой порожденные подграфы Н порядка п, следует, что группа подстановок, необ ходимая для исследования надграфов графа Н, может быть получена расширением множества объектов группы Г ( Н) о Sp n путем включения ребер из дополнения Я. [52]

Мы увидим в нижеследующем уравнении, что эта формула включает в себя цикловой индекс реберной группы дополнения графа Я. Из метода, рассмотренного в предыдущем параграфе при перечислении корневых графов с корнями, представляющими собой порожденные подграфы Я порядка / г, следует, что группа подстановок, необходимая для исследования надграфов графа Я, может быть получена расширением множества объектов группы Г ( Н) о Sp n путем включения ребер из дополнения Я. [53]

Утверждение очевидно для вполне несвязных графов. Пусть G - произвольный n - хроматический граф, п - 2, а Н - любой наименьший порожденный подграф, для которого х ( Я) я. Таким образом, х ( Я - и) п - 1 для всех вершин v графа Я. [54]

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