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

Cтраница 2

Этот пустой подграф является одновременно и ограничением графа О, и его порожденным подграфом, но он не является остовным подграфом никакого графа О, кроме нуль-графа. [16]

Случай 2.3. Если ud, vc или uv принадлежит G, то G3 - порожденный подграф. [17]

Операции удаления вершины и дуги, а также понятия подграфа, остовного подграфа и порожденного подграфа определяются для ориентированных псевдографов аналогично тому, как это делалось в случае неориентированных псевдографов. [18]

Граф С с р2п вершинами обладает следующим свойством: для каждого мн ожества Sen вершинами порожденные подграфы S и У-S изоморфны тогда и только тогда, когда G совпадает с одним из графов К2п, КПХК2, 2Кп, 2С4 или с их дополнениями. [19]

Если эти вершины удалить из графа G ( X, Г), то в оставшемся порожденном подграфе G ( X - R ( хг) fl Q ( xi)) можно таким же способом выделить новую СК, содержащую х, 6 X - - R ( xt) П Q ( xt) - Эту процедуру можно повторять до тех пор, пока все вершины графа G не будут сгруппированы в соответствующие СК. [20]

Покажем, что если граф G не удовлетворяет утверждению ( 3), то в G найдется порожденный подграф, изоморфный одному из девяти запрещенных графов. Предположим, что G содержит нечетные треугольники abc и aba, причем с и а не смежны. [21]

Для каждого / величина ( - 1) т - 5 / является суммой определителей матриц смежности порожденных подграфов графа О, имеющих т - / вершин. [22]

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

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

В зависимости от того, принадлежит или нет ребро uv графу G, получаем G4 или G7 в качестве порожденного подграфа. [25]

Вместо утомительной фразы корневые графы G, у которых в качестве корня берется подграф Н, не обязательно являющийся порожденным подграфом, мы предпочитаем говорить над-графы графа Я, что обеспечивает более эффективную мнемоническую схему. [26]

Ниже на основе введенных в разделе 4.3 понятий и свойств формализованного описания ВХС формулируется и доказывается критерий выбора влияющих совокупностей RJ водохранилищ и порожденных подграфов GR, состояния которых влияют на функционирование j - соответствующих замыкающих створов. [27]

Пять триангулированных пятиугольников, каждый из которых имеет ориентированное граничное ребро. [28]

Техника этой главы может быть приспособлена и к нахождению производящих функций для многих классов таких графов, которые либо похожи на деревья, либо содержат деревья, как порожденные подграфы. Мы рассмотрим достаточно подробно задачи перечисления унициклических графов, функциональных орграфов, деревьев блоков и точек сочленения, графов блоков и кактусов. [29]

Граф G ( VH) имеет - фактор тогда и только тогда, когда V четно и не существует такого множества S вершин, что число нечетных компонент порожденного подграфа G ( F - - S) превосходит S. Под нечетной компонентой графа понимается компонента с нечетным числом вершин. [30]

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