Степень - вершина
Cтраница 3
Найдите аналог теоремы 8А для бесконечных графов, у которых степени вершин имеют мощность большую, чем счетная. [31]
Поэтому на первом шаге 7У образуется первая строка, содержащая степени вершин v2 - vt, и столбец, указывающий, что v2 - vt соединены с вершиной, степень которой равна трем. [32]
Лемму 5 и теорему 6 удобно применять тогда, когда степени вершин примерно одинаковы. Если же граф имеет вершины с резко отличающимися степенями, в особенности если вершин с большой степенью ве-много, они дают чрезвычайно завышенные оценки; так, звездный граф, имеющий одну вершину степени р, а остальные вершины степени 1, по теореме 6 является р-раскрашиваемым, а на самом, деле он бихроматичен. [33]
Задача объединения электростанций или общая задача определения оптимального подграфа с ограниченными степенями вершин по существу связана с большинством экстремальных комбинаторных задач, для которых известны хорошие алгоритмы решения. Эти алгоритмы хороши в том смысле, что объемы вычислений при их применении растут как степенные функции при увеличении размерности задачи. В случае, когда все di2, мы получаем задачу, очень близкую к задаче коммивояжера. Если этот подграф связен, то мы получим минимальный маршрут коммивояжера при длинах ребер ctj. К сожалению, задача, получаемая после добавления к задаче объединения электростанций дополнительного ограничения связности подграфа, пока не решена. [34]
Теорема 8.1 дает условия существования m - фактора как чистые на степени вершин, так и смешанные на степени вершин и на число ребер. В литературе по теории графов обычно приводятся чистые условия - либо на степени вершин, либо на число ребер. В соответствии с этим возникают следующие два вопроса. [35]
Обозначим соответственно через р [ 0) и р 0) локальные степени вершин do и а. [36]
Способ упорядочения может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик. Показано ( см. [20]), что можно построить графы, для которых любой из эвристических методов дает сколь угодно плохие оценки хроматического числа. [37]
Тогда оставшаяся часть графа G будет двудольным графом с наибольшей из степеней вершин, равной р - 1, и мы можем по индукции установить осуществимость раскраски этой части графа G в остальные р - 1 цветов. Тем самым доказательство завершено. [38]
Способ упорядочивания может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик. Границы применимости этих эвристических методов демонстрируются у Митчема [17], показавшего, что можно построить графы, для которых любой из эвристических методов дает произвольно плохие оценки хроматического числа. [39]
 |
Примеры графов. [40] |
Число ребер, входящих в данную вершину и выходящих из нее характеризует степень вершины. Число ребер графа равно половине суммы степеней его вершин. Граф однороден ( регулярен), если степени всех его вершин одинаковы, степень их выражает и степень графа. Молекулу Н2 изображает граф 1 - й степени, молекулу О2 - граф 2 - й степени, N2 - граф 3 - й степени, граф, изображающий молекулу СО2, неоднороден, степени его вершин С и О различны. [41]
Ясно, что если et - ( v, iv, то степень вершины et в L ( G) есть d ( v) - i d ( w) - i d ( v) d ( w) - 2, где d ( y), d ( u) - степени вершин v, w в G. [42]
Рассмотрим следующую задачу построения остовного подграфа Ор общего неориентированного графа О, степени вершин которого по отношению к подграфу Ор заданы. [43]
Рассмотрим следующую задачу построения остовного подграфа Gp общего неориентированного графа G, степени вершин которого по отношению к подграфу Gp заданы. [44]
Если цикл S содержит одну вершину степени 2, скажем Уь а степени вершин Vt больше 2 для всех /, 2 / г, будем рассуждать следующим образом. [45]
Страницы: 1 2 3 4