Cтраница 1
Полные графы обязательно обладают этим свойством. Тоже относится к графам, которые являются сами простыми циклами и цепями, имеющими четное число вершин. [1]
Рассмотренные полные графы являются предельным случаем максимально непланарных графов. Представляет интерес исследование минимально непланарных графов. [2]
В практических задачах полные графы встречаются редко. В таблице расстояний соответствующие клетки удобно оставлять незаполненными. [3]
На рис. 4.2 и 4.3 изображены полные графы на восемь вершин. [4]
Найти хорошую характеризацию для графов, которые можно разбить на вершинно непересекающиеся полные графы, содержащие хотя бы по две вершины. [5]
Саксов граф - подграф исходного графа G, все ком поненты которого являются полными графами одновалентного типа ( изолированные связи) и ( или) циклами. [6]
В общем случае, при рассмотрении графа К ( j), компоненты которого являются полными графами, Группа Г ( К ()) может быть представлена в виде произведения ( см. Харари [1], стр. [7]
В общем случае, при рассмотрении графа К ( /), компоненты которого являются полными графами, группа Г ( К (; )) может быть представлена в виде произведения ( см. Харари [1], стр. [8]
Найти несколько первых членов производящих функций, перечисляющих такие связные графы, блоки которых являются полными графами порядка: ( а) 2, ( Ь) 3, ( с) 4 или ( d) являются четырехвершинными циклами. [9]
Найти несколько первых членов производящих функций, перечисляющих такие связные графы, блоки которых являются полными графами порядка: ( а) 2, ( Ь) 3, ( с) 4 или ( d) являются четырехвершинными циклами. [10]
Пусть Gl - граф, содержащий для каждого / с ровно rk компонент связности, представляющих собой полные графы с / с вершинами. Аналогично, пусть граф G2 имеет для каж. [11]
Пусть Gt - граф, содержащий для каждого k ровно r / t компонент связности, представляющих собой полные графы с k вершинами. [12]
Пример графа Кц убеждает, что вместо рассмотрения 2-упаковки нечетных циклов с последующим делением на 2 использовать 1-упа-ковку нечетных циклов недостаточно. Рассматривая полные графы большего размера, легко убедиться в том, что условием планарности пренебрегать нельзя. Для разрушения всех нечетных циклов из графа / LS нужно удалить 4 ребра. С другой стороны, каждый нечетный цикл имеет не менее трех ребер и, следовательно, любая Аг-упаковка нечетных циклов состоит не более чем из 10fc / 3 4fc циклов. [13]
Упрощение задания отношения эквивалентности достигается следующим образом. Gw, которые все являются полными графами на классах эквивалентности. [14]
К сожалению, отношение О / Ф ( С) может экспоненциально расти с ростом размера р задачи, что в общем случае делает этот метод непригодным. С другой стороны, существуют некоторые графы ( например, полные графы), для которых отношение П / Ф ( С) полиномиально ограничено. Есть ли более интересные классы таких графов, авторам не известно. Однако бесспорной истиной является тот факт, что применение вероятностных методов для задач комбинаторного перечисления, в духе рассмотренного примера, широко не используется и представляет собой весьма перспективную область для исследований. [15]