Cтраница 2
Отсюда следует, что данный граф Ою непланарный. [16]
Понятие реберного графа для данного графа настолько естественно, что независимо было введено многими авторами. Были даны различные описания реберных графов. В этой главе вводится также тотальный граф, который изучался впервые Бехзадом [1], и поскольку ( это очень удивительно. Мы исследуем связь между реберными и тотальными графами, уделяя особое внимание эйлеровым и га-мильтоновым графам. [17]
Геометрический граф, изоморфный данному графу. [18]
Достаточно удвоить ребра в данном графе G, расщепляя каждое па пару ребер противоположной ориентации. [19]
Достаточно удвоить ребра в данном графе G, расщепляя каждое на пару ребер противоположной ориентации. [20]
Нелегко выяснить, 1-факторизуем ли данный граф, или хотя бы установить существование какого-нибудь 1-фактора. Байнеке и Пламмер [ 11 показали, однако, что многие графы либо вообще не имеют 1-факторов, либо у них число 1-факторов не меньше двух. [21]
Теорема 9.5. Пусть G - данный граф, af - функция, определенная на множестве V вершин графа G и принимающая неотрицательные целые значения. [22]
Когда сме / кностный граф данного графа имеет дилеров цикл. [23]
Для минимизации числа пересечений ребер данного графа переходим к блоку генетических операторов. [24]
Напомним, что многогранником паросочетаний данного графа G называется выпуклая оболочка всех паросочетаний графа G. [25]
Постройте алгоритм для раскраски вершин данного графа G, использующий минимально возможное число красок и такой, что никакие две смежные вершины не имеют одного и того же цвета. [26]
Так как двудольная часть В произвольного данного графа G характеризуется тем, что В не содержит нечетных простых циклов, из общих результатов главы 6 следует. [27]
Из теоремы Кенига следует, что данный граф двудольный. [28]
Матроид паросочетаний определяется на множестве вершин данного графа, независимыми множествами являются подмножества вершин, для которых в G существует совершенное паросо-четание. [29]
Рассмотрим декомпозицию Галлаи - Эдмондса для данного графа G. Через G обозначим двудольный граф, получаемый из G удалением входящих в C ( G) вершин и стягиваемых множеством A ( G) ребер и сжатием каждой связной компоненты графа ( D ( G)) в одиночную вершину. [30]