Данный граф

Cтраница 3

Как правило, определить, является ли данный граф критическим, чрезвычайно трудно. Однако каждый / г-хроматический граф, п 2, содержит - критический подграф. Действительно, если Я - такой наименьший порожденный подграф графа G, что % ( Щ - % ( 0), то Н - критический граф. [31]

Для доказательства достаточности нужно построить плоскую укладку данного графа G, обладающую определенными свойствами. [32]

Восемь помеченных графов третьего порядка. s, . j. [33]

Тогда возникает вопрос: Сколькими способами можно пометить данный граф. Чтобы ответить на этот вопрос, мы должны рассмотреть симметрии, или автоморфизмы, графа. Взаимно однозначное отображение а множества V ( G) на множество V ( G1), сохраняющее смежность, обычно называется изоморфизмом. [34]

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

Таким образом, снова получено противоречие, и данный граф не плоский. [36]

Восемь помеченных графов третьего порядка. [37]

Тогда возникает вопрос: Сколькими способами можно пометить данный граф. Чтобы ответить на этот вопрос, мы должны рассмотреть симметрии, или автоморфизмы, графа. Взаимно однозначное отображение а множества V ( G) на множество V ( Gj), сохраняющее смежность, обычно называется изоморфизмом. [38]

Максимальная планарная укладка графа G. [39]

Следовательно, построенное базовое решение является оптимальным для данного графа и улучшено быть не может. [40]

Приведение сигнального графа к конечному. [41]

Только при выполнении указанного условия система, соответствующая данному графу, имеет ненулевые решения. [42]

Покажите, что задача о коммивояжере ( По данному графу G с целочисленными весами ребер найти цикл, который включает каждый узел и сумма весов ребер которого не превосходит k) NP-полна. [43]

В данном параграфе определяются понятия подграфа, множества подграфов данного графа и дается оценка числа подграфов, которые можно образовать на произвольном непустом множестве элементов. [44]

К матричным методам относятся работы, использующие некоторые матрицы данного графа с целью построения матрицы инциденций. [45]

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