Звездный граф

Cтраница 1

Звездный граф, определяемый вершиной а, состоит из всех ребер G, имеющих а концевой точкой. Петли в а могут как включаться, так и не включаться в звезду. [1]

Звездный граф, определяемый вершиной а, состоит из всех ребер G, имеющих я концевой точкой. Петли в а могут как включаться, так и не включаться в звезду. [2]

Может ли звездный граф быть смежностным графом другого графа. [3]

Может ли звездный граф быть смсжностпым графом другого графа. [4]

Сложности циклоалканов ( С.| Звездные графы. [5]

В табл. 2 представлены прогрессия звездных графов и их индексы. [6]

С ( G) принимал наибольшее значение, равное единице, в случае звездных графов. [7]

Пусть Н - минимальный покрывающий суграф для G; согласно теореме 13.2.1, Н является суммой частей звездных графов. [8]

Пусть / / - минимальный покрывающий суграф для G; согласно теореме 13.2.1, Н является суммой частей звездных графов. [9]

Лемму 5 и теорему 6 удобно применять тогда, когда степени вершин примерно одинаковы. Если же граф имеет вершины с резко отличающимися степенями, в особенности если вершин с большой степенью ве-много, они дают чрезвычайно завышенные оценки; так, звездный граф, имеющий одну вершину степени р, а остальные вершины степени 1, по теореме 6 является р-раскрашиваемым, а на самом, деле он бихроматичен. [10]

Обе эти теоремы удобно применять тогда, когда степени всех вершин графа примерно одинаковы. Так, из теоремы 17А сразу получается, что всякий кубический граф 4-рас-крашиваем, а из теоремы 17В - что всякий связный кубический граф ( кроме / С4) на самом деле 3-раскрашиваем. С другой стороны, если граф имеет несколько вершин довольно высокой степени, эти теоремы дают очень мало. Хорошей иллюстрацией служит звездный граф К п который по теореме Брукса n - раскрашиваем, а на самом деле является 2-хроматическим. В настоящее время действительно эффективного способа, позволяющего улучшить положение, не существует, хотя метод, предлагаемый в упр. [11]

Определение 6.2. Двудольный граф СЫ ( А В Е назовем магистральным, если в результате удаления в нем всех висячих ребер полученный граф будет состоять из простой цепи и / или изолированных вершин. Здесь висячим считается ребро, инцидентное висячей вершине. Обработку графа G, при которой каждая вершина просматривается однократно, будем называть магистральной. Обработка магистральных двудольных графов характеризуется однократным просмотром каждой вершины. Заметим, в частности, что ребро и звездный граф, как связные компоненты графов, отражающих соответственно взаимосвязи типов 1: 1 и l: N, также являются магистральными. [12]

Страницы: 1